하드와이거 수
Hadwiger number
그래프 이론에서, 비방향 그래프 G의 Hadwiger 번호는 G의 가장자리를 수축하여 얻을 수 있는 가장 큰 전체 그래프의 크기다. 동등하게, Hadwiger 번호 h(G)는 전체 그래프k K가 G의 마이너인 가장 큰 숫자 k이며, 가장자리 수축과 정점 및 가장자리 삭제에 의해 G에서 얻은 더 작은 그래프다.하드와이거 번호는 G의[1] 수축 클릭 수 또는 G의 동형성 정도로도 알려져 있다.[2]1943년 하드와이거 추측과 연계해 소개한 우고 하드와이거의 이름을 따온 것으로, 하드와이거의 숫자는 적어도 G의 색수만큼 항상 크다는 내용이다.
하드와이거 숫자가 최대 4개인 그래프는 바그너(1937년)가 특징이다.Hadwiger 번호에 유한한 경계를 가진 그래프는 희박하고 색도 수가 적다.그래프의 Hadwiger 번호를 결정하는 것은 NP-hard이지만 고정 파라미터는 추적 가능하다.
작은 Hadwiger 번호가 있는 그래프
그래프 G는 숲인 경우에만 최대 2개의 Hadwiger 번호를 가지고 있으며, 3Vex 완전 마이너의 경우 G의 사이클을 수축해야만 구성할 수 있다.
그래프에는 트리 너비가 최대 2인 경우에만 최대 3개의 Hadwiger 번호가 있으며, 이는 각각의 이코넥트 구성요소가 직렬-병렬 그래프인 경우에만 해당된다.
그들의 금지된 미성년자들이 평면 그래프를 특징짓는 바그너의 정리는 평면 그래프가 최대 4개의 하드와이거 숫자를 가지고 있음을 암시한다.이 정리를 증명했던 같은 논문에서 바그너(1937년)는 하드와이거 숫자를 가진 그래프를 최대 4개까지 더 정밀하게 특징지었는데, 그것은 평면 그래프를 8베르크스 바그너 그래프와 결합한 클릭-섬 연산에 의해 형성될 수 있는 그래프들이다.
최대 5개의 Hadwiger 번호가 있는 그래프에는 정점 그래프와 연결되지 않은 내장형 그래프가 포함되며, 두 그래프 모두 금지된 미성년자 중 완전한 그래프 K를6 가지고 있다.[3]
스파르시티
정점과 Hadwiger 번호 k를 가진 모든 그래프에는 O(nk √log k) 에지가 있다.이 바운드는 단단하다: 모든 k에 대해 Ω(nk klog k) 에지를 갖는 Hadwiger 번호 k의 그래프가 존재한다.[4]그래프 G에 Hadwiger 번호 k가 있으면 모든 하위 그래프에도 최대 k의 Hadwiger 번호가 있고, G에는 반드시 퇴보 O(k loglog k)가 있어야 한다.따라서 경계 Hadwiger 번호가 있는 그래프는 희박한 그래프다.
컬러링
하드와이거 추측에 의하면 하드와이거 숫자는 적어도 G의 색수만큼 항상 크다고 한다.즉, Hadwiger 번호 k를 가진 모든 그래프에는 최대 k 색상의 그래프 색상이 있어야 한다.사례 k = 4는 평면 그래프 색상에 대한 4가지 색상 정리(이 하드와이거 숫자로 그래프를 특성화한 바그너에 의해)와 동일하며, 추측도 k ≤ 5에 대해 증명되었지만, 더 큰 k 값에 대해서는 입증되지 않은 채로 남아 있다.[5]
퇴보도가 낮기 때문에 해드와이거 번호가 최대 k인 그래프는 O(k √log k) 색상을 이용한 탐욕스러운 컬러링 알고리즘으로 채색할 수 있다.
계산 복잡성
주어진 그래프의 Hadwiger 번호가 적어도 주어진 값 k인지 여부를 시험하는 것은 NP-완전하며,[6] 여기서 Hadwiger 번호를 결정하는 것은 NP-hard이다.그러나 문제는 고정 매개변수 추적가능하다. 그래프 크기에 따라 다항식적으로만 의존하지만 h(G)에서는 기하급수적으로 의존하는 시간 내에 가장 큰 클릭 부전수를 찾는 알고리즘이 있다.[7]또한, 다항식 시간 알고리즘은 가장 큰 전체 서브그래프의 크기에 가장 좋은 다항식 시간 근사치(P ≠ NP로 가정)보다 훨씬 더 정확하게 Hadwiger 숫자의 근사치를 구할 수 있다.[7]
관련개념
그래프 G의 무채색 숫자는 G에서 독립 집합의 계열을 계약함으로써 형성될 수 있는 가장 큰 집단의 크기이다.
무한 그래프의 헤아릴 수 없는 패거리 미성년자는 피신처로 특징지어질 수 있는데, 이것은 특정 추적-피신 게임에 대한 회피 전략을 공식화한다: 만약 하드와이거 숫자가 셀 수 없다면, 그것은 그래프에서 가장 큰 피신처 순서와 같다.[8]
Hadwiger 번호 k가 있는 모든 그래프에는 최대 n2개의O(k log log k) 분류(완전한 하위 그래프)가 있다.[9]
할린(1976년)은 그가 S-기능이라고 부르는 그래프 매개변수의 클래스를 정의하는데, 여기에는 하드와이거 번호가 포함된다.그래프에서 정수에 이르는 이러한 함수는 가장자리가 없는 그래프에서 0이 되어야 하고, 마이너-모노톤이 되어야 하며,[10] 이전의 모든 정점에 인접한 새로운 정점이 추가되었을 때 1이 증가해야 하며, 클라이크 분리기의 양쪽에 있는 두 개의 하위 그래프에서 더 큰 값을 얻어야 한다.그러한 모든 기능 세트는 요소별 최소화와 최대화의 작동 하에서 완전한 격자를 형성한다.이 격자의 하단 원소는 하드와이거 수이고, 상단 원소는 나무 너비다.
메모들
- ^ 볼로바스, 캐틀린 & 에르드스(1980년).
- ^ 할린(1976년).
- ^ 로버트슨, 시모어&토머스(1993b).
- ^ 코스토치카(1984);토마슨(2001년.이러한 표현에서 O와 Ω은 큰 O 표기법을 호출한다.
- ^ 로버트슨, 시모어 & 토마스(1993a).
- ^ 엡스타인(2009년).
- ^ a b 알론, 링가스 & 와를렌(2007)
- ^ 로버트슨, 시모어 & 토마스(1991년).
- ^ 포민, 옴앤틸리코스(2010년).
- ^ 함수 f가 마이너-모노톤인 경우, H가 G의 마이너인 경우 f(H) g f(G)이다.
참조
- Alon, Noga; Lingas, Andrzej; Wahlen, Martin (2007), "Approximating the maximum clique minor and some subgraph homeomorphism problems" (PDF), Theoretical Computer Science, 374 (1–3): 149–158, doi:10.1016/j.tcs.2006.12.021.
- Bollobás, B.; Catlin, P. A.; Erdős, Paul (1980), "Hadwiger's conjecture is true for almost every graph" (PDF), European Journal of Combinatorics, 1: 195–199, doi:10.1016/s0195-6698(80)80001-1.
- Eppstein, David (2009), "Finding large clique minors is hard", Journal of Graph Algorithms and Applications, 13 (2): 197–204, arXiv:0807.0007, doi:10.7155/jgaa.00183.
- Fomin, Fedor V.; Oum, Sang-il; Thilikos, Dimitrios M. (2010), "Rank-width and tree-width of H-minor-free graphs", European Journal of Combinatorics, 31 (7): 1617–1628, arXiv:0910.0079, doi:10.1016/j.ejc.2010.05.003.
- Hadwiger, Hugo (1943), "Über eine Klassifikation der Streckenkomplexe", Vierteljschr. Naturforsch. Ges. Zürich, 88: 133–143.
- Halin, Rudolf (1976), "S-functions for graphs", J. Geometry, 8 (1–2): 171–186, doi:10.1007/BF01917434, MR 0444522.
- Kostochka, A. V. (1984), "Lower bound of the Hadwiger number of graphs by their average degree", Combinatorica, 4 (4): 307–316, doi:10.1007/BF02579141.
- Robertson, Neil; Seymour, Paul; Thomas, Robin (1991), "Excluding infinite minors", Discrete Mathematics, 95 (1–3): 303–319, doi:10.1016/0012-365X(91)90343-Z, MR 1141945.
- Robertson, Neil; Seymour, Paul; Thomas, Robin (1993a), "Hadwiger's conjecture for K6-free graphs" (PDF), Combinatorica, 13 (3): 279–361, doi:10.1007/BF01202354.
- Robertson, Neil; Seymour, P. D.; Thomas, Robin (1993b), "Linkless embeddings of graphs in 3-space", Bulletin of the American Mathematical Society, 28 (1): 84–89, arXiv:math/9301216, doi:10.1090/S0273-0979-1993-00335-5, MR 1164063.
- Thomason, Andrew (2001), "The extremal function for complete minors", Journal of Combinatorial Theory, Series B, 81 (2): 318–338, doi:10.1006/jctb.2000.2013.
- Wagner, K. (1937), "Über eine Eigenschaft der ebenen Komplexe", Math. Ann., 114: 570–590, doi:10.1007/BF01594196.
