신장 부분 그래프

1. 개요

신장 부분 그래프는 그래프의 부분 그래프로, 원래 그래프의 모든 정점을 포함한다. 신장 부분 그래프 중 나무 그래프는 신장 나무 부분 그래프, 숲 그래프는 신장 숲 부분 그래프라고 한다. 신장 부분 그래프는 다양한 특성을 가지며, 특히 가중치가 있는 그래프에서 간선 비용의 합을 최소화하는 최소 비용 신장 트리를 찾는 문제가 중요하다. 최소 비용 신장 트리는 크루스칼 알고리즘이나 프림 알고리즘을 통해 구할 수 있으며, 최단 경로 문제 해결에도 활용된다. 또한, 신장 트리의 수는 그래프의 불변량으로, 케일리 공식 등을 통해 계산할 수 있다. 신장 트리는 통신망 구축, 경로 탐색, 네트워크 라우팅 등 다양한 분야에 응용된다.

2. 정의

그래프 $\backslash Gamma$의 부분 그래프 $\backslash Gamma\text{'}\backslash subseteq\backslash Gamma$가 모든 꼭짓점을 포함하면($\backslash operatorname\; V(\backslash Gamma\text{'})=\backslash operatorname\; V(\backslash Gamma)$), $\backslash Gamma\text{'}$를 $\backslash Gamma$의 신장 부분 그래프라고 한다. 나무 그래프인 신장 부분 그래프는 신장 나무(spanning subtree^영어)라고 하며, 숲 그래프인 신장 부분 그래프는 신장 숲(spanning subforest^영어)이라고 한다.

나무는 연결된 무방향 그래프이며, 사이클이 없다. 그래프 G의 신장 트리는 G의 모든 정점을 포함하고 G의 부분 그래프(트리의 모든 변이 G에 속함)인 경우를 말한다. 연결 그래프 G의 신장 트리는 사이클을 포함하지 않는 G의 변들의 최대 집합 또는 모든 정점을 연결하는 변들의 최소 집합으로 정의할 수도 있다.

2.1. 인자

신장 부분 그래프 가운데, $r$-정규 그래프인 것을 $r$차 인자($r$次因子, $r$-factor^영어)라고 한다. 특히, 1차 인자는 완벽 부합이라고 한다. (0차 인자는 꼭짓점 집합 위의 무변 그래프이다.)

2.2. 기본 사이클과 기본 컷셋

스패닝 트리에 단 하나의 간선을 추가하면 사이클이 생성되는데, 이러한 사이클을 해당 트리에 대한 기본 사이클이라고 한다. 스패닝 트리에 없는 각 간선에 대해 고유한 기본 사이클이 존재하며, 따라서 기본 사이클과 스패닝 트리에 없는 간선 사이에는 일대일 대응이 있다. V개의 정점을 가진 연결 그래프에서 모든 스패닝 트리는 V − 1개의 간선을 가지므로, E개의 간선을 가진 그래프와 그 스패닝 트리는 E − V + 1개의 기본 사이클을 갖는다. (스패닝 트리에 포함된 간선 수를 빼서 스패닝 트리에 포함되지 않은 간선의 수를 구한다.) 주어진 스패닝 트리에 대해, 모든 E − V + 1개의 기본 사이클 집합은 사이클 기저를 형성한다. 즉, 사이클 공간의 기저이다.

주어진 신장 트리에 대한 기본 컷셋의 개념은 기본 사이클의 개념과 쌍대 관계에 있다. 신장 트리의 단 하나의 에지를 삭제하면 정점들은 두 개의 서로소 집합으로 분할된다. 기본 컷셋은 동일한 분할을 수행하기 위해 그래프 G에서 제거해야 하는 에지들의 집합으로 정의된다. 따라서 각 신장 트리는 신장 트리의 각 에지에 대해 하나의 V − 1개의 기본 컷셋을 정의한다.

기본 컷셋과 기본 사이클 간의 쌍대성은 사이클 에지가 신장 트리에 없는 경우 해당 사이클의 다른 에지들의 컷셋에만 나타날 수 있고, 반대로 컷셋의 에지는 컷셋에 해당하는 에지를 포함하는 사이클에만 나타날 수 있다는 점에 의해 성립된다. 이러한 쌍대성은 매트로이드 이론을 사용하여 표현할 수도 있다. 신장 트리는 그래픽 매트로이드의 기저이고, 기본 사이클은 기저에 하나의 요소를 추가하여 형성된 집합 내의 고유한 회로이며, 기본 컷셋은 쌍대 매트로이드에서 동일한 방식으로 정의된다.

2.3. 신장 숲

그래프에서 숲은 분리(연결되지 않은)된 나무 그래프들의 집합이다. 신장 숲은 추가적인 요구 사항이 있는 숲인 부분 그래프이다. 신장 숲에 대한 두 가지 주요 정의가 있다.

* 대부분의 그래프 이론 서적과 논문에서는 신장 숲을 모든 정점을 포함하는 숲으로 정의한다. 즉, 그래프의 각 정점이 숲에 포함된다. 연결된 그래프는 각 정점이 단일 정점 트리를 형성하는, 가장자리가 없는 숲과 같이 연결되지 않은 신장 숲을 가질 수 있다.

* 일부 그래프 이론 저자들은 신장 숲을 주어진 그래프의 최대 비순환 부분 그래프, 또는 각 연결 요소에서 신장 트리를 포함하는 부분 그래프로 정의한다.

이 두 정의는 혼동될 수 있으므로, "전체 신장 숲"(주어진 그래프와 동일한 수의 구성 요소를 가진 신장 숲) 또는 "최대 신장 숲"(최대 숲은 필연적으로 모든 정점을 포함)이라는 용어를 사용하기도 한다.

3. 성질

임의의 그래프 $\backslash Gamma$의 신장 부분 그래프의 수는 $2^$

👆

좌우로 밀어서 보기

📌 열 고정 해제

이다. (여기서 $\backslash operatorname\; E(\backslash Gamma)$는 $\backslash Gamma$의 간선 집합이다.) 모든 연결 그래프는 적어도 하나의 신장 나무를 갖는다. (무한 그래프의 경우 선택 공리가 필요하다.) 연결 그래프의 신장 트리는 순환 매트로이드의 기저와 같다.

4. 최소 비용 신장 트리 (Minimum Spanning Tree)

연결 유한 그래프 $\backslash Gamma$와 함수 $f\backslash colon\backslash operatorname\; E(\backslash Gamma)\backslash to\backslash mathbb\; R$ (비용 함수, cost function^영어)가 주어졌을 때, $\backslash Gamma$의 최소 비용 신장 나무 부분 그래프(最小費用身長部分graph, minimum cost spanning tree^영어)는 $\backslash Gamma$의 연결 신장 부분 그래프 $\backslash Gamma\text{'}\backslash subseteq\backslash Gamma$ 가운데, 변들의 비용의 합
:$\backslash sum\_\{e\backslash in\backslash operatorname\; E(\backslash Gamma\text{'})\backslash subseteq\backslash operatorname\; E(\backslash Gamma)\}f(e)\backslash in\backslash mathbb\; R$
를 최소화하는 것이다. 이는 항상 나무 그래프가 되며, 항상 존재한다.

각 변에 가중치(비용)가 있는 경우, 최소 총합 비용으로 구성된 신장 트리를 최소 신장 트리라고 한다. 어떤 분야의 그래프 이론에서는 가중 그래프의 최소 신장 트리를 찾는 것이 종종 유용하다.

최소 신장 트리를 찾는 대표적인 알고리즘은 다음과 같다:

* 크루스칼 알고리즘: 단순한 탐욕법으로 계산량은 $O(E\; \backslash log\{E\})$이다.
* 프림 알고리즘: 탐욕법이지만 계산량은 $O(E\; +\; V\; \backslash log\{V\})$이다. 변의 수가 정점에 비해 충분히 클 때는 $O(E)$로 간주할 수 있다.

변의 가중치가 균일한 경우에는 너비 우선 탐색으로 $O(E)$에 구할 수 있다.

5. 최단 경로 트리 (Shortest Path Tree)

최단 경로 문제는 어떤 정점에서 다른 정점으로 가는 비용이 가장 적게 드는 경로를 찾는 문제이다. 어떤 정점에서 다른 모든 정점으로 이동하는 비용이 가장 적게 드는 트리를 최단 경로 트리라고 하며, 이는 신장 트리이다. 최단 경로 트리를 구하는 방법으로는 다익스트라 알고리즘, 벨만-포드 알고리즘 등이 있다.

6. 신장 트리 계산

케일리 공식에 따라, $K\_n$의 $2^\{n(n-1)/2\}$개의 신장 부분 그래프 가운데 $n^\{n-2\}$개가 신장 트리이다.

연결된 그래프의 스패닝 트리의 수 t(G)는 잘 연구된 불변량이다. 특정 그래프의 경우, t(G)는 다음과 같이 계산할 수 있다.

👆

좌우로 밀어서 보기

📌 열 고정 해제

그래프	신장 트리 개수(t(G))
트리	1
사이클 그래프 Cn	n
완전 그래프 Kn	$n^\{n-2\}$ (케일리 공식)
완전 이분 그래프 $K\_\{p,q\}$	$p^\{q-1\}q^\{p-1\}$
n차원 하이퍼큐브 그래프 $Q\_n$	$2^\{2^n-n-1\}\backslash prod\_\{k=2\}^n\; k^$

7. 알고리즘

유한 연결 그래프의 최소 비용 신장 부분 그래프는 프림 알고리즘이나 크러스컬 알고리즘을 사용하여 다항 시간 안에 찾을 수 있다. 그래프의 단일 신장 트리는 선형 시간 안에 깊이 우선 탐색 또는 너비 우선 탐색으로 찾을 수 있다. 이 두 알고리즘 모두 임의의 정점 v에서 시작하여 발견한 정점의 이웃을 반복하고 탐색되지 않은 각 이웃을 나중에 탐색할 데이터 구조에 추가하여 주어진 그래프를 탐색한다. 이들은 이 데이터 구조가 스택 (깊이 우선 탐색의 경우)인지 큐 (너비 우선 탐색의 경우)인지에 따라 다르다. 어느 경우든, 루트 정점 v를 제외한 각 정점을 발견된 정점에 연결하여 신장 트리를 형성할 수 있다. 이 트리는 이를 구성하는 데 사용된 그래프 탐색 알고리즘에 따라 깊이 우선 탐색 트리 또는 너비 우선 탐색 트리로 알려져 있다. 깊이 우선 탐색 트리는 19세기에 깊이 우선 탐색을 발견한 사람의 이름을 딴 트레모 트리라고 불리는 신장 트리의 특별한 경우이다.

신장 트리는 병렬 및 분산 컴퓨팅에서 프로세서 집합 간의 통신을 유지하는 방법으로 중요하다. 예를 들어 OSI 링크 계층 장치에서 사용되는 스패닝 트리 프로토콜 또는 분산 컴퓨팅을 위한 Shout (프로토콜)를 참조할 수 있다. 그러나 순차 컴퓨터에서 신장 트리를 구성하기 위한 깊이 우선 및 너비 우선 방법은 병렬 및 분산 컴퓨터에 적합하지 않다. 대신, 연구자들은 이러한 계산 모델에서 신장 트리를 찾기 위한 몇 가지 더 전문화된 알고리즘을 고안했다.

각 변에 가중치(비용)가 있는 경우, 최소 총합 비용으로 구성된 신장 트리를 최소 신장 트리라고 한다.

8. 응용

경로 탐색 알고리즘, 다익스트라 알고리즘, A* 탐색 알고리즘 등은 문제를 해결하기 위한 중간 단계로 내부적으로 신장 트리를 구축한다.

전력 네트워크, 배선 연결, 배관, 자동 음성 인식 등 비용을 최소화하기 위해 최소 신장 트리를 찾는 과정에서 중간 단계로 신장 트리(또는 여러 개의 트리)를 점진적으로 구축하는 알고리즘을 사용한다.

인터넷 및 기타 통신망은 일부 루프를 포함하는 메시 토폴로지에서 노드를 연결하는 전송 링크를 가지고 있다. 브리지 루프 및 라우팅 루프를 방지하기 위해 스패닝 트리 프로토콜, OSPF, 링크 상태 라우팅 프로토콜, 증강 트리 기반 라우팅 등과 같은 라우팅 프로토콜은 각 라우터가 신장 트리를 기억하도록 요구한다.

Xuong 트리는 위상 기하학에서 최대 종수를 가진 그래프 임베딩을 찾기 위해 사용되는 특수한 종류의 신장 트리이다. Xuong 트리는 나머지 그래프에서 홀수 개의 간선을 가진 연결 요소의 수가 가능한 한 적도록 하는 신장 트리이다. Xuong 트리와 관련된 최대 종수 임베딩은 다항 시간 내에 찾을 수 있다.

전역 트리의 개념은 컴퓨터 네트워크 관련 분야에서 중요한 위치를 차지한다. 단말, 라우터, 스위칭 허브 등을 정점으로, 연결된 케이블을 변으로 간주하면 네트워크는 하나의 거대한 그래프가 되며, 전역 트리는 그 그래프에 대한 경로 구축 절차로 간주할 수 있다. OSPF, STP 등에서는 최단 경로 트리를 구성하여 통신 경로를 결정한다.