그래프 배색

그래프 이론에서 그래프 색칠(graph coloring)은 그래프 라벨링의 특별한 경우로, 전통적으로 "color"라고 불리는 레이블을 특정 제약 조건에 따라 그래프의 요소에 할당하는 것입니다.가장 간단한 형태로, 그래프의 꼭짓점을 색칠하는 방법으로, 두 개의 인접한 꼭짓점이 같은 색이 되지 않도록 합니다. 이를 꼭짓점 색칠이라고 합니다.마찬가지로, 모서리 색상은 인접한 두 모서리가 동일한 색상을 갖지 않도록 각 모서리에 색상을 할당하고, 평면 그래프의 면 색상은 경계를 공유하는 두 면이 동일한 색상을 갖지 않도록 각 면 또는 영역에 색상을 할당합니다.

다른 색칠 문제가 꼭짓점 색칠 인스턴스로 변환될 수 있기 때문에, 꼭짓점 색칠은 종종 그래프 색칠 문제를 도입하는 데 사용됩니다.예를 들어, 그래프의 모서리 색상은 선 그래프의 꼭지점 색상이고, 평면 그래프의 얼굴 색상은 듀얼의 꼭지점 색상입니다.그러나, 꼭짓점이 아닌 착색 문제는 종종 그대로 진술되고 연구됩니다.이것은 부분적으로 교육학적이고 부분적으로는 가장자리 색칠의 경우와 같이 일부 문제가 정점이 아닌 형태로 가장 잘 연구되기 때문입니다.

색을 사용하는 관습은 각각의 얼굴이 문자 그대로 색을 칠하는 지도의 나라들을 색칠하는 것에서 유래합니다.이는 평면에 내장된 그래프의 면에 색상을 입히는 것으로 일반화되었습니다.평면 이중성에 의해 꼭짓점에 색을 입히게 되고, 이 형태로 모든 그래프에 일반화됩니다.수학 및 컴퓨터 표현에서 처음 몇 개의 양 또는 음이 아닌 정수를 "색"으로 사용하는 것이 일반적입니다.일반적으로 유한 집합을 "색상 집합"으로 사용할 수 있습니다.색상 문제의 본질은 색상의 개수에 따라 달라지지만 색상이 무엇인지에 따라 달라지지는 않습니다.

그래프 색칠은 이론적인 문제뿐만 아니라 많은 실용적인 응용들을 즐깁니다.고전적인 유형의 문제 외에도 그래프, 색상이 할당되는 방식, 또는 색상 자체에 대해서도 다양한 제한을 설정할 수 있습니다.그것은 심지어 인기 있는 숫자 퍼즐 스도쿠의 형태로 일반 대중들에게 인기를 얻고 있습니다.그래프 색칠은 여전히 매우 활발한 연구 분야입니다.

참고: 이 글에서 사용하는 많은 용어는 그래프 이론 용어집에 정의되어 있습니다.

역사

그래프 색칠에 대한 첫 번째 결과는 지도의 색칠 형태의 평면 그래프를 거의 독점적으로 다룹니다.프랜시스 거스리는 영국의 여러 주의 지도를 색칠하려고 시도하면서 4가지 색이 지도를 색칠하기에 충분하다고 가정하여, 같은 경계를 공유하는 어떤 지역도 같은 색을 받지 못한다고 언급했습니다.거스리의 형은 유니버시티 칼리지의 수학 선생님 아우구스투스 드 모건에게 이 문제를 전달했고, 그는 1852년 윌리엄 해밀턴에게 보낸 편지에서 이 문제를 언급했습니다.아서 케일리는 1879년 런던 수학회의 회의에서 이 문제를 제기했습니다.같은 해 알프레드 켐페는 결과를 확립했다고 주장하는 논문을 발표했고 10년 동안 4가지 색 문제가 해결되었다고 여겨졌습니다.그의 업적으로 켐페는 왕립학회의 회원으로 선출되었고 후에 런던 수학 학회의 회장으로 선출되었습니다.^[1]

1890년 퍼시 존 히우드는 켐페의 주장이 틀렸다고 지적했습니다.그러나 그 논문에서 그는 켐페의 아이디어를 사용하여 모든 평면 지도는 5가지 색 이하로 색칠될 수 있다고 말하면서 5가지 색 정리를 증명했습니다.그 다음 세기에, 케네스 아펠과 볼프강 하켄에 의해 마침내 4가지 색 정리가 증명될 때까지, 방대한 양의 작업이 이루어졌고 이론들이 개발되어 4가지 색 정리가 마침내 1976년에 증명되었습니다.그 증거는 Heawood와 Kempe의 생각으로 되돌아갔고, 그 동안의 전개를 대체로 무시했습니다.^[2]4색 정리의 증명은 100년 된 문제의 해결과는 별개로 최초의 주요 컴퓨터 지원 증거라는 점에서 주목할 만합니다.

1912년 조지 데이비드 버크호프는 채색 문제를 연구하기 위해 색다항식을 도입했고, 이는 대수 그래프 이론에서 중요한 불변량인 투테에 의해 투테 다항식으로 일반화되었습니다.켐페는 1879년에 이미 평면이 아닌 일반적인 경우에 관심을 끌었고,^[3] 20세기 초에 더 높은 차수의 표면에 대한 평면 그래프 채색의 일반화에 대한 많은 결과들이 뒤따랐습니다.

1960년 클로드 베르게는 그래프 색칠에 대한 또 다른 추측인 강력한 완벽한 그래프 추측을 공식화했는데, 원래 섀넌이 도입한 그래프의 제로 오류 용량이라고 불리는 정보 이론적 개념에 의해 동기부여되었습니다.이 추측은 2002년 추드노브스키, 로버트슨, 시모어, 토마스에 의해 유명한 강력한 완벽한 그래프 정리로 확립되기 전까지 40년 동안 풀리지 않은 채로 남아 있었습니다.

그래프 색칠은 1970년대 초부터 알고리즘 문제로 연구되어 왔습니다. 색수 문제(아래 참조)는 1972년부터 Karp의 21개 NP-완전 문제 중 하나이며, 거의 동시에 역추적과 자이코프(1949)의 삭제-수축 재발을 기반으로 다양한 지수 시간 알고리즘이 개발되었습니다.그래프 색칠의 주요 응용 중 하나인 컴파일러에서의 레지스터 할당은 1981년에 도입되었습니다.

정의 및 용어

꼭지점 배색

아무런 조건 없이 사용할 경우 그래프의 색상은 거의 항상 적절한 정점 색상, 즉 동일한 가장자리를 공유하는 두 정점이 동일한 색상을 갖지 않도록 그래프의 정점에 색상을 표시하는 것을 말합니다.루프가 있는 정점(즉, 연결이 직접 다시 연결됨)은 결코 제대로 채색될 수 없기 때문에, 이 맥락의 그래프는 루프가 없는 것으로 이해됩니다.

꼭짓점 레이블에 색상을 사용하는 용어는 지도 색상으로 돌아갑니다.빨간색과 파란색 같은 라벨은 색상 수가 적을 때만 사용되며, 일반적으로 라벨은 정수 {1, 2, 3, …}에서 추출됩니다.

기껏해야 k개의 색을 사용하는 색을 (적절한) k개의 색이라고 합니다.그래프 G를 색칠하는 데 필요한 가장 적은 수의 색을 색수라고 하며, 종종 χ(G)로 표시합니다.χ(G)는 그래프의 오일러 특성을 나타내기 위해 사용되기 때문에 때때로 γ(G)가 사용됩니다.(적절한) k-컬러링을 할당할 수 있는 그래프는 k-컬러링이 가능하며, 색수가 정확히 k이면 k-컬러링이 가능합니다.동일한 색에 할당된 정점의 부분 집합을 색상 클래스라고 하며, 이러한 클래스는 모두 독립적인 집합을 형성합니다.따라서 k-coloring은 k개의 독립적인 집합으로 이루어진 정점 집합의 분할과 같고 k-partite와 k-colorable이라는 용어는 동일한 의미를 갖습니다.

색다항식

색다항식은 주어진 수의 색상 중 일부를 사용하여 그래프를 색칠할 수 있는 방법의 수를 계산합니다.예를 들어, 세 가지 색상을 사용하여 인접 이미지의 그래프를 12가지 방식으로 색칠할 수 있습니다.단 두 가지 색상으로는 전혀 색칠할 수 없습니다.4가지 색상을 사용하면 24 + 4 ⋅12 = 72가지 방식으로 색상을 지정할 수 있습니다. 4가지 색상을 모두 사용하면 4가지 색상이 있습니다! = 24가지 유효 색상(4가지 vertex 그래프에 4가지 색상을 할당할 때마다 적절한 색상이 지정됨). 4가지 색상 중 3가지 색상을 선택할 때마다 12가지 유효한 3가지 색상이 지정됩니다.예제의 그래프에서 유효한 색상 수에 대한 표는 다음과 같이 시작합니다.

사용가능 색상	1	2	3	4	…
착색횟수	0	0	12	72	…

색다항식은 G의 t색의 수를 세는 함수 P(G,t)입니다. 이름에서 알 수 있듯이 주어진 G에 대해 함수는 실제로 다항식 int입니다.예제 그래프의 경우 P(G,t) = t(t – 1)(t – 2)이고 실제로 P(G,4) = 72입니다.

색다항식은 색수보다 G의 색도에 대한 더 많은 정보를 포함합니다.실제로 χ는 색다항식 χ(G) = min{k : P(G,k) > 0}의 0이 아닌 가장 작은 양의 정수입니다.

특정 그래프에 대한 색다항식

삼각형3 K	t(t – 1)(t – 2)
완전그래프 Kn	t(t – 1)(t – 2) … (t – (n – 1))
정점이 n개인 트리	t(t – 1)n – 1
사이클 다n	(t – 1)n + (-1)n(t – 1)
페테르센 그래프	t(t – 1)(t – 2)(t7 – 12t6 + 67t5 – 230t4 + 529t3 – 814t2 + 775t – 352)

테두리 배색

그래프의 모서리 색상은 모서리의 적절한 색상으로, 꼭짓점이 같은 색의 두 모서리에 입사하지 않도록 모서리에 색상을 할당하는 것을 의미합니다.k개의 색을 갖는 에지 컬러링을 k-edge-coloring이라고 하며, 에지 세트를 k개의 매칭으로 분할하는 문제와 같습니다.그래프 G의 가장자리 색칠에 필요한 가장 적은 수의 색은 색지수, 즉 가장자리 색수 χ'(G)입니다.Tait 컬러링은 입방체 그래프의 3개의 가장자리 컬러링입니다.4색 정리는 모든 평면 입방정교 없는 그래프가 Tait 색을 허용한다는 주장과 같습니다.

전체 배색

전체 색칠은 그래프의 꼭짓점과 가장자리에 있는 색칠의 한 종류입니다.아무런 조건 없이 사용할 경우, 인접한 꼭짓점, 인접한 꼭짓점, 가장자리 및 끝-끝점이 동일한 색으로 할당되지 않는다는 점에서 토탈 컬러링은 항상 적절한 것으로 가정됩니다.그래프 G의 전체 색수 χ″(G)는 G의 전체 색에 필요한 가장 적은 색입니다.

라벨이 부착되지 않은 착색

그래프의 레이블이 없는 색상은 그래프의 오토모피즘 그룹의 작용에 따른 색상의 궤도입니다.색상은 레이블이 지정된 상태로 유지되며, 레이블이 지정되지 않은 그래프입니다.주어진 유한 색상 집합에서 그래프의 레이블이 지정되지 않은 색상의 수를 세는 색다항식의 유사체가 있습니다.

만약 우리가 ${\displaystyle {}^{}}$ ${\$에서 정점 위의 그래프의 색칠을 벡터로 해석한다면$,$ 오토모피즘의 작용은 색칠 벡터의 계수들의 순열입니다.

특성.

색수의 상한

서로 다른 꼭짓점에 고유한 색을 할당하면 항상 적절한 색이 생성되므로

${\displaystyle 1\leq \chi(G)\leq n.}$

1색으로 표시할 수 있는 그래프는 무연 그래프뿐입니다.n개의 정점의 완전한 그래프 ${\displaystyle {Kn}_{}}$ ${\displaystyle K_{n}}$에는 χ${\displaystyle ({Kn}_{}}$ = n ${\displaystyle \chi (K_{n$})= $n}$개의 색상이 필요합니다.최적 색상에서는 모든 색상 클래스 쌍 사이에 그래프의 가장자리 중 하나 이상이 있어야 합니다.

${\displaystyle \chi(G)(\chi(G)-1)\leq 2m.}$

일반적으로 F ${\displaystyle {\mathcal {F}}$의 패밀리 $F$는 χ ${\displaystyle \chi}$ - $F$ ${\displaystyle$ {F$}$의 그래프 $G$ ${\displaystyle G}$을(를) $최대$ c (${\displaystyle }$ω ${\displaystyle (G}$ ${\$$mathcal {$F}) {\$displaystyle c(\omega(G))}$ 색상으로 색칠할 수 있도록 일부 $함수$ c$${\$displaystyle c}$가 있는 경우 경계가 있음, 이 function은 $c$ (${\displaystyle }$ω${\displaystyle }$( ${\displaystyle G}$)${\displaystyle }$= ω${\displaystyle }$( ${\displaystyle G}$) ${\displaystyle$c$(\omega ($G)) =\$omega (G )}$ 입니다$.$

2색 그래프는 정확히 나무와 숲을 포함한 이분 그래프입니다.4색 정리에 의해, 모든 평면 그래프는 4색이 될 수 있습니다.

그리디 컬러링은 모든 그래프가 최대 정점 도보다 하나의 색을 더 많이 칠할 수 있다는 것을 보여줍니다.

${\displaystyle \chi (G)\leq \Delta (G)+1.}$

완전한 그래프는 χ${\displaystyle }$(${\displaystyle G)}$ = ${\displaystyle n}$ ${\displaystyle \chi (G$)=$n}$이고 δ (${\displaystyle G)}$= n${\displaystyle }$- ${\displaystyle 1}$ ${\displaystyle \Delta ($G)=$n-1}$이고$$홀수 주기는 χ${\displaystyle }$(${\displaystyle G)}$ = ${\displaystyle 3}$ ${\displaystyle \chi ($G)= $3}$이고 δ ${\displaystyle (G)}$ = 2 ${\displaystyle \Delta ($G)= $2}$이므로$$이러한 그래프의 경우 이 경계가 가장 적합합니다.다른 모든 경우에는 경계가 약간 개선될 수 있습니다. 브룩스 정리는^[4] 다음과 같이 말합니다.

브룩스의 정리: G가 완전한 그래프 또는 홀수 사이클이 아닌 한 연결된 단순 그래프 G에 대한 χ ${\displaystyle (}$G${\displaystyle )}$ ${\displaystyle \le }$ δ (${\displaystyle G)}$ ${\displaystyle \chi (G)\leq \Delta (G)}.$

색수의 하한선

몇 년 동안 채도 한계에 대한 몇 가지 하한이 발견되었습니다.

G가 k 크기의 클라이크를 포함하는 경우 해당 클라이크를 색칠하려면 적어도 k개의 색상이 필요합니다. 즉, 색수는 적어도 클라이크 번호입니다.

${\displaystyle \chi(G)\geq \omega(G)}$

완벽한 그래프의 경우 이 경계가 엄격합니다.클리크를 찾는 것은 클리크 문제로 알려져 있습니다.

호프만의 한계:${\displaystyle W}$ ${\displaystyle W}$을(를${\displaystyle )}$${\displaystyle {}_{}}$${\displaystyle \mathrm{Wi},}$$$j$$= 0 {\$displaystyle$$$$W_{i$$,$$}$=0이 되도록 실제 대칭 행렬이라고 하자$.$$$χ W (${\displaystyle {}_{}}$G${\displaystyle }$) = ${\displaystyle 1}$ -${\displaystyle }$λ ${\displaystyle \frac{{최대값}_{}}{}}$(${\displaystyle \frac{W)}{}}$ λ ${\displaystyle \frac{{최소값}_{}}{}}$ ${\displaystyle \frac{{}_{}W}{}}$) ${\displaystyle \chi _{W}(G$) = 1 - ${\tfrac {\$lambda $_{\max }(W)}$ {\$lambda _{\min$}($W)},$ λ ${\displaystyle {최소값}_{}{}_{}{}_{}W)}$ ${\di$}을${\displaystyle (}$를${\displaystyle )}$ 정의합니다$.$$\$$displaystyle$ \$lambda$ _${\max}(W),\lambda$ _${\min$}(W$)}$는$$W ${\displaystyle$ W$}$의 가장 크고 작은 고유값입니다.$$위와 $같이$ W ${\displaystyle$ W}로$$$χ$ H ($G_{}{}_{}$$=$ 최대 $\underset{}{W}$ $χ$ W ($G_{})$ ${\textstyle \chi$ _${H}(G$) $=$\$max$ _${W}\chi$ _${W}(G)$를 정의합니다$.$그러면:

${\displaystyle \chi _{H}(G)\leq \chi(G)}$

벡터 색수:$W$ ${\displaystyle W}$을$($를${\displaystyle )}$${\displaystyle {Wi}_{}}$$,$ j ${\displaystyle {}_{}}$ -${\displaystyle 1}$ ${\displaystyle \frac{\mathrm{k}}{}}$- 1 ${\displaystyle W_{i,$${\displaystyle j}$$}\leq$ -${\tfrac {1}{$$k-1$$}}}$인 양의 준정의 행렬이라 하자.$$χ V (${\displaystyle {}_{}G)}$ ${\displaystyle \chi _{V}(G)$를 이러한 $행렬$ W ${\displaystyle W}$가 존재하는 최소 k로 정의합니다.그리고나서

${\displaystyle \chi _{V}(G)\leq \chi(G)}$

로바즈 번호:상보 그래프의 로바즈 수는 색수의 하한이기도 합니다.

${\displaystyle \vartheta({\bar {G}})\leq \chi(G)}$

분수 색수:그래프의 부분 색수는 색수의 하한이기도 합니다.

${\displaystyle \chi _{f}(G)\leq \chi(G)}$

이러한 한계는 다음과 같이 정렬됩니다.

${\displaystyle \chi _{H}(G)\leq \chi _{V}(G)\leq \vartheta ({\bar {G}})\leq \chi _{f}(G)\leq \chi (G)}$

색수가 높은 그래프

클라이크가 큰 그래프는 색수가 높지만, 그 반대입니다.그뢰츠쉬 그래프는 삼각형이 없는 4색 그래프의 예이며, 그 예는 마이시엘스키안으로 일반화될 수 있습니다.

정리 (윌리엄 T. Tutte 1947,^[5] Alexander Zykov 1949, Jan Mycielski 1955):색수가 임의로 높은 삼각형이 없는 그래프가 있습니다.

이를 증명하기 위해, Mycielski와 Zykov는 각각 임의로 큰 색수를 가진 유도적으로 정의된 삼각형이 없는 그래프 계열의 구성을 제공했습니다.^[6]$Burling{\displaystyle {\mathbb{}}^{}}$(1965)^[7]은 R3 {\$displaystyle \mathbb {R}^{3}$에 축 정렬 상자를 구성하였는데, 이 상자의$$ 교차 그래프는 삼각형이 없고 임의로 많은 색을 적절하게 색칠해야 합니다.이 그래프 계열을 벌링 그래프(Burling graphs)라고 합니다.Pawlik et al. (2014)이 제공한 평면에서 삼각형이 없는 선분군의 구성에 동일한 종류의 그래프가 사용됩니다.^[8]교차 그래프의 색수도 임의로 크다는 것을 보여줍니다.따라서 R ${\displaystyle {}^{}}$ ${\displaystyle \mathbb {R} ^{3}$의 축 정렬 상자와 R ${\displaystyle {}^{}}$ ${\displaystyle \mathbb {R} ^{2}$의 선분은 χ로 바운드되지 않습니다.

브룩스의 정리에 따르면, 색수가 높은 그래프는 최대 도수가 높아야 합니다.그러나 색상이 완전히 국소적인 현상은 아닙니다. 둘레가 높은 그래프는 모든 주기가 길지만 색수가 2일 필요는 없기 때문에 국소적으로 나무처럼 보입니다.

정리(Erd ő):임의로 높은 둘레와 색수의 그래프가 있습니다.^[9]

색지수 경계

G의 가장자리 색은 L${\displaystyle (G)}$ ${\displaystyle L(G)}$ 선 그래프의 꼭짓점 색이며$,$ 그 반대도 마찬가지입니다.따라서,

${\displaystyle \chi '(G)=\chi (L(G))}$

가장자리 색도는 그래프의 최대 δ${\displaystyle (G)}$ ${\displaystyle \Delta(G)}$와 강한 관계가 있습니다$.$ 같은 꼭짓점에 입사하는 모든 가장자리는 고유의 색을 필요로 하기 때문에, 우리는

${\displaystyle \chi'(G)\geq \Delta(G)}$

게다가.

K ő$니그$ 정리: G가 이분이면 χ ' (${\displaystyle G){}^{}}$= δ ${\displaystyle (G)}$ ${\displaystyle \chi'$ $($G)=\$Delta (G)}$

일반적으로, 이 관계는 브룩스 정리가 정점 색을 제공하는 것보다 훨씬 더 강합니다.

비징의 정리:최대 δ δ$${\$displaystyle \Delta}$의 그래프에서 가장자리 색수가 δ ${\displaystyle \Delta$$\}$ 또는 .${\displaystyle }$+ ${\displaystyle 1}$ ${\displaystyle \Delta +1}$입니다.

기타속성

그래프가 가장 긴 경로의 길이가 최대 k인 비순환 방향을 갖는 경우에만 k색을 가질 수 있습니다. 이것이 갈라이-하세-로이-비타버 정리(Neset řil & Ossona de Mendez 2012)입니다.

평면 그래프의 경우 정점 색상은 기본적으로 nowhere-zero 흐름에 대해 이중으로 지정됩니다.

무한 그래프에 대해서는 알려진 바가 거의 없습니다.다음은 무한 그래프 색상에 대한 몇 가지 결과 중 두 가지입니다.

• 무한 그래프 G의 모든 유한 부분 그래프가 k색이면 선택 공리의 가정 하에서 G도 마찬가지입니다.이것은 드 브루인 & 에르드 ő스(1951)의 드 브루인-에르드 ő스 정리입니다.
• 그래프가 모든 n개의 ≥n에 대해 완전한 n색을 허용하면 무한한 완전한 색을 허용합니다(Fawcett 1978).

미해결 문제

위에서 언급한 바와 같이, ω ${\displaystyle (G)}$ ${\displaystyle \le }$ χ ${\displaystyle (G)}$ ${\displaystyle \le }$ δ ${\displaystyle (G)}$+ ${\displaystyle 1.}$ ${\displaystyle \omega (G)\leq \chi (G)\leq \Delta (G)$ + $1.}$ 1998년 리드의 추측은 그 값이 본질적으로 하한에 더 가깝다는 것입니다. χ${\displaystyle }$(${\displaystyle G)}$ ${\displaystyle \le }$ ⌈ ω${\displaystyle \frac{}{}}$(${\displaystyle \frac{G)}{}}$ +${\displaystyle \frac{}{}}$δ${\displaystyle \frac{}{}}$(${\displaystyle \frac{G)}{}}$+ ${\displaystyle \frac{1}{}}$.${\displaystyle \frac{}{}}$ ⌉${\displaystyle .}$ ${\displaystyle \chi (G)\leq \left\lceil {\frac {\omega ($G) $+\Delta (G)$ + $1}{2}\right\rceil .}$

단위 거리가 있는 경우 두 점이 인접한 평면의 색수는 알 수 없지만 5, 6, 7 중 하나입니다.색수 그래프와 관련된 다른 열린 문제로는 색수 k인 모든 그래프가 k개의 꼭짓점에 완전한 그래프를 부로 갖는다는 하드위거 추측, 각 쌍에 공통적으로 최대 하나의 꼭짓점을 갖는 완전한 그래프의 색수 조합을 경계하는 에르드 ő스-파버-로바즈 추측,그리고 K-변색 그래프 중에서 완전한 그래프는 교차 수가 가장 작은 그래프라는 앨버트슨 추측.

Birkhoff와 Lewis가 4색 정리를 공격할 때, 그들은 평면 그래프 G의 $경우{\displaystyle \mathrm{다항식}}$ P${\displaystyle }$($,$ t) {\$displaystyle P (G,t)}$가 영역 [4${\displaystyle ,}$∞$)$ {\$displaystyle [$4,\infty $)}$에 0이 없다고 추측했습니다$.$ 비록 이러한 색 다항식이 영역 $[{\displaystyle 5,}$${\displaystyle \mathrm{\infty )}}$ ${\displaystyle [5,\infty )}$ 그리고 $P$ ${\displaystyle (G,}$ ${\displaystyle 4)}$${\displaystyle \mathrm{\ne }}$ ${\displaystyle 0}$ ${\displaystyle P(G,4)\neq$ 0$},$그들의 추측은 여전히 풀리지 않았습니다.또한 동일한 색다항식을 갖는 그래프를 특성화하고 어떤 다항식이 색다항식인지 결정하는 것은 해결되지 않은 문제로 남아 있습니다.

알고리즘

그래프 배색
결정
이름.	그래프 색칠하기, 꼭지점 색칠하기, k-coloring
인풋	정점이 n개인 그래프 G.정수 k
산출량	G는 k개의 색상으로 적절한 꼭지점 색상을 인정합니까?
러닝타임	O(2 nn)[10]
복잡성	NP-완전
감점:	3-만족도
개리-존슨	GT4
최적화
이름.	색수
인풋	정점이 n개인 그래프 G.
산출량	χ(G)
복잡성	NP하드
근사치	O(n(log n)(−3log log n))2
범접불가	P = NP가 아니면 O(n)
카운팅문제
이름.	색다항식
인풋	정점이 n개인 그래프 G.정수 k
산출량	G의 고유 k-색소의 수 P(G,k)
러닝타임	O(2 nn)
복잡성	#P완성형
근사치	제한 사례에 대한 FPRAS
범접불가	P = NP가 아니면 PTAS 없음

다항식 시간

그래프가 2가지 색상으로 채색될 수 있는지 여부를 결정하는 것은 그래프가 이분형인지 여부를 결정하는 것과 같으며, 따라서 너비 우선 검색 또는 깊이 우선 검색을 사용하여 선형 시간으로 계산할 수 있습니다.보다 일반적으로, 완벽한 그래프의 색과 색은 반무한 프로그래밍을 사용하여 다항 시간 내에 계산될 수 있습니다.색다항식에 대한 닫힌 공식은 숲, 코드 그래프, 사이클, 휠 및 사다리와 같은 많은 종류의 그래프에 대해 알려져 있으므로 다항 시간 내에 평가할 수 있습니다.

그래프가 평면이고 분기 너비가 낮은 경우(또는 평면이 아니지만 분기 분해가 알려진 경우), 동적 프로그래밍을 사용하여 다항 시간 내에 해결할 수 있습니다.일반적으로 필요한 시간은 그래프 크기에서는 다항식이지만 분기 너비에서는 지수형입니다.

정확한 알고리즘

k-컬러에 대한 브런트-포스 검색은 k개의 색상을 n개의 정점에 할당한$$ ${\displaystyle {kn}^{}}${\$displaystyle$k^{$n}$개의 각 할당을 고려하고 합법적인지 여부를 검사합니다.색수와 색다항식을 계산하기 위해 이 절차는 모든 $k$ = ${\displaystyle 1,}$ ${\displaystyle \dots ,}$ ${\displaystyle \mathrm{n}}$- ${\displaystyle 1}$ ${\displaystyle$k = 1$,\ldots,n-1}$에 대해 사용되며$,$ 가장 작은 입력 그래프를 제외한 모든 그래프에 대해 비현실적입니다.

동적 프로그래밍과 최대 독립 집합의 수에 대한 경계를 사용하여 시간과 공간 O ${\displaystyle ({\mathrm{.}}^{4423}}$ n${\displaystyle {}^{}}$) ${\displaystyle$ O $(2.4423^{n})}$에서 k-색소성을 결정할 수 있습니다$.$^[11] 포함-배제의 원리와 빠른 제타 변환을 위한 예이츠의 알고리즘을 사용하면,k-채색성은 임의의 k에 대해$$^{[10][12][13][14]} 시간 $O{\displaystyle ({}^{})}$ ${\displaystyle O(2^{n}n)}$에서 결정할 수 있습니다.더 빠른 알고리즘은 3색 및 4색성으로 알려져 있으며, $시간{\displaystyle }$ O$($^[16]${\displaystyle {\mathrm{.}}^{3289}}$ n${\displaystyle {}^{}}$ ${\displaystyle O(1.3289^{n})}$와^[15] $O{\displaystyle ({.7272}^{}}$ ${\displaystyle n^{}}$ ${\displaystyle O(1.7272^{n})}$에서 각각 결정할 수 있습니다.기하급수적으로 더 빠른 알고리즘은 5색 및 6색도뿐만 아니라 희소 그래프를 포함한 제한된 그래프 계열에 대해서도 알려져 있습니다.^[17]

수축

그래프 G의 수축$$ $G{\displaystyle }$/ ${\displaystyle u}$ v ${\displaystyle G/uv}$는 정점 u와 v를 식별하고 그들 사이의 간선을 제거한 그래프입니다.원래 u 또는 v에 입사된 나머지 에지는 이제 식별(즉, 새로운 융합 노드 uv)에 입사됩니다.이 작업은 그래프 색상 분석에 중요한 역할을 합니다.

색수는 재발 관계를 만족합니다.

${\displaystyle \chi(G)={\text{min}}\{\chi(G+uv),\chi(G/uv)\}$

zykov(1949)로 인해, u와 v는 인접하지 않은 정점이고, $G{\displaystyle }$+ u ${\displaystyle v}$ ${\displaystyle G+uv}$는 가장자리 uv가 추가된 그래프입니다.여러 알고리즘은 이러한 재발을 평가하는 것에 기반을 두고 있으며, 결과 계산 트리를 Zykov 트리라고 부르기도 합니다.실행 시간은 정점 u와 v를 선택하기 위한 휴리스틱에 기초합니다.

색다항식은 다음과 같은 반복 관계를 만족합니다.

${\displaystyle P(G-uv,k)=P(G/uv,k)+P(G,k)}$

여기서 u와 v는 인접한 정점이고, G -${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle G-uv}$는 가장자리 uv가 제거된 그래프입니다.${\displaystyle P}$ (${\displaystyle G}$ -${\displaystyle \mathrm{uv},}$ k${\displaystyle }$) ${\displaystyle P(G-uv,k)}$은(는) 그래프의 가능한 적절한 색상의 수를 나타냅니다$$. 여기서 정점의 색상은 같거나 다를 수 있습니다.그러면 두 개의 다른 그래프에서 적절한 색상이 나타납니다.예를 들어, 정점 u와 v가 서로 다른 색을 가지면 u와 v가 인접한 그래프를 고려할 수 있습니다.만약 당신과 v가 같은 색상이라면, 당신과 v가 계약된 그래프를 고려하는 것이 좋을 것 같습니다.투테는 어떤 다른 그래프 특성이 이 재발을 만족시켰는지에 대한 호기심으로 인해 색다항식인 투테 다항식의 이변량 일반화를 발견하게 되었습니다.

이러한 표현은 삭제-수축 알고리즘이라고 하는 재귀적 절차를 발생시키며, 이는 그래프 색칠을 위한 많은 알고리즘의 기초를 형성합니다.실행 시간은 피보나치 수와 동일한 재발 관계를 만족하므로 최악의 경우 ${\displaystyle {}^{}}$은$$(${\displaystyle {1\frac{}{}}^{}}$+ ${\displaystyle {\frac{52}{})}^{}}$ n${\displaystyle {}^{}}$+ ${\displaystyle m^{}}$ = ${\displaystyle O({.6180}^{}}$ ${\displaystyle n^{}}$+ ${\displaystyle m^{}}$ ${\displaystyle \left$({\$tfrac {1+{\sqrt {5}}{2}}\right)$ n개의 정점과 m개의 간선에 대해 {$n+m$}=$O(1.6180^{n+m})}.$분석은 입력 그래프의 신장 트리 수$$ t (${\displaystyle G)}$ ${\displaystyle$t ($G)}$의 다항식 인자 내로 개선할 수 있습니다.^[19]실제로 분기 및 경계 전략과 그래프 동형 거부는 일부 재귀적 호출을 피하기 위해 사용됩니다.실행 시간은 정점 쌍을 선택하는 데 사용되는 휴리스틱에 따라 달라집니다.

그리디 컬러링

greedy ${\displaystyle {알고리즘}_{}}$은 v1$${\$displaystyle v_{$1}},…,$$ ${\displaystyle {vn}_{}}${\$displaystyle v_{$n}}의 정점을 vi {\$displaystyle$$$v_${i$$}$에 할당합니다$$. ${\displaystyle {v1\mathrm{}}_{}}${\$displaystyle v_{1},…,$ ${\displaystyle {vi-1}_{}}${\$displaystyle v_{i-1}$ 중 ${\displaystyle {vi}_{}}$ ${\$displaystyle v_{i-1}의$$이웃에서 사용하지 않는 최소 색상을$$ ${\displaystyle {vi}_{}}$ ${\${i-1}에 할당하여 필요한 경우 새 색상을 추가합니다$.$선택한 순서에 따라 색상의 품질이 달라집니다.최적의 χ${\displaystyle (G)}$ ${\displaystyle \chi(G)}$가지 색상으로 그리디 컬러를 유도하는 순서가 있습니다.반면 그리디 컬러링은 임의로 나쁠 수 있습니다. 예를 들어 n개 정점의 크라운 그래프는 2색일 수 있지만 $n{\displaystyle /2\mathrm{}}$ ${\displaystyle n/2}$개의 컬러로$$ 그리디 컬러링을 유도하는 순서를 가집니다.

초달 그래프의 경우, 구간 그래프 및 무관심 그래프와 같은 특수한 초달 그래프의 경우 그래프에 대한 완벽한 제거 순서의 역순으로 정점 순서를 선택하여 다항 시간 내에 최적의 색상을 찾는 데 그리디 컬러링 알고리즘을 사용할 수 있습니다.완전 순서 그래프는 이 속성을 일반화하지만 이러한 그래프의 완벽한 순서를 찾기는 어렵습니다.

정점이 정도에 따라 순서가 정해지면 결과적인 그리디 색상은 ${\displaystyle {}_{}}$ ${\displaystyle \{d({xi}_{}}$+ ${\displaystyle 1,}$ ${\displaystyle i\}}$ ${\displaystyle {\text{max}}_{i}{\text{min}}\{d(x_{i})$ + $1,i\}$가지$$ 색상을 최대로 사용하며 그래프의 최대 정도보다 한 가지 더 많이 사용합니다.이러한 휴리스틱은 때때로 웨일스-파월 알고리즘이라고 불립니다.^[20]Brélaz로 인한 또 다른 휴리스틱은 알고리즘이 진행되는 동안 동적으로 순서를 설정하고 가장 많은 다른 색에 인접한 꼭지점을 선택합니다.^[21]다른 많은 그래프 색칠 휴리스틱은 정점 순서의 특정 정적 또는 동적 전략에 대한 탐욕스러운 색칠에 유사하게 기반을 두고 있으며, 이러한 알고리즘은 때때로 순차 색칠 알고리즘이라고 합니다.

이 수를 최대화하기 위해 선택된 정점 순서를 사용하여 그리디 알고리즘에 의해 얻을 수 있는 최대(최악) 색상 수를 그래프의 그룬디 수라고 합니다.

휴리스틱 알고리즘

그래프 착색에 대해 잘 알려진 두 가지 다항식 시간 휴리스틱은 DSatur와 RLF(Recursive Large First) 알고리즘입니다.

그리디 컬러링 알고리즘과 유사하게 DSatur는 그래프의 꼭짓점을 차례로 컬러링하여 필요할 때 이전에 사용하지 않았던 컬러를 확장합니다.새 정점에 색을 입히면 알고리즘은 나머지 색을 입히지 않은 정점 중 이웃에서 가장 많은 색을 입히고 다음에 이 정점에 색을 입히는 것을 결정합니다.이것은 주어진 꼭지점의 포화 정도로 정의됩니다.

재귀적으로 가장 큰 첫 번째 알고리즘은 한 번에 하나씩 색상 클래스를 구성하여 다른 방식으로 작동합니다.특수한 휴리스틱 규칙을 사용하여 그래프에서 최대 독립 정점 집합을 식별함으로써 이 작업을 수행합니다.그런 다음 이 정점들을 같은 색으로 할당하고 그래프에서 제거합니다.이러한 작업은 정점이 남지 않을 때까지 나머지 부분 그래프에서 반복됩니다.

DSatur의 최악의 복잡도는 $O{\displaystyle ({}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ ${\displaystyle O(n^{2})}$이며$,$ 여기서 $n{\displaystyle }$ ${\displaystyle n}$은 그래프의 정점 개수입니다.이 알고리즘은 $이진$ 힙을 사용하여 O${\displaystyle ((n}$+ m${\displaystyle }$) ${\displaystyle \log }$ ⁡ n${\displaystyle }$) ${\displaystyle O((n+m)\log n)}($여기서 $m$ ${\displaystyle m}$은 그래프의 가장자리 수입니다.이렇게 하면 희소 그래프로 훨씬 더 빠른 실행이 발생합니다.$RLF$의 전체 복잡도는 DSatur at O${\displaystyle (\mathrm{mn})}$ ${\displaystyle {\mathcal {O}}(mn)$보다 약간 높습니다$.$^[22]

DSatur와 RLF는 이분 그래프, 사이클 그래프 및 휠 그래프에 정확합니다.^[22]

병렬 및 분산 알고리즘

분산 알고리즘 분야에서 그래프 색칠은 대칭 깨짐의 문제와 밀접한 관련이 있습니다.현재의 최첨단 무작위 알고리듬은 결정론적 알고리듬보다 충분히 큰 최대 δ에 대해 더 빠릅니다.가장 빠른 무작위 알고리즘은 Schneider 등의 다중 시험 기법을 사용합니다.^[23]

대칭 그래프에서 결정론적 분산 알고리즘은 적절한 정점 색상을 찾을 수 없습니다.대칭성을 깨기 위해서는 몇 가지 보조 정보가 필요합니다.표준 가정은 처음에는 각 노드가 예를 들어 {1, 2, ..., n} 집합에서 고유한 식별자를 갖는다는 것입니다. 달리 말하면, 우리는 n-coloring이 주어졌다고 가정합니다.문제는 색상 수를 n에서 δ + 1로 줄이는 것입니다.예를 들어 δ + 1 대신 O( δ) 색상을 많이 사용할수록 통신 라운드가 적게 필요합니다.

(δ + 1)-컬러링을 위한 그리디 알고리즘의 간단한 분산 버전은 최악의 경우 θ θ(n) 통신 라운드가 필요합니다. -정보는 네트워크의 한 쪽에서 다른 쪽으로 전파되어야 할 수도 있습니다.

가장 간단한 흥미로운 경우는 n-사이클입니다.Richard Cole과 Uzi Vishkin은^[24] 하나의 동기 통신 단계에서 색상 수를 n에서 O(log n)로 줄이는 분산 알고리즘이 있음을 보여줍니다.동일한 절차를 반복함으로써, O(log*n) 통신 단계에서 (우리가 고유한 노드 식별자를 가지고 있다고 가정할 때) n 사이클의 3-컬러를 얻을 수 있습니다.

로그를 반복한 함수 로그*는 매우 느리게 증가하는 함수로 "거의 일정"합니다.따라서 Cole과 Vishkin에 의한 결과는 3-coloring n-cycle에 대한 일정한 시간 분산 알고리즘이 있는지에 대한 문제를 제기했습니다.Linial(1992)은 이것이 불가능하다는 것을 보여주었습니다. 어떤 결정론적 분산 알고리즘도 n-cycle에서 n-color를 3-color로 줄이기 위해 ω(log*n) 통신 단계가 필요합니다.

Cole과 Vishkin의 기법은 임의의 경계 차수 그래프에서도 적용될 수 있습니다. 실행 시간은 poly( δ) + O(log*n)입니다.이 기법은 Schneider 등에 의해 단위 디스크 그래프로 확장되었습니다.^[26]작은 δ을 위한 (δ + 1)-컬러링에 대한 가장 빠른 결정론적 알고리즘은 레오니드 바렌보임, 마이클 엘킨 및 파비안 쿤에 기인합니다.Barenboim et al. 의 알고리즘은 O(시간 O( δ) + log*(n)/2에 실행되며, 이는 상수 인자 1/2이 Linial의 하한으로 인해 개선될 수 없기 때문에 n에 대해 최적입니다.Panconesi & Srinivasan (1996$)$은 네트워크 분해를 사용하여 2 $O$ ${\displaystyle {시간}^{}}$에 δ+1 색상을 계산합니다 ${\displaystyle {(\sqrt{\mathrm{로그}}}^{}}$ ⁡ ${\displaystyle {\sqrt{n}}^{}}$ )${\displaystyle 2^{O\left({\sqrt {\log n}}\right)}.$

분산 모델에서도 엣지 컬러링의 문제가 연구되었습니다.Panconesi & Rizzi(2001)는 이 모델에서 O(2 δ + log*n)에서 (2 δ - 1)-컬러링 시간을 달성합니다.Linial(1992)로 인한 분산 정점 착색의 하한은 분산 에지 착색 문제에도 적용됩니다.

분산형 알고리즘

분산형 알고리즘은 메시지 전달이 허용되지 않는 것이며(로컬 메시지 전달이 이루어지는 분산형 알고리즘과 달리), 적절한 색상이 존재할 경우 그래프에 색상을 입히는 효율적인 분산형 알고리즘이 존재합니다.이들은 꼭짓점이 이웃 중 하나가 꼭짓점과 동일한 색을 사용하고 있는지, 즉 로컬 충돌이 존재하는지를 감지할 수 있다고 가정합니다.이것은 많은 응용 분야에서 가벼운 가정입니다. 예를 들어, 무선 채널 할당의 경우, 스테이션이 (예를 들어, SINR을 측정함으로써) 다른 간섭 송신기들이 동일한 채널을 사용하고 있는지 여부를 감지할 수 있다고 가정하는 것이 일반적으로 타당합니다.이 감지 정보는 학습 오토마타를 기반으로 한 알고리즘이 확률 1로 적절한 그래프 색상을 찾을 수 있도록 하기에 충분합니다.^[28]

계산 복잡도

그래프 색칠은 계산적으로 어렵습니다.주어진 그래프가 주어진 k에 대하여 k ∈ {0,1,2}인 경우를 제외하고 k 색을 허용하는지를 결정하는 것은 NP-완전이며, 특히 색수를 계산하는 것은 NP-hard입니다.3색 문제는 4개의 정규 평면 그래프에서도 NP-완전한 상태를 유지합니다.^[30]그러나 최대 차수가 3 이하인 그래프에서 브룩스의 정리는 3색 문제가 선형 시간으로 해결될 수 있음을 의미합니다.또한, k > 3 일 때마다 4 색 정리에 의해 평면 그래프의 k 색이 존재하며, 다항 시간에 이러한 색을 찾는 것이 가능합니다.

가장 잘 알려진 근사 알고리즘은 색수의 인자 O(n(log log n)(²log n))⁻³ 내에서 최대 크기의 색을 계산합니다.^[31]모든 ε > 0에 대하여, n 내의 색수를 근사하는 것은 NP-hard입니다.

5가지 색상으로 3가지 색상의 그래프, 7가지 색상으로 4가지 색상의 그래프, k${\displaystyle }$≥${\displaystyle \genfrac{}{}{0ex}{}{\mathrm{5가지}}{}}$ 색상으로 ${\displaystyle \mathrm{1가지}}$ ${\displaystyle {\binom {k}{\lfloor k/2\rfloor }-1}$가지 색상의 그래프를 색칠하는 것도 NP-hard입니다.

색다항식의 계수를 계산하는 것은 #P-hard입니다.실제로 χ(${\displaystyle G,}$ k${\displaystyle )}$ ${\displaystyle \chi(G,k)}$의 값을 계산해도 k = 1 및 k = 2를 제외한 임의의 유리점 k에서 #P-하드입니다.NP = RP가 아닌 한 k ≥ 1.5의 유리한 점에서 색다항식을 평가하기 위한 FPRAS는 없습니다.

에지 컬러링의 경우, Vizing의 결과의 증명은 최대 δ+1 색상을 사용하는 알고리즘을 제공합니다.그러나 에지 색수에 대한 두 후보 값 사이의 결정은 NP-완전입니다.^[37]근사 알고리즘 측면에서, Vizing의 알고리즘은 에지 색수가 4/3 이내로 근사될 수 있음을 보여주며, 경도 결과는 P = NP가 아니면 0보다 큰 ε에 대해 (4/3 - ε)-algorithm가 존재하지 않음을 보여줍니다.이는 두 논문 모두 그 개념을 명시적으로 사용하지는 않지만 근사 알고리즘 문헌에서 가장 오래된 결과 중 하나입니다.^[38]

적용들

스케쥴링

여러 가지 스케줄링 문제에 대한 정점 색상 모델.^[39]가장 깨끗한 형태로, 주어진 작업 집합을 타임 슬롯에 할당해야 하며, 각 작업에는 이러한 슬롯이 하나씩 필요합니다.작업은 순서에 상관없이 예약할 수 있지만, 공유 리소스에 둘 다 의존하기 때문에 같은 시간대에 할당되지 않을 수 있다는 점에서 작업 쌍이 충돌할 수 있습니다.해당 그래프에는 모든 작업에 대한 정점과 충돌하는 모든 작업 쌍에 대한 가장자리가 포함됩니다.그래프의 색수는 충돌 없이 모든 작업을 완료할 수 있는 최적의 시간인 최소 메이크스팬입니다.

스케줄링 문제에 대한 세부 정보는 그래프의 구조를 정의합니다.예를 들어 항공기를 비행에 할당할 때 결과 충돌 그래프는 구간 그래프이므로 색칠 문제를 효율적으로 해결할 수 있습니다.무선국에 대한 대역폭 할당에서 결과적인 충돌 그래프는 단위 디스크 그래프이므로 색상 문제는 3-대략적입니다.

레지스터배정

컴파일러는 한 컴퓨터 언어를 다른 컴퓨터 언어로 번역하는 컴퓨터 프로그램입니다.결과 코드의 실행 시간을 향상시키기 위해 컴파일러 최적화 기법 중 하나는 레지스터 할당(register allocation)이며, 여기서 컴파일된 프로그램의 가장 자주 사용되는 값은 빠른 프로세서 레지스터에 저장됩니다.이상적으로 값은 레지스터에 할당되어 레지스터를 사용할 때 모두 레지스터에 상주할 수 있습니다.

이 문제에 대한 교과서적 접근은 그래프 색칠 문제로 모델링하는 것입니다.^[40]컴파일러는 간섭 그래프를 구성하는데, 여기서 정점은 변수이고 에지는 필요한 경우 두 정점을 연결합니다.그래프를 k개의 색으로 색칠할 수 있다면 동시에 필요한 변수 집합을 최대 k개의 레지스터에 저장할 수 있습니다.

기타 어플리케이션

그래프를 색칠하는 문제는 ^{[citation needed]}패턴 매칭, 스포츠 스케쥴링, 좌석계획 설계, 시험시간표, 택시 스케쥴링, 스도쿠 퍼즐 풀기와 같은 많은 실용적인 부분에서 발생합니다.^[22]

기타착색

램지 이론

부적절한 색상 문제의 중요한 부류는 그래프의 가장자리가 색상에 할당되고 입사 가장자리의 색상에 제한이 없는 램지 이론에서 연구됩니다.간단한 예는 친구와 낯선 사람에 대한 정리인데$,$ 6개의 정점으로 이루어진 $완전$한 그래프인 $K6$ {\displaystyle K_${6}}$의 가장자리의 어떤 색상에도 단색 삼각형이 존재할 것이라는 것입니다. 흔히 6명으로 이루어진 어떤 그룹이든 3명의 서로 모르는 사람이 있거나 3명의 서로 아는 사이가 있다고 말함으로써 설명됩니다.램지 이론은 주어진 구조를 가진 단색 하위 그래프의 존재에 대한 일반적인 조건을 찾으면서 무질서 속에서 규칙성을 추구하기 위한 이 아이디어의 일반화와 관련이 있습니다.

기타착색

서명된 그래프와 게인 그래프에 대해서도 채색을 고려할 수 있습니다.

참고 항목

• 임계 그래프
• 그래프 색칠하기 게임
• 그래프 동형 사상
• 하요스 건설
• 스도쿠의 수학
• 다등분 그래프
• 고유 색상 그래프

메모들

참고문헌

외부 링크

• 고성능 그래프 색칠 알고리즘suite (C++에서 구현) A Graph Coloning 가이드에 사용된 8가지 다른 알고리즘: 알고리즘과 응용(Springer International Publishers, 2015)
• 그래프 컬러링 페이지 by Joseph Culberson (그래프 컬러링 프로그램)
• Jim Andrews and Mike Fellows의 CoLoRaTiOn은 그래프 색칠 퍼즐입니다.
• 그래프 색출 소스 코드에 대한 링크
• Gary Hagard, David J. Pearce 및 Gordon Royle에 의해 Wayback Machine에서 2008-04-16에 보관된 Tutte, Chromatic 및 Flow 다항식을 효율적으로 계산하기 위한 코드
• Jose Antonio Martin H의 웹 앱을 색칠하는 그래프.