스패닝 트리

Spanning tree
네트워크 프로토콜에 대해서는 스패닝 트리 프로토콜을 참조하십시오.기타 용도는 스패닝 트리(동음이의)를 참조하십시오.
그리드 그래프의 스패닝 트리(파란색 헤비 에지)

그래프 이론의 수학적 분야에서, 비방향 그래프 G의 스패닝 트리 T는 G의 모든 정점을 포함하는 나무인 하위 그래프다.[1]일반적으로 그래프에는 여러 개의 스패닝 트리가 있을 수 있지만 연결되지 않은 그래프에는 스패닝 트리가 포함되지 않는다(아래 스패닝 포리스트 참조).G의 모든 가장자리가 G의 스패닝 트리 T의 가장자리인 경우, G는 트리로서 T와 동일하다(즉, 나무는 고유한 스패닝 트리를 가지고 있고 그 자체다).

적용들

Dijkstra의 알고리즘과 A* 검색 알고리즘을 포함한 몇 가지 경로 탐색 알고리즘은 문제를 해결하는 중간 단계로 스패닝 트리를 내부적으로 구축한다.

전력망, 배선 연결, 배관, 자동 음성 인식 등의 비용을 최소화하기 위해 최소 스패닝 트리를 찾는 과정에서 중간 단계로서 스패닝 트리(또는 그와 같은 트리)를 점진적으로 구축하는 알고리즘을 이용하는 경우가 많다.[2]

인터넷과 많은 다른 통신 네트워크들은 일부 루프를 포함하는 망사 위상에서 노드를 서로 연결하는 전송 링크를 가지고 있다.브리지 루프와 라우팅 루프를 피하기 위해 스패닝 트리 프로토콜, 개방 최단 경로 우선, 링크 상태 라우팅 프로토콜, 증강 트리 기반 라우팅 등을 포함하여 그러한 네트워크를 위해 설계된 많은 라우팅 프로토콜이 있다.—스패닝 트리를 기억하도록 각 라우터 연결

특별한 종류의 스패닝 트리인 쉬옹 트리는 위상학적 그래프 이론에서 최대 속성이 포함된 그래프를 찾기 위해 사용된다.쉬옹 트리는 스패닝 트리로, 나머지 그래프에서 가장자리 수가 홀수인 연결된 성분의 수가 가능한 한 작다.쉬옹 나무와 관련된 최대 유전자를 내장하는 것은 다항식 시간에 찾을 수 있다.[3]

정의들

트리는 사이클이 없는 연결된 비방향 그래프다.G(즉, G의 모든 꼭지점을 포함)에 걸쳐 있는 경우 그래프 G의 스패닝 트리로서 G의 서브그래프(트리의 모든 가장자리는 G에 속한다)이다.연결된 그래프 G의 스패닝 트리는 사이클이 없는 G의 최대 에지 집합 또는 모든 정점을 연결하는 최소 에지 집합으로도 정의할 수 있다.

기본 사이클

스패닝 트리에 하나의 에지만 추가하면 주기가 생성된다; 그러한 주기는 기본 주기라고 불린다.스패닝 트리에 없는 각 가장자리에는 뚜렷한 기본 주기가 있으므로, 스패닝 트리에 없는 기본 주기와 가장자리 사이에는 일대일 일치성이 있다.V 정점이 있는 연결된 그래프의 경우, 모든 스패닝 트리는 V - 1 가장자리를 가지며, 따라서 E 가장자리의 그래프와 스패닝 트리 중 하나의 기본 사이클(스패닝 트리에 포함된 가장자리 수로 감산된 가장자리 수, 스패닝 트리에 포함되지 않은 가장자리 수를 나타냄)을 갖는다.주어진 신장 트리의 경우 모든 E - V + 1 기본 사이클 집합이 사이클 공간을 위한 기초인 사이클 베이스를 형성한다.[4]

기본 컷셋

기본 사이클의 개념에 이중적인 것은 기본 컷셋의 개념이다.스패닝 트리의 한쪽 가장자리만 삭제하면 정점이 두 개의 분리 세트로 분할된다.기본 컷셋은 동일한 파티션을 수행하기 위해 그래프 G에서 제거해야 하는 가장자리 집합으로 정의된다.따라서 각 스패닝 트리는 스패닝 트리의 각 가장자리마다 하나씩 V - 1 기본 컷셋 세트를 정의한다.[5]

기본 컷셋과 기본 사이클 사이의 이중성은 스패닝 트리에 없는 사이클 에지는 사이클 내 다른 에지의 컷셋에만 나타날 수 있다는 점에 주목함으로써 설정되며, 반대로 컷셋의 에지는 컷셋에 해당하는 에지를 포함하는 사이클에서만 나타날 수 있다.이 이중성은 또한 매트로이드 이론을 이용하여 표현할 수 있는데, 스패닝 트리가 그래픽 매트로이드의 기초가 되는 것에 따라, 기본 사이클은 베이스에 하나의 원소를 추가함으로써 형성된 세트 내의 고유 회로이며, 기본 컷셋은 이중 매트로이드로부터 동일한 방법으로 정의된다.[6]

스패닝 숲

연결되지 않은 그래프에서는 스패닝 트리가 있을 수 없으며, 대신 스패닝 포리스트를 고려해야 한다.여기에는 두 가지 경쟁적 정의가 있다.

  • 일부 저자는 스패닝 포리스트를 주어진 그래프의 최대 반복 하위 그래프 또는 그래프의 각 연결된 구성 요소에서 스패닝 트리로 구성된 그래프로 간주한다.[7]
  • 다른 저자의 경우 스패닝 포리스트는 모든 정점을 가로지르는 포리스트로, 그래프의 각 꼭지점이 숲의 꼭지점이라는 의미일 뿐이다.이 정의의 경우, 연결된 그래프라도 각 꼭지점이 단일 버텍스 트리를 형성하는 숲과 같이 분리되지 않은 스패닝 포리스트를 가질 수 있다.[8]

이 두 정의 사이의 혼동을 피하기 위해, 그로스 & 옐런(2005)은 주어진 그래프와 같은 연결성을 가진 스패닝 숲에 대해 "완전 스패닝 숲"이라는 용어를 제안하고, 본디 & 머티(2008)는 대신 이러한 종류의 숲을 "최대 스패닝 숲"[9]이라고 부른다.

스패닝 트리 카운팅

Cayley의 공식은 완전한 그래프에 스패닝 나무의 수를 카운트한다.There are trees in , trees in , and trees in .

연결된 그래프의 스패닝 트리의 숫자 t(G)는 잘 연구된 불변량이다.

특정 그래프에서

t(G)를 직접 계산하기 쉬운 경우도 있다.

  • G 자체가 나무라면 t(G) = 1이다.
  • G가 정점이 n인 사이클 그래프 C인n 경우 t(G) = n.
  • 정점이 n인 전체 그래프의 경우, 케이리의 공식은[10] 스패닝 트리 수를 n으로n − 2 제공한다.
  • G가 완전한 양분 그래프 , t ( G[11])= - - - 1 t
  • n차원 하이퍼큐브 그래프 의 경우[12]스패닝 트리 수는 t)= - n- ∏ k= k( ) = 2n k = 2n k) =2n k = 2n (n kn}k^{n}kn}{n^{n}k^{n^{n}{n}{n

임의 그래프에서

주요 기사: 키르흐호프의 정리

보다 일반적으로, 어떤 그래프 G의 경우, 숫자 t(G)는 Kirchhoff의 행렬-트리 정리를 이용하여 그래프에서 파생된 행렬의 결정요인으로 다항식 시간으로 계산할 수 있다.[13]

특히 t(G)를 계산하기 위해 행과 열이 모두 G의 정점에 의해 색인화된 정사각형 행렬인 그래프의 라플라시안 행렬을 구성한다.i행과 j열의 항목은 다음 세 가지 값 중 하나이다.

  • i = j일 경우 정점 i의 정도
  • -1, 정점 i와 j가 인접한 경우 또는
  • 0, 정점 i와 j가 서로 다르지만 인접하지는 않은 경우.

결과 행렬은 단수적이므로 결정 인자는 0이다.그러나 임의로 선택한 꼭지점에 대한 행과 열을 삭제하면 결정인자가 정확히 t(G)인 더 작은 행렬로 이어진다.

삭제-연락

G가 그래프 또는 다중글자이고 e가 G의 임의의 가장자리인 경우 G의 스패닝 트리의 숫자 t(G)는 삭제-접속 반복 t(G) = t(G - e) + t(G/e)를 만족한다. 여기서 G - e는 e를 삭제하여 얻은 다중글자이고 G/e는 e에 의한 G의 수축이다.[14]이 공식에서 t(G - e)라는 용어는 엣지 e를 사용하지 않는 G의 스패닝 트리를 계수하고 t(G/e)라는 용어는 e를 사용하는 G의 스패닝 트리를 계수한다.

이 공식에서, 주어진 그래프 G가 다중 글자인 경우 또는 수축으로 인해 두 개의 정점이 여러 모서리에 의해 서로 연결되는 경우, 중복 에지는 제거되지 않아야 하며, 이는 잘못된 총계를 야기할 수 있기 때문이다.예를 들어, 두 꼭지점을 k 가장자리로 연결하는 결합 그래프는 k개의 서로 다른 신장 트리를 가지고 있으며, 각각은 이러한 가장자리의 단일으로 구성된다.

투테 다항식

주요 기사:투테 다항식

그래프의 Tutte 다항식은 그래프의 스패닝 트리에 걸쳐, 트리의 "내부 활동"과 "외부 활동"으로부터 계산된 용어의 합으로 정의할 수 있다.인수(1,1)에서 그것의 값은 신장 트리의 수 또는 연결되지 않은 그래프에서 최대 신장 숲의 수입니다.[15]

Tutte 다항식도 삭제-축소 재발을 사용하여 계산할 수 있지만, 그 계산 복잡성은 높은데, 그 인수의 많은 값에 대해 계산은 정확히 #P-완전하며, 또한 보장된 근사비로 근사치하기도 어렵다.키르흐호프의 정리를 이용해 평가할 수 있는 지점(1,1)은 몇 안 되는 예외 중 하나이다.[16]

알고리즘

건설

그래프의 단일 스패닝 트리는 깊이 우선 검색 또는 너비 우선 검색으로 선형 시간 내에 찾을 수 있다.이 두 알고리즘 모두 임의의 정점 v에서 시작하여, 그들이 발견한 정점의 이웃을 루핑하여 각각의 미개척 이웃을 나중에 탐구할 데이터 구조에 추가함으로써 주어진 그래프를 탐구한다.이들은 이 데이터 구조가 스택(심층 우선 검색의 경우)인지 대기열(범위 우선 검색의 경우)인지에 따라 다르다.어느 경우든 루트 꼭지점 v가 아닌 각 꼭지점을 발견된 정점에 연결하면 신장 트리를 형성할 수 있다.이 트리는 그것을 구성하는 데 사용되는 그래프 탐색 알고리즘에 따라 깊이 우선 검색 트리 또는 폭 우선 검색 트리로 알려져 있다.[17]깊이 우선 탐색 트리는 19세기 깊이 우선 탐색의 발견자의 이름을 딴 '트레모 나무'라 불리는 신장 나무의 특별한 경우다.[18]

스패닝 트리는 프로세서 세트 간의 통신을 유지하기 위한 방법으로 병렬 컴퓨팅과 분산 컴퓨팅에서 중요하다. 예를 들어 OSI 링크 계층 장치에 사용되는 스패닝 트리 프로토콜 또는 분산 컴퓨팅에 대한 외침(프로토콜)을 참조하십시오.그러나 순차적 컴퓨터에 신장 트리를 구성하는 깊이 우선 및 폭 우선 방법은 병렬 및 분산형 컴퓨터에는 적합하지 않다.[19]대신, 연구원들은 이러한 연산 모델에서 신장 트리를 찾기 위해 몇 가지 더 전문화된 알고리즘을 고안해냈다.[20]

최적화

그래프 이론의 특정 분야에서는 가중 그래프의 최소 스패닝 트리를 찾는 것이 종종 유용하다.스패닝 트리의 다른 최적화 문제들 또한 연구되었는데, 여기에는 최대 스패닝 트리, 최소 k 정점을 가로지르는 최소 트리, 정점당 가장자리가 가장 적은 스패닝 트리, 잎 수가 가장 많은 스패닝 트리, 가장 적은 스패닝 트리(해밀턴식 경로 문제와 밀접하게 관련됨)가 포함된다.m), 최소 직경 스패닝 트리 및 최소 확장 스패닝 트리.[21][22]

유클리드 평면과 같은 기하학적 공간의 유한한 점 집합에 대해서도 최적의 신장 트리 문제가 연구되었다.그러한 입력에서 스패닝 트리는 다시 주어진 포인트에 정점이 있는 트리가 된다.나무의 품질은 점 쌍 사이의 유클리드 거리를 각 가장자리의 무게로 사용하여 그래프와 동일한 방법으로 측정한다.따라서 예를 들어 유클리드 최소 스패닝 트리는 유클리드 에지 중량이 있는 전체 그래프에서 그래프 최소 스패닝 트리와 동일하다.단, 최적화 문제를 해결하기 위해 이 그래프를 구성할 필요는 없다. 예를 들어, 유클리드 최소 스패닝 트리 문제는 Delaunay 삼각측량을 구성한 다음 결과 삼각형에 선형 시간 평면 그래프 최소 스패닝 트리 알고리즘을 적용하면 O(n log n) 시간에 더 효율적으로 해결할 수 있다.ulation[21]

무작위화

같은 확률의 모든 신장 나무 중에서 무작위로 선택한 신장 트리를 균일한 신장 트리라고 한다.Wilson의 알고리즘은 주어진 그래프에서 무작위로 산책하고 이 걷기에 의해 생성된 사이클을 지우는 과정에 의해 다항 시간 내에 균일한 신장 트리를 생성하는데 사용될 수 있다.[23]

균일하지 않지만 무작위로 스패닝 트리를 생성하는 대안 모델은 무작위 최소 스패닝 트리다.이 모델에서 그래프의 가장자리에는 랜덤 가중치가 할당되고 그 다음 가중 그래프의 최소 신장 트리가 생성된다.[24]

열거

그래프에는 기하급수적으로 많은 스패닝 트리가 있을 수 있기 때문에 다항식 시간에 모두 나열할 수는 없다.그러나 알고리즘은 모든 신장 트리를 트리당 다항식 시간으로 나열하는 것으로 알려져 있다.[25]

무한 그래프에서

모든 유한 연결 그래프에는 스패닝 트리가 있다.그러나 무한 연결 그래프의 경우 스패닝 트리의 존재는 선택의 공리와 동등하다.무한 그래프는 그 정점의 각 쌍이 유한한 경로의 끝점 쌍을 이루면 연결된다.유한 그래프와 마찬가지로 트리는 유한 주기가 없는 연결된 그래프로서, 스패닝 트리는 가장자리의 최대 악순환 집합이나 모든 꼭지점을 포함하는 나무로 정의할 수 있다.[26]

그래프 안의 나무는 그 하위 그래프 관계에 의해 부분적으로 순서가 정해질 수 있으며, 이 부분 순서의 어떤 무한 체인은 상한(사슬 속 나무의 결합)을 가진다.조른의 보조정리법은 선택 공리와 많은 동등한 문장 중 하나로서, 모든 사슬이 상한으로 되어 있는 부분 순서에 최대 요소가 있어야 한다. 그래프의 나무에서 부분 순서에 있어서는 이 최대 요소는 스패닝 트리여야 한다.따라서 조른의 보조마법을 가정하면 모든 무한 연결 그래프에는 스패닝 트리가 있다.[26]

다른 방향에서는 집합의 패밀리가 주어진 경우 그래프의 모든 스패닝 트리가 집합 패밀리의 선택 함수에 해당하도록 무한 그래프를 구성할 수 있다.따라서 무한히 연결된 모든 그래프에 스패닝 트리가 있다면 선택의 공리는 참이다.[27]

지시된 다중 그래프

스패닝 트리의 개념은 지시된 다중 글자로 일반화될 수 있다.[28]방향 다중그래프 G에 정점 v가 주어진 경우, v에 뿌리를 둔 방향 스패닝 트리 T는 v를 제외한 모든 정점이 1을 초과하는 G의 반복 하위 그래프다.이 정의는 T의 "branches"가 v를 향할 때에만 충족된다.

참고 항목

참조

  1. ^ "Tree". NetworkX 2.6.2 documentation. Retrieved 2021-12-10. For trees and arborescence, the adjective “spanning” may be added to designate that the graph, when considered as a forest/branching, consists of a single tree/arborescence that includes all nodes in the graph.
  2. ^ Graham, R. L.; Hell, Pavol (1985). "On the History of the Minimum Spanning Tree Problem" (PDF).
  3. ^ Beineke, Lowell W.; Wilson, Robin J. (2009), Topics in topological graph theory, Encyclopedia of Mathematics and its Applications, vol. 128, Cambridge University Press, Cambridge, p. 36, doi:10.1017/CBO9781139087223, ISBN 978-0-521-80230-7, MR 2581536
  4. ^ 코카이 & 크레어(2004), 페이지 65–67.
  5. ^ 코카이 & 크레어(2004), 페이지 67–69.
  6. ^ Oxley, J. G. (2006), Matroid Theory, Oxford Graduate Texts in Mathematics, vol. 3, Oxford University Press, p. 141, ISBN 978-0-19-920250-8.
  7. ^ Bollobás, Béla (1998), Modern Graph Theory, Graduate Texts in Mathematics, vol. 184, Springer, p. 350, ISBN 978-0-387-98488-9; Mehlhorn, Kurt (1999), LEDA: A Platform for Combinatorial and Geometric Computing, Cambridge University Press, p. 260, ISBN 978-0-521-56329-1.
  8. ^ Cameron, Peter J. (1994), Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, p. 163, ISBN 978-0-521-45761-3.
  9. ^ Gross, Jonathan L.; Yellen, Jay (2005), Graph Theory and Its Applications (2nd ed.), CRC Press, p. 168, ISBN 978-1-58488-505-4; Bondy, J. A.; Murty, U. S. R. (2008), Graph Theory, Graduate Texts in Mathematics, vol. 244, Springer, p. 578, ISBN 978-1-84628-970-5.
  10. ^ Aigner, Martin; Ziegler, Günter M. (1998), Proofs from THE BOOK, Springer-Verlag, pp. 141–146.
  11. ^ Hartsfield, Nora; Ringel, Gerhard (2003), Pearls in Graph Theory: A Comprehensive Introduction, Courier Dover Publications, p. 100, ISBN 978-0-486-43232-8.
  12. ^ Harary, Frank; Hayes, John P.; Wu, Horng-Jyh (1988), "A survey of the theory of hypercube graphs", Computers & Mathematics with Applications, 15 (4): 277–289, doi:10.1016/0898-1221(88)90213-1, hdl:2027.42/27522, MR 0949280.
  13. ^ Kocay, William; Kreher, Donald L. (2004), "5.8 The matrix-tree theorem", Graphs, Algorithms, and Optimization, Discrete Mathematics and Its Applications, CRC Press, pp. 111–116, ISBN 978-0-203-48905-5.
  14. ^ 코케이&크레어(2004), 페이지 109.
  15. ^ 볼로바스(1998), 페이지 351.
  16. ^ 골드버그, LA, Jerrum, M.(2008년),"그 투떼 polynomial의 Inapproximability", 정보 및 계산, 206개의(7):908–929, arXiv:cs/0605140, doi:10.1016/j.ic.2008.04.003. 재거, F.;Vertigan, D.L.;웨일스, D.J.A(1990년),"존스와 투떼 다항식의 계산 복잡도에", 수학적 저자들은 캠브리지 Philosophi.Cal은 협회에 108:35–53, doi:10.1017/S0305004100068936.
  17. ^ Kozen, Dexter (1992), The Design and Analysis of Algorithms, Monographs in Computer Science, Springer, p. 19, ISBN 978-0-387-97687-7.
  18. ^ de Fraysseix, Hubert; Rosenstiehl, Pierre (1982), "A depth-first-search characterization of planarity", Graph theory (Cambridge, 1981), Ann. Discrete Math., vol. 13, Amsterdam: North-Holland, pp. 75–80, MR 0671906.
  19. ^ Reif, John H. (1985), "Depth-first search is inherently sequential", Information Processing Letters, 20 (5): 229–234, doi:10.1016/0020-0190(85)90024-9, MR 0801987.
  20. ^ Gallager, R.G.;Humblet, P.A.;Spira, P.M.(1983년),"minimum-weight 신장 트리에 대한 분산된 알고리즘", 프로그래밍 언어 및 제도에 대한, 5(1):66–77, doi:10.1145/357195.357200, Gazit, 히렐(1991년),"그래프에서 연결이 완료된 요소들을 찾는 데에 최적 임의적인 병렬 알고리즘", SIAM 저널 컴퓨팅, 20일에 ACMTransactions이.(6):1046–1067, doi:10.1137/0220066, MR1135748;베이더, 데이비드 A., 민족 해방 전선, Guojing(2005년),"대칭 multiprocessors에 대한 빠른 평행의 신장 트리 알고리즘(SMPs)"(PDF)면 필기장 평행과 분산의 65(9):994–1006, doi:10.1016/j.jpdc.2005.03.011.
  21. ^ a b Eppstein, David (1999), "Spanning trees and spanners" (PDF), in Sack, J.-R.; Urrutia, J. (eds.), Handbook of Computational Geometry, Elsevier, pp. 425–461.
  22. ^ Wu, Bang Ye; Chao, Kun-Mao (2004), Spanning Trees and Optimization Problems, CRC Press, ISBN 1-58488-436-3.
  23. ^ Wilson, David Bruce (1996), "Generating random spanning trees more quickly than the cover time", Proceedings of the Twenty-eighth Annual ACM Symposium on the Theory of Computing (STOC 1996), pp. 296–303, doi:10.1145/237814.237880, MR 1427525.
  24. ^ McDiarmid, Colin; Johnson, Theodore; Stone, Harold S. (1997), "On finding a minimum spanning tree in a network with random weights" (PDF), Random Structures & Algorithms, 10 (1–2): 187–204, doi:10.1002/(SICI)1098-2418(199701/03)10:1/2<187::AID-RSA10>3.3.CO;2-Y, MR 1611522.
  25. ^ Gabow, Harold N.; Myers, Eugene W. (1978), "Finding all spanning trees of directed and undirected graphs", SIAM Journal on Computing, 7 (3): 280–287, doi:10.1137/0207024, MR 0495152
  26. ^ a b Serre, Jean-Pierre (2003), Trees, Springer Monographs in Mathematics, Springer, p. 23.
  27. ^ Soukup, Lajos (2008), "Infinite combinatorics: from finite to infinite", Horizons of combinatorics, Bolyai Soc. Math. Stud., vol. 17, Berlin: Springer, pp. 189–213, doi:10.1007/978-3-540-77200-2_10, MR 2432534. 특히 정리 2.1, 페이지 192–193을 참조하라.
  28. ^ Levine, Lionel (2011). "Sandpile groups and spanning trees of directed line graphs". Journal of Combinatorial Theory, Series A. 118 (2): 350–364. arXiv:0906.2809. doi:10.1016/j.jcta.2010.04.001. ISSN 0097-3165.