트레모 나무

Trémaux tree

그래프 이론에서 비방향 그래프 G의 트레모 트리는 그 정점 중 하나에 뿌리를 둔 G의 스패닝 트리로, G의 인접한 정점 두 개가 모두 나무의 조상과 후손으로 서로 연관되어 있다는 속성을 가지고 있다.모든 깊이 우선 탐색 나무와 모든 해밀턴 길은 트레모 나무다.트레모 트리는 미로를 해결하기 위한 전략으로 깊이 우선 탐색의 형태를 사용했던 19세기 프랑스 작가 찰스 피에르 트레모(Charles Pierre Témaux)의 이름을 딴 것이다.[1][2]특히 무한 그래프의 맥락에서 그들은 보통 신장 나무라고도 불려왔다.[3]

유한 그래프에서, 깊이 우선 검색 자체는 본질적으로 순차적이지만, 트레모 트리는 복잡도 등급 RNC에서 무작위화된 병렬 알고리즘에 의해 구성될 수 있다.그래프의 트리 깊이를 정의하고 그래프가 평면 그래프인지 여부를 테스트하기 위한 왼쪽-오른쪽 평면도 검사의 일부로 사용할 수 있다.단색 2차 그래프 논리에서의 트레모 트리의 특성화를 통해 Courcelle의 정리를 이용한 경계가 있는 트리 폭의 그래프에 대해 방향을 포함하는 그래프 속성을 효율적으로 인식할 수 있다.

무한하게 연결된 모든 그래프에 트리모 트리가 있는 것은 아니며, 그래프가 있는 그래프는 그들의 금지된 미성년자들로 특징지어질 수 있다.Tremaux 트리는 무한 형태의 깊이 우선 검색이 그래프의 모든 꼭지점을 탐색하는 데 성공하지 못할 경우에도 정점이 셀 수 없이 많은 연결된 모든 그래프에 존재한다.무한 그래프에서, 트레모 트리는 그래프의 각 끝에 대해 정확히 하나의 무한 경로를 가져야 하며, 트레모 트리의 존재는 각 끝의 무한점에 점을 추가함으로써 형성된 위상학적 보완이 미터법 공간인 그래프를 특징짓는다.

예

아래 그래프에서 가장자리가 1–3, 2–3, 3–4인 트리는 꼭지점 1 또는 꼭지점 2에 뿌리를 내릴 때 트레모 나무로, 그래프의 모든 가장자리는 (이러한 루트의 선택에 대해) 선조-후대 쌍을 연결하는 가장자리 1–2를 제외한 트리에 속한다.

Undirected graph.svg

그러나 꼭지점 3이나 꼭지점 4에 같은 나무를 뿌리치면 트레모 나무가 아닌 뿌리 나무가 생성되는데, 이 뿌리 1과 2는 더 이상 서로의 조상과 후예가 아니기 때문이다.

유한 그래프에서

존재

모든 한정된 연결되지 않은 그래프에는 적어도 하나의 트레모 트리가 있다.깊이 우선 검색을 수행하고 발견된 초기 정점에 각 정점(검색 시작 정점 제외)을 연결하면 이러한 트리를 구성할 수 있다.이런 방식으로 조성된 트리는 깊이 우선 탐색 트리로 알려져 있다.uv가 그래프에서 임의의 가장자리이고, u가 검색으로 도달하는 두 정점 중 가장 이른 경우, v는 깊이 첫 번째 검색 트리에서 u에서 하강하는 하위 트리에 속해야 한다. 왜냐하면 검색이 하위 트리의 다른 정점 중 하나에서 이 하위 트리를 탐색하는 동안 반드시 v를 발견하기 때문이다.직접 당신으로부터모든 유한트레모 트리는 깊이 우선 검색 트리로 생성될 수 있다:T가 유한 그래프의 트레모 트리이고, 깊이 우선 검색이 다른 정점을 탐색하기 전에 각 꼭지점 T의 어린이를 탐색한다면, 그것은 반드시 깊이 우선 검색 트리로서 T를 생성하게 될 것이다.

병렬구축

컴퓨터 과학의 미해결 문제:

트레모 트리를 만들기 위한 결정론적 병렬 NC 알고리즘이 있는가?

(컴퓨터 과학에서 더 풀리지 않은 문제)

순차적 깊이 우선 검색 알고리즘에 의해 발견될 트리모(Tremaux) 트리를 찾는 것이 P-complete로, 각 꼭지점의 이웃이 자신의 정체성에 의해 순서대로 검색된다.[4]그럼에도 불구하고 무작위화된 병렬 알고리즘에 의해 다른 트레모 트리를 찾을 수 있어 트레모 트리의 건설이 복잡도 등급 RNC에 속함을 알 수 있다.알고리즘은 0-1 가중치 그래프에서 최소 가중치 만점 일치를 찾기 위한 또 다른 랜덤화 병렬 알고리즘을 기반으로 한다.[5]1997년 현재, Tremaux 트리 건설이 복잡도 등급 NC에서 결정론적 병렬 알고리즘에 의해 수행될 수 있을지는 여전히 알려지지 않았다.[6]만약 NC에서 성냥을 찾을 수 있다면, 트레모 나무도 마찬가지일 것이다.[5]

논리식

뿌리 꼭지점 r을 선택한 가장자리의 집합 T가 트레모 트리를 형성하고, 그래프의 단색 2차 순서 논리학에서, 보다 구체적으로 정점과 가장자리 집합 모두에 대해 정량화가 가능한 MSO라는2 이 논리학의 형태로 표현될 수 있다.이 속성은 다음과 같은 속성의 결합으로 표현할 수 있다.

  • 그래프는 T의 가장자리로 연결되어 있다.이것은 그래프 정점의 비어 있지 않은 모든 적절한 부분 집합에 대해 주어진 부분 집합에 정확히 하나의 끝점이 있는 T에 가장자리가 있다는 문장으로 논리적으로 표현될 수 있다.
  • T는 반복적이다.이는 각 꼭지점이 C의 0 또는 2개의 가장자리로 충돌하는 T의 비어 있지 않은 부분집합 C가 존재하지 않는다는 문장으로 논리적으로 표현될 수 있다.
  • T에 없는 모든 에지는 T에 있는 정점의 조상-후속 쌍을 연결한다.e의 두 끝점이 모두 T의 경로에 속할 때 이는 사실이다.모든 에지 e에 대해 정확히 두 개의 꼭지점(그 중 r)이 P의 단일 에지에 발생하도록 T의 부분 집합 P가 존재하고, e의 양쪽 끝점이 적어도 P의 한쪽 에지에 발생하도록 논리적으로 표현할 수 있다.

일단 이런 방식으로 트레모 트리가 식별되면, 조상 끝점에서 후손 끝점까지의 방향이 있는 가장자리 집합을 지정함으로써 주어진 그래프의 방향을 단차적인 2차 논리에서도 설명할 수 있다.이 세트 외부의 나머지 가장자리는 다른 방향으로 향해야 한다.이 기법은 방향을 포함하는 그래프 속성을 단차순차 로직으로 지정할 수 있게 하여, 이러한 속성을 쿠르셀의 정리를 이용하여 경계 트리폭의 그래프에서 효율적으로 시험할 수 있게 한다.[7]

관련 속성

만약 그래프가 해밀턴 경로를 가지고 있다면, 그 경로(그 끝점 중 하나에 뿌리째 뽑힌)도 트레모 나무다.모든 Tremaux 트리가 이러한 형태를 갖는 비방향 그래프는 사이클 그래프, 전체 그래프, 균형 잡힌 완전 양분 그래프들이다.[8]

트레모 나무는 나무 깊이의 개념과 밀접한 관련이 있다.그래프 G의 트리 깊이는 가장 작은 숫자 d로 정의할 수 있는데, 이는 깊이 d의 트레모 트리 T가 있는 그래프 H의 서브그래프로 G가 포함될 수 있다.경계 트리 깊이는 그래프 제품군에서 해당 제품군 내 그래프의 마이너로서 발생할 수 없는 경로의 존재와 동일하다.그래프의 많은 하드 연산 문제에는 입력된 트리의 깊이에 의해 매개변수화되었을 때 고정 매개변수를 추적할 수 있는 알고리즘이 있다.[9]

트레모 나무는 또한 주어진 그래프가 평면인지 여부를 테스트하기 위한 프레이섹스-로센스티엘 평면성 기준에서 중요한 역할을 한다.이 기준에 따르면 G의 특정 트레모 트리 T에 대해 나머지 가장자리를 트리 왼쪽이나 오른쪽에 일관성 있게 배치할 수 있는 경우 동일한 배치의 가장자리가 서로 교차하지 못하도록 하는 제약조건에 따라 그래프 G가 평면이다.[10]

무한 그래프에서

존재

모든 무한 그래프가 정상적인 스패닝 트리를 가지고 있는 것은 아니다.예를 들어, 정점 집합에 대한 완전한 그래프에는 정점이 없다: 완전한 그래프의 정규 스패닝 트리는 경로일 수 있지만, 경로는 카운트 가능한 정점 수만 가지고 있다.그러나 정점 집합의 카운트 가능한 모든 그래프에는 정규 스패닝 트리가 있다.[3]

계수 가능한 그래프에서도 깊이 우선 검색은 결국 전체 그래프 탐사에 성공하지 못할 수 있으며,[3] 모든 정규 스패닝 트리가 깊이 우선 검색에 의해 생성될 수 있는 것은 아니다: 깊이 우선 검색 트리가 되려면 카운트 가능한 일반 스패닝 트리는 무한 경로 하나 또는 무한히 많은 자식(둘 다 아님)이 있는 하나의 노드만 가져야 한다.

미성년자

무한 그래프 G에 정규 스패닝 트리가 있으면 연결된 모든 그래프에서 G 단위가 된다.이로부터 정상적인 신장 트리를 갖는 그래프는 금지된 미성년자에 의한 특성을 가지고 있다.금지된 미성년자의 두 종류 중 하나는 양분율의 한 쪽을 셀 수 있고, 다른 한 쪽은 셀 수 없으며, 모든 정점에는 무한한 정도가 있는 양분율 그래프로 구성되어 있다.금지된 다른 등급의 미성년자들은 아론자진 나무에서 파생된 특정한 그래프로 구성되어 있다.[11]

이 특성화의 세부사항은 수학을 공식화하는 데 사용되는 설정-이론적 공리화의 선택에 달려 있다.특히 마틴의 공리가 참이고 연속적인 가설이 거짓인 집합 이론 모델에서, 이 특성화에서 초당적 그래프의 등급은 금지된 단일 소수로 대체될 수 있다.단, 연속체 가설이 참인 모형의 경우, 이 세분류는 부차 순서에서 서로 비교할 수 없는 그래프를 포함한다.[12]

종료 및 측정 가능성

정상적인 스패닝 트리는 또한 무한궤도의 등가 등급인 무한궤도의 끝부분과 직감적으로 같은 방향으로 무한궤도로 가는 것과 밀접한 관련이 있다.그래프에 정규 스패닝 트리가 있으면 이 트리는 그래프 끝마다 하나의 무한 경로를 가져야 한다.[13]

무한 그래프를 사용하면 그래프 자체를 단순 복합체로 보고 그래프의 각 끝에 무한에 점을 추가함으로써 위상학적 공간을 형성할 수 있다.이 위상에서는 정점 집합을 폐쇄 집합의 카운트 가능한 조합으로 분해할 수 있는 경우에만 그래프가 정규 스패닝 트리를 가진다.또한 이 위상학적 공간은 그래프에 정규 스패닝 트리가 있는 경우에만 메트릭 공간으로 나타낼 수 있다.[13]

참조

  1. ^ Even, Shimon (2011), Graph Algorithms (2nd ed.), Cambridge University Press, pp. 46–48, ISBN 978-0-521-73653-4.
  2. ^ Sedgewick, Robert (2002), Algorithms in C++: Graph Algorithms (3rd ed.), Pearson Education, pp. 149–157, ISBN 978-0-201-36118-6.
  3. ^ a b c 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, ISBN 978-3-540-77199-9, MR 2432534. 특히 정리 3 페이지 193을 참조하라.
  4. ^ 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.
  5. ^ a b Aggarwal, A.; Anderson, R. J. (1988), "A random NC algorithm for depth first search", Combinatorica, 8 (1): 1–12, doi:10.1007/BF02122548, MR 0951989.
  6. ^ Karger, David R.; Motwani, Rajeev (1997), "An NC algorithm for minimum cuts", SIAM Journal on Computing, 26 (1): 255–272, doi:10.1137/S0097539794273083, MR 1431256.
  7. ^ Courcelle, Bruno (1996), "On the expression of graph properties in some fragments of monadic second-order logic" (PDF), in Immerman, Neil; Kolaitis, Phokion G. (eds.), Proc. Descr. Complex. Finite Models, DIMACS, vol. 31, Amer. Math. Soc., pp. 33–62, MR 1451381.
  8. ^ Chartrand, Gary; Kronk, Hudson V. (1968), "Randomly traceable graphs", SIAM Journal on Applied Mathematics, 16 (4): 696–700, doi:10.1137/0116056, MR 0234852.
  9. ^ Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), "Chapter 6. Bounded height trees and tree-depth", Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics, vol. 28, Heidelberg: Springer, pp. 115–144, doi:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, MR 2920058.
  10. ^ 드 Fraysseix, 휴버트, Rosenstiehl, 피에르(1982년),"평평한 정도의 depth-first-search 특성화", 그래프 이론(캠브리지, 1981년), 앤.이산 수학입니다., 13, 암스테르담:vol..North-Holland, 니코틴산. 75–80, MR0671906, 드 Fraysseix, 휴버트, Ossona 드 멘데스, 파트리스;Rosenstiehl, 피에르(2006년),"Trémaux 나무와 평평한", 국제 저널 컴퓨터 과학의 기초, 17(5):1017–1029, arXiv:math/0610935, doi:10.1142/S0129054106004248, MR2270949.
  11. ^ Diestel, Reinhard; Leader, Imre (2001), "Normal spanning trees, Aronszajn trees and excluded minors" (PDF), Journal of the London Mathematical Society, Second Series, 63 (1): 16–32, doi:10.1112/S0024610700001708, MR 1801714.
  12. ^ Bowler, Nathan; Geschke, Stefan; Pitz, Max (2016), Minimal obstructions for normal spanning trees, arXiv:1609.01042, Bibcode:2016arXiv160901042B
  13. ^ a b Diestel, Reinhard (2006), "End spaces and spanning trees", Journal of Combinatorial Theory, Series B, 96 (6): 846–854, doi:10.1016/j.jctb.2006.02.010, MR 2274079.