나무 깊이

그래프 이론에서, 연결된 비방향 그래프 G의 트리 깊이는 G의 수퍼그래프를 위한 트레모 나무의 최소 높이인 G의 숫자 불변성이다.이 불변성과 그 가까운 친척들은 문헌에서 정점 순위 번호, 순서 색수, 최소 제거 트리 높이 등 많은 다른 이름으로 통했다. 또한 지시된 그래프의 사이클 순위 및 정규 언어의 별 높이와도 밀접한 관련이 있다.^[1]직관적으로 나무 너비 매개변수가 그래프가 나무에서 얼마나 떨어져 있는지 측정하는 경우, 이 매개변수는 그래프가 별에서 얼마나 떨어져 있는지를 측정한다.

정의들

그래프 G의 트리 깊이는 F에서 G의 모든 가장자리가 서로 조상-후속 관계를 갖는 한 쌍의 노드를 연결하는 특성을 가진 포리스트 F의 최소 높이로 정의할 수 있다.^[2]G가 연결되어 있다면 이 숲은 반드시 하나의 나무여야 한다. G의 서브그래프가 될 필요는 없지만, 만약 그렇다면 G를 위한 트레모 나무다.

F에 있는 조상-후대 쌍들의 집합은 사소한 것으로 완벽한 그래프를 형성하고 있으며, F의 높이는 이 그래프에서 가장 큰 클라이크의 크기다.따라서 나무 깊이는 G의 사소한 완벽한 수퍼그래프에서 가장 큰 클라이크의 크기로 정의될 수 있으며, 이는 코드 수퍼그래프에서 가장 큰 클라이크의 크기보다 작은 나무 너비의 정의를 반영한다.^[3]

또 다른 정의는 다음과 같다.

여기서 V는 G의 정점 집합이고 ${\displaystyle {Gi}_{}}$ ${\$는 G의 연결된 구성요소다.^[4]이 정의는 지시된 그래프의 사이클 순위에 대한 정의를 반영하며, 비방향 연결 및 연결 구성요소 대신 강력한 연결성과 강하게 연결된 구성요소를 사용한다.

나무 깊이는 그래프 색상의 형태를 사용하여 정의할 수도 있다.그래프의 중심 색상은 연결된 모든 유도 서브그래프가 정확히 한 번 나타나는 색상을 갖는 속성을 가진 정점의 색이다.그런 다음, 트리 깊이는 주어진 그래프의 중심 색상에 있는 최소 색상 수입니다.F가 나무에서 G의 모든 가장자리가 조상과 후손을 연결하는 속성을 가진 높이 d의 숲이라면, D색을 사용한 G의 중심 색상은 F의 나무 뿌리로부터 각 꼭지점에 거리만큼 색을 입혀 얻을 수 있다.^[5]

마지막으로, 사람들은 이것을 조약돌 놀이의 관점에서, 또는 더 정확히 말하면 경찰과 강도 놀이로 정의할 수 있다.다음 게임을 고려해 보십시오. 방향이 정해지지 않은 그래프에서.두 명의 선수가 있는데, 강도 한 명과 경찰 한 명이다.그 강도는 주어진 그래프의 가장자리를 따라 움직일 수 있는 하나의 조약돌을 가지고 있다.경찰은 자갈을 무제한으로 가지고 있지만, 그녀는 그녀가 사용하는 자갈의 양을 최소화하기를 원한다.경찰은 자갈을 그래프에 놓은 후에 움직일 수 없다.경기는 다음과 같이 진행된다.강도는 자갈을 놓는다.그리고 나서 경찰은 그녀가 새로운 경찰 자갈을 어디에 놓기를 원하는지 발표한다.그러면 강도는 자갈을 가장자리를 따라 움직일 수 있지만, 꽉 막힌 곳을 통해 움직일 수는 없다.경찰 선수가 강도의 조약돌 위에 조약돌을 올려놓으면 게임은 끝난다.주어진 그래프의 나무 깊이는 경찰이 승리를 보장하는 데 필요한 최소한의 조약돌 수입니다.^[6]별 그래프의 경우 두 개의 조약돌이면 충분하다: 조약돌을 중앙 꼭지점에 놓아 강도는 한 팔로 강제한 다음 남은 조약돌을 강도에 놓는 전략이다.정점이$$ $n{\displaystyle }$ ${\displaystyle n}$인 경로에 대해 경찰은 2진수 검색 전략을 사용하며, 이는 최대${\displaystyle }$most ${\displaystyle {\mathrm{로그}}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$⁡${\displaystyle }$(${\displaystyle \mathrm{n}}$+ 1${\displaystyle }$) ${\displaystyle \rceil }$ ${\displaystyle \lceil \log _{$2}($n+1)\rceil$}개의 조약돌이$$ 필요함을 보장한다.

예

전체 그래프의 트리 깊이는 정점의 수와 동일하다.이 경우, 모든 꼭지점 쌍이 조상-후대 관계에 있는 유일한 숲 F는 하나의 경로일 뿐이다.마찬가지로 완전한 양분 그래프 K의_x,y 나무 깊이는 최소(x,y) + 1. 숲 F의 잎에 놓여 있는 노드는 최소(x,y)의 조상이 F에 있어야 한다.이 최소(x,y) + 1 바운드를 달성하는 숲은 이 경로의 하단 정점에 연결된 F의 잎을 형성하면서, 양분보다 큰 쪽의 각 꼭지점에 대한 경로를 형성하여 건설할 수 있다.

정점이 없는 경로의 트리 깊이는 정확히${\displaystyle }$log ${\displaystyle {\mathrm{로그}}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$⁡${\displaystyle }$(${\displaystyle \mathrm{n}}$+ 1${\displaystyle }$) ${\displaystyle \rceil }$ ${\displaystyle \lceil \log _{2}(n+1)\rceil$ $\}\}\}.$ 이 깊이로 경로의 중간점을 F의 근원으로 하고 그 양쪽에 있는 두 개의 작은 경로 내에 반복함으로써 이 경로를 나타내는 F숲을 형성할 수 있다.^[7]

나무의 깊이 및 나무 폭과의 관계

n-vertex 숲은 나무 깊이 O(log n)를 가지고 있다.숲에서는 항상 일정한 수의 정점을 찾을 수 있으며, 그 정점을 제거하면 각각 최대 2n/3 정점을 가진 두 개의 작은 하위 숲으로 분할될 수 있다.이 두 개의 하위 숲 각각을 재귀적으로 분할함으로써, 우리는 나무 깊이에서 로그 상한을 쉽게 도출할 수 있다.그래프의 트리 분해에 적용된 동일한 기법은 n-vertex 그래프 G의 트리 너비가 t이면 G의 트리 깊이가 O(t log n)임을 보여준다.^[8]외부 평면 그래프, 직렬-병렬 그래프, 할린 그래프는 모두 경계 트리 너비를 가지기 때문에 로그 트리 깊이도 모두 가진다.큰 삼엽수와 작은 나무 너비를 가진 전형적인 그래프는 완벽한 이진수 나무와 경로들이다.정확히는 다음과 같은 속성을 가진 상수 C가 있다: 그래프가 최소 $C{\displaystyle }$ k ${\displaystyle 5}$ ${\displaystyle {\mathrm{로그}}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ ${\displaystyle {}^{}}$ k ${\displaystyle Ck^{5}\log ^{2}k}$보다 작은 트리$$ 폭을 가진 경우 높이 k 또는 길이 $2{\displaystyle {\mathrm{}}^{}}$ ${\displaystyle k^{}}$의 경로$({\$를 단수로 사용하는$$ 완벽한 이진 트리를 포함한다.^[9]

다른 방향에서 그래프의 트리 너비는 최대 트리 깊이와 동일하다.보다 정확히 말하면, 나무 너비는 나무 깊이보다 최대 1개 적은 경로 너비에 있다.^[10]

그래프 마이너

그래프 G의 부차는 G의 일부 가장자리를 수축시켜 G의 하위 그래프에서 형성된 또 다른 그래프다.나무 깊이는 미성년자 이하에서 단조롭다: 그래프 G의 모든 마이너스는 나무 깊이가 G 자체의 나무 깊이와 최대 동일하다.^[11]따라서, 로버트슨-시모어 정리, 모든 고정 d에 대해 나무 깊이가 최대 d인 그래프의 집합에는 금지된 미성년자 집합이 한정되어 있다.

C가 그래프 Minor를 취합하여 닫힌 그래프 클래스인 경우, C의 그래프에는 모든 경로 그래프를 포함하지 않는$$ 경우에만 트리 $깊이{\displaystyle }$O(${\displaystyle 1}$) ${\displaystyle$O(1$)$가 있다.^[12]더 정확히 말하면, $최소{\displaystyle {}^{}}$ k ${\displaystyle c^{}}${\$displaystyle$ k$^{c}}$의 모든 그래프에 다음 미성년자(각각 최소 k)가$$ 포함될 정도로 상수 c가 있다.^[9]

• $k{\displaystyle }$ ${\displaystyle \times }$ ${\displaystyle k}$ ${\displaystyle k\put$ k$}$ 격자$$
• 높이 k의 완전한 이진수,
• 순서 ${\displaystyle {2k}^{}}$ ${\$ 2$^{k}}$의 경로$.$

유도 서브그래프

그래프 미성년자 아래에서 잘 동작하는 것뿐만 아니라 나무 깊이는 그래프의 유도 하위그래프 이론과 밀접한 관련이 있다.최대 d(정수 d의 경우)의 나무 깊이를 갖는 그래프 클래스 내에서 유도 하위 그래프로서의 관계는 적절한 준순서를 형성한다.^[13]이 관계가 잘 준주문이라는 증거의 기본 개념은 d에 유도를 사용하는 것이다; 높이 d의 숲은 높이 d - 1의 숲으로 해석될 수 있고(높이-d 숲의 나무뿌리를 삭제하여 형성됨), 히그만의 보조마(lemema)는 이러한 순서가 아른다는 것을 유도 가설과 함께 사용할 수 있다.잘 다듬어진

잘 준순서는 유도 하위 그래프와 관련하여 단조로운 그래프의 성질이 금지된 유도 하위 그래프를 매우 많이 가지고 있으므로, 경계 트리 깊이의 그래프에서 다항 시간 내에 시험할 수 있음을 암시한다.나무 깊이가 최대 d인 그래프도 제한된 유도 하위 그래프를 가지고 있다.^[14]

C가 경계가 있는 그래프의 한 종류인 경우, C의 그래프는 C의 그래프의 유도 하위그래프로 발생할 수 없는 경로 그래프가 있는 경우에만 나무 깊이를 경계했다.^[12]

복잡성

트리 깊이를 계산하는 것은 계산적으로 어렵다: 해당 의사결정 문제는 NP-완전이다.^[15]문제는 초당적 그래프(Bodlaender et al. 1998)뿐만 아니라 화음 그래프에서도 NP-완전하다.^[16]

양의 측면에서 트리 깊이는 순열, 사다리꼴, 원형 아크, 원형 순열 그래프 및 경계 치수의 코콤파빌리티 그래프뿐만 아니라 ^[17]구간 그래프에서 다항식으로 계산할 수 있다.^[18]비방향 트리의 경우 나무 깊이를 선형 시간으로 계산할 수 있다.^[19]

Bodlaender 외 연구진(1995)은 트리 깊이가 항상 그래프의 트리 너비의 로그 계수 내에 있다는 사실에 기초하여 $근사비{\displaystyle }$ ${\displaystyle O}$( (${\displaystyle }$ n${\displaystyle {}^{}}$) ${\displaystyle {2\mathrm{}}^{}}$) ${\displaystyle O((\log n)^{2$의 트리 깊이에 대한 근사 알고리즘을 제공한다.

트리 깊이는 그래프 마이너에서 단조롭기 때문에 고정 매개변수 트랙터블: 시간 ${\displaystyle f}$( d${\displaystyle }$) ${\displaystyle n^{}}$ ${\displaystyle {\mathrm{O}}^{}}$( 1$){\$ f(d$)n^{O(1)}}}$에서 실행되는 트리 깊이를 계산하는 알고리즘이 있다$.$ 여기서 d는 주어진 그래프의 깊이이고 n은 정점 수입니다.따라서 d의 모든 고정 값에 대해 트리 깊이가 최대 d인지 여부를 검정하는 문제는 다항식 시간 내에 해결할 수 있다.구체적으로는, 이 알고리즘의 n에 대한 의존은, 깊이 첫 번째 검색 트리를 계산하고, 이 트리의 깊이가 2보다^d 큰지 시험하는 방법으로, 선형화할 수 있다.그렇다면 그래프의 나무 깊이가 d보다 커 문제가 해결된다.그렇지 않을 경우, 얕은 깊이 첫 번째 검색 트리를 사용하여 경계 너비로 트리 분해를 구성할 수 있으며, 경계 트리 너비의 그래프에 대한 표준 동적 프로그래밍 기법을 사용하여 선형 시간 내에 깊이를 계산할 수 있다.^[20]

또한 트리 깊이가 클 수 있는 그래프의 경우 2보다 약간 작은 상수 c에 대한 시간 O(cⁿ)로 트리 깊이를 정확하게 계산할 수도 있다.^[21]

메모들

참조

• Aspvall, Bengt; Heggernes, Pinar (1994), "Finding Minimum Height Elimination Trees for Interval Graphs in Polynomial Time", BIT, 34 (4): 484–509, doi:10.1007/BF01934264.
• Bodlaender, Hans L.; Deogun, Jitender S.; Jansen, Klaus; Kloks, Ton; Kratsch, Dieter; Müller, Haiko; Tuza, Zsolt (1998), "Rankings of graphs" (PDF), SIAM Journal on Discrete Mathematics, 11 (1): 168–181, doi:10.1137/S0895480195282550
• Bodlaender, Hans L.; Gilbert, John R.; Hafsteinsson, Hjálmtýr; Kloks, Ton (1995), "Approximating treewidth, pathwidth, frontsize, and shortest elimination tree", Journal of Algorithms, 18 (2): 238–255, CiteSeerX 10.1.1.29.7198, doi:10.1006/jagm.1995.1009.
• Deogun, Jitender S.; Kloks, Ton; Kratsch, Dieter; Müller, Haiko (1999), "On the vertex ranking problem for trapezoid, circular-arc and other graphs", Discrete Applied Mathematics, 98: 39–63, doi:10.1016/S0166-218X(99)00179-1.
• Dereniowski, D.; Nadolski, A. (2006), "Vertex rankings of chordal graphs and weighted trees", Information Processing Letters, 98: 96–100, doi:10.1016/j.ipl.2005.12.006.
• Fomin, 표도르 V;Giannopoulou, Archontia C;Pilipczuk, Michał(2013년),"더 빨리 2n보다 tree-depth을 산출하는", Gutin, 그레고리에;Szeider, 스테판(eds.), Parameterized과 엄밀한 계산:8일 국제 심포지엄, IPEC, 2013년 소피아 앙티 폴리스, 프랑스, 9월 4-6,2013년 개정된 선택 기술, 강의 노트 컴퓨터 과학으로, p. 8246 vol.P. 137–149, arXiv:1306.3857, doi:10.1007/978-3-319-03898-8_13.
• Gruber, Hermann; Holzer, Markus (2008), "Finite automata, digraph connectivity, and regular expression size" (PDF), Proc. 35th International Colloquium on Automata, Languages and Programming, Lecture Notes on Computer Science, vol. 5126, Springer-Verlag, pp. 39–50, doi:10.1007/978-3-540-70583-3_4.
• Hunter, Paul (2011), "LIFO-Search on Digraphs: A Searching Game for Cycle-Rank", 18th International Symposium on Fundamentals of Computation Theory, Lecture Notes on Computer Science, vol. 6914, Springer-Verlag, pp. 217–228, arXiv:1103.6019, doi:10.1007/978-3-642-22953-4_19
• Iyer, Ananth V.; Ratliff, H. Donald; Vijayan, Gopalakrishnan (1988), "Optimal node ranking of trees", Information Processing Letters, 28: 225–229, doi:10.1016/0020-0190(88)90194-9.
• Kawarabayashi, Ken-ichi; Rossman, Benjamin (2018), "A Polynomial Excluded-Minor Approximation of Treedepth", Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, pp. 234–246, doi:10.1137/1.9781611975031.17.
• 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.
• Pothen, Alex (1988), The complexity of optimal elimination trees, Tech. Report CS-88-13, Pennsylvania State University.
• Reidl, 펠릭스, Rossmanith, 피터, 산체스 Villaamil, 페르난도, Sikdar, 솜 나트(2014년),"treedepth기 때문에, 더 빠른 매개 변수 알고리즘", Esparza, 하비에르;Fraigniaud, 피에르, Husfeldt, Thore, et 알.(eds.), 자동자, 언어, 프로그래밍:41회 국제 콜로퀴움, ICALP 2014년, 코펜하겐, 덴마크, 7월 8–11, 2014년, 회보, PartYouandI. 강의 노트 컴퓨터 과학으로, 8572,를 대신하여 서명함 vol.. 931–942, arXiv:1401.7540, doi:10.1007/978-3-662-43948-7_77.
• Rossman, Benjamin (2008), "Homomorphism preservation theorems", Journal of the ACM, 55 (3): Article 15, doi:10.1145/1379759.1379763.
• Schäffer, Alejandro A. (1989), "Optimal node ranking of trees in linear time", Information Processing Letters, 33: 91–96, doi:10.1016/0020-0190(89)90161-0, hdl:10338.dmlcz/140723.