스패닝 트리(Spanning Tree)
트리(tree)를 간단히 정의하면 사이클(cycle)이 하나도 없는 연결 그래프입니다. 여기서 사이클이란 간선을 반복해서 사용하지 않고 어떤 노드에서 출발해 다시 자기 자신에게 돌아올 수 있는 경로를 의미합니다.
연결 그래프 G에 대한 스패닝 트리(spanning tree)는 G의 모든 정점을 포함하는 트리로 정의됩니다.
스패닝 트리는 인터넷 라우팅 알고리즘에서 널리 활용됩니다. 실제 인터넷 환경에서 컴퓨터(노드)들은 수많은 중복된 물리적 회선으로 서로 연결되어 있는데, 스패닝 트리를 활용하면 루프 없이 효율적이고 안정적인 통신 경로를 구성할 수 있습니다.
그래프의 스패닝 트리 개수 구하기
n개의 정점을 가진 완전 그래프(complete graph)라면, 스패닝 트리의 총 개수는 n^(n-2)개입니다. 여기서 n은 그래프 안에 있는 노드의 수를 나타냅니다. 완전 그래프에서 스패닝 트리의 개수를 세는 문제는 n개의 노드로 만들 수 있는 서로 다른 레이블 트리(labeled tree)의 개수를 세는 것과 동일하며, 이는 잘 알려진 케일리 공식(Cayley's formula)으로 계산할 수 있습니다.
연결성(Connectivity)
수학과 컴퓨터 과학에서 연결성(connectivity)은 그래프 이론의 가장 기본적인 개념 중 하나입니다.
연결성이란 남은 노드들을 고립된 부분 그래프(isolated subgraph)들로 분리시키기 위해 제거해야 하는 요소(노드 또는 간선)의 최소 개수를 의미합니다. 이 개념은 네트워크 플로우(network flow) 이론과도 매우 밀접한 관련이 있습니다.
위 그래프는 점선으로 표시된 간선이 제거되면 더 이상 연결 상태를 유지하지 못하고 끊어지게 됩니다.
정점 연결성(Vertex Connectivity)
그래프의 정점 연결성(vertex connectivity)은 그래프의 연결을 끊기 위해 삭제해야 하는 노드의 최소 개수를 뜻합니다. 경우에 따라 '점 연결성(point connectivity)' 또는 단순히 '연결성(connectivity)'이라고도 불립니다.
간선 연결성(Edge Connectivity)
간선 연결성(edge connectivity)은 그래프에서 간선을 삭제했을 때 그래프가 분리되기 위해 필요한 간선의 최소 개수를 의미하며, '선 연결성(line connectivity)'이라고도 표현합니다.
연결되어 있지 않은 그래프(disconnected graph)의 간선 연결성은 0이며, 그래프 브리지(graph bridge)를 하나 가진 연결 그래프의 간선 연결성은 1입니다.
거리(Distance)
트리에서 두 노드 사이의 거리는 최소 공통 조상(LCA, Lowest Common Ancestor)을 이용해 효율적으로 계산할 수 있습니다. 계산 공식은 다음과 같습니다.
Dist(d1, d2) = Dist(root, d1) + Dist(root, d2) - 2*Dist(root, lca) 'd1'과 'd2' : 거리를 구하려는 두 노드(키) 'root' : 주어진 이진 트리의 루트 'lca' : d1과 d2의 최소 공통 조상 Dist(d1, d2) : d1과 d2 사이의 거리