목록BFS (1)

Doctor Pepper

네트워크 특징 (2) : 트리 및 최단 경로 찾기

1. 트리 트리는 모든 링크를 제거하지 않고 단 하나의 링크만 삭제해도 네트워크가 두 개의 부분으로 나뉘는 특별한 형태의 무방향 연결 네트워크를 의미한다. 이러한 네트워크 구조를 트리(Tree)라고 부른다.링크 수트리의 노드가 n개라면, 항상 n-1개의 링크를 가짐사이클 없음트리에는 사이클(순환 경로)이 존재하지 않으며, 이를 귀류법으로 증명할 수 있음- 만약 트리에 사이클이 존재한다고 가정하면, 사이클 내의 링크 중 하나를 제거하더라도 여전히 모든 노드가 연결된 상태를 유지할 수 있음- 이 경우, 트리는 더 이상 링크를 하나 삭제해도 분리되지 않는 상태가 되며, 트리의 정의에 어긋남.(따라서, 트리는 사이클을 가질 수 없음)사이클이 없기 때문에 트리의 임의의 두 노드를 연결하는 경로는 항상 하나만 존재..
Network 심화/네트워크 분석 2024. 11. 27. 12:30
이전 Prev 1 Next 다음