색다항식

색채 다항식은 수학의 한 분야인 대수 그래프 이론에서 연구하는 그래프 다항식이다.그것은 그래프 색상의 수를 색상 수의 함수로 세고, 원래 조지 데이비드 비르코프가 4가지 색상의 문제를 연구하기 위해 정의했다.하슬러 휘트니와 W. T. 투테에 의해 투테 다항식(Tutte polyomial)에 일반화되어 통계물리학의 포츠 모델과 연결되었다.

역사

조지 데이비드 비르코프는 4가지 색상 정리를 증명하기 위해 1912년에 색도 다항식을 도입하여 평면 그래프에 대해서만 정의했다.$P{\displaystyle }$( ${\displaystyle G}$, ${\displaystyle k}$) ${\displaystyle P(G,$$)}$이(가) k 색상으로 G의 적절한 색상 수를 나타낸다면$$, 모든 평면 그래프 G에 P( , 4)> ${\displaystyle$P$(G,4)>0}$을(를) 표시하여 4가지 색상 정리를 설정할 수 있다.이런 식으로 그는 다항식의 뿌리를 연구하기 위한 분석과 대수학의 강력한 도구를 결합색소 문제에 적용하기를 희망했다.

하슬러 휘트니는 1932년 비르코프의 다항식을 평면 사례에서 일반 그래프에 일반화했다.1968년, 로널드 C. 어떤 다항식이 일부 그래프의 색다항식인지, 열린 채로 남아 있는 질문을 읽고 색도 등가 그래프의 개념을 소개했다.^[1]오늘날 색채 다항식은 대수 그래프 이론의 중심 개체 중 하나이다.^[2]

정의

그래프 G의 경우, $P{\displaystyle (G}$, k${\displaystyle }$) ${\displaystyle P(G,k)}$이(가) 정점 k-색상의 수를 카운트한다.다른 일반적으로 사용되는 표기법으로는 ${\displaystyle P_{}}$ ${\displaystyle G{}_{}}$( k${\displaystyle }$) ${\displaystyle P_{G}(k)},$${\displaystyle \chi }$ ${\displaystyle G_{}}$( k${\displaystyle }$) ${\displaystyle \chi _{G}(k)$ 또는$$${\displaystyle {\pi }_{}}$ G${\displaystyle {}_{}}$( ${\displaystyle k}$) ${\displaystyle \pi _{G}(k)}}$ 등이 있다$.$어떤 정수 k ≥ 0에서 평가한 P$($$G$ ,${\displaystyle x}$) {\$displaystyle P(G,x)}$이(가) P${\displaystyle (G}$ ${\displaystyle ,}$ k${\displaystyle }$) ${\displaystyle$ P$(G,k)}$과 일치하는 고유한 다항식 $P{\displaystyle (G}$,k)가 있는데$,$ G의 색도 다항식이라고 한다.

예를 들어 3정점에 ${\displaystyle {대한\mathrm{}}_{}}$ 경로$$그래프 P 3 {\$displaystyle$ P_$$${3}$을 k 색으로 색칠하려면 첫 번째 정점에 대한 k 색, 두 번째 정점에 ${\displaystyle \mathrm{대한}}$ $k{\displaystyle }$- 1 ${\displaystyle k-1}$색$$, 마지막으로 세 번째 정점에 대해 다른 $k{\displaystyle }$- ${\displaystyle 1}$ ${\displaysty k-1}$ 색$$ 중 하나를 선택할 수 있다.두 번째 꼭지점부터Therefore, ${\displaystyle P(P_{3},k)=k\cdot (k-1)\cdot (k-1)}$ is the number of k-colorings of ${\displaystyle P_{3}}$. For a variable x (not necessarily integer), we thus have ${\displaystyle P(P_{3},x)=x(x-1)^{2$$}}=x^{3}-2x^{2}+x}$. (색상을 허용하거나 G의 자동화에 의해서만 차이가 나는 색상은 여전히 다른 것으로 계산된다.)

삭제-연락

k-색상 수가 k의 다항식이라는 사실은 삭제-연락재발 또는 근본감소정리라는 재발관계에서 비롯된다.^[3]가장자리 수축에 기반한다. 정점 $u{\displaystyle }$ ${\displaystyle u}$ 및$$ $v{\displaystyle }$ ${\displaystyle v}$ 쌍의 경우 두 정점을 병합하고 그 사이의 가장자리를 제거하여 그래프 $G{\displaystyle /u}$ v ${\displaystyle G/uv}$을(를) 얻는다$$.$u{\displaystyle }$ ${\displaystyle u}$ $및{\displaystyle }$ v$$ ${\displaystyle v}$이(가) $G$에 인접해 있는$$ 경우${\displaystyle G}$ - ${\displaystyle u}$v {\$displaystyle$ $G-uv}$ 에지 $uv}$을(를$)$ 제거하여 얻은 그래프를 표시하십시오$.$그러면 이러한 그래프의 k-색상 수가 다음을 만족한다.

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

마찬가지로 $u{\displaystyle }$ ${\displaystyle u}$ 및 $v{\displaystyle }$ ${\displaystyle v}$이(가) $G$에 인접하지 않고$$ G${\displaystyle }$+ ${\displaystyle u}$ v ${\displaystyle G+uv}$이(가) edge ${\displaystyle u}$ v ${\displaysty uv}$이(가) 추가된$$ 그래프인$$ 경우

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

이는 G의 모든 k-색상이 $u{\displaystyle }$ ${\displaystyle u}$ 및 $v$ ${\displaystyle v$에 다른 색상을 주거나 동일한 색상을 주거나, 동일한 색상을 제공한다는 관측에서 비롯된다.In the first case this gives a (proper) k-coloring of ${\displaystyle G+uv}$, while in the second case it gives a coloring of ${\displaystyle G/uv}$. Conversely, every k-coloring of G can be uniquely obtained from a k-coloring of ${\displaystyle G+uv}$ or ${\displaystyle G/uv}$ (if ${\displaystyle u}$${\displaystyle u}$ 및$$ $v{\displaystyle }$ ${\displaystyle v}$이(가) G)에 인접하지 않음$$

따라서 색도 다항식은 다음과 같이 재귀적으로 정의할 수 있다.

${\displaystyle }$p${\displaystyle (G}$, ${\displaystyle x}$)${\displaystyle }$= ${\displaystyle x^{}}$ n ${\$ P$(G,x)=x^{n}.$

${\displaystyle }$$P$${\displaystyle (G}$, x${\displaystyle }$)${\displaystyle }$= ${\displaystyle P(G}$ -${\displaystyle u}$ v${\displaystyle }$, x${\displaystyle }$)${\displaystyle }$= ${\displaystyle P(G}$ /${\displaystyle u}$ v${\displaystyle }$, ${\displaystyle x}$) ${\$$displaystyle$ $P(G,x)=P$$($$G-uv,x)-P(G/uv,x$$)}($임의로 선택됨).$$

엣지 없는 그래프의 k-색상 수는 실제로 ${\displaystyle {kn}^{}}$ ${\$ k$^{n}}$이므로$,$ 모든 G에 대해 다항식 $P{\displaystyle (G}$ ${\displaystyle ,}$ ${\displaystyle x}$) ${\displaystyle P(G,x)}$이 정수점 x = k에서의 k-색상 수와 일치한다는$$ 유도에 의해 뒤따른다.특히 색도 다항식은 점을 통해 최대 n개까지 보간하는 고유 다항식이다.

${\displaystyle \left\{(0,P(G,0),(1,P(G,1)),\ldots ,(n,P(G,n)\right\}.}$

어떤 다른 그래프 불변기가 그러한 재발을 만족시키는지에 대한 투트의 호기심은 투테 다항식 T ${\displaystyle G_{}}$(${\displaystyle x}$, ${\displaystyle y}$ $){\displaystyle T_{G}(x,y)}$의 이변성 일반화를 발견하게 했다$.$

예

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

${\displaystyle {Triangle\mathrm{}}_{}}$ K 3 ${\$	${\displaystyle x(x-1)(x-2)}$
전체 그래프 ${\displaystyle K_{n}}$	${\displaystyle x(x-1)(x-2)\cdots(x-(n-1))}$
에지리스 그래프 ${\displaystyle {\overline{K}_{n}}$	${\displaystyle x^{n}}$
경로 그래프 ${\displaystyle P_{n}}$	${\displaystyle x(x-1)^{n-1}$
정점에 있는 모든 트리	${\displaystyle x(x-1)^{n-1}$
사이클 ${\displaystyle C_{n}}$	${\displaystyle (x-1)^{n}+(-1)^{n}(x-1)}$
피터슨 그래프	${\displaystyle x(x-1)(x-2)\왼쪽(x^{7}-12x^{6}+67x^{5}-230x^{5}+230x^{4}+529x^{3}-814x^{2}+775x-352\오른쪽)}}$

특성.

n 정점의 고정 G의 경우, 색도 다항식 $P{\displaystyle (G}$, ${\displaystyle x}$) ${\displaystyle P(G,x)}$은 정수 계수를 가진 정확히 n의 단항 다항식이다$$.

색도 다항식에는 색도 숫자와 마찬가지로 G의 색도성에 대한 적어도 많은 정보가 포함되어 있다.실제로, 색소수는 색소 다항식의 0이 아닌 가장 작은 양의 정수다.

$\displaystyle \chi(G)=\min\{k\in \mathb {N} :P(G,k)>0\}$

-${\displaystyle 1}$ ${\displaystyle -1$ 즉 $P{\displaystyle (\mathrm{G}}$,${\displaystyle }$- 1${\displaystyle }$) ${\displaystyle P(G,-1$에서 평가한 다항식은${\displaystyle }$G의 순환 방향 횟수의${\displaystyle }$-${\displaystyle {}^1}$V$(G){{V(G) }}}$을 산출한다.^[4]

1, $P{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$( ${\displaystyle G}$, ${\displaystyle 1}$) ${\displaystyle P'$ ($G,1)}$에서 평가된 파생상품은 서명할 색도 불변성 $\theta {\displaystyle }$( ${\displaystyle G}$) ${\displaystyle \theta (G)}$과 동일하다$$.

G에 정점이 없고 c ${\displaystyle {성분}_{}}$이 G${\displaystyle {}_{}}$1${\displaystyle }$, …${\displaystyle }$, ${\displaystyle G_{}}$ c ${\$.

• ${\displaystyle {\mathrm{x}}^{}}$ ${\displaystyle {0\mathrm{}}^{}}$,${\displaystyle }$…${\displaystyle }$, x${\displaystyle {}^{}}$- ${\displaystyle 1^{}}$ ${\$의 계수는 0이다$$.
• $x{\displaystyle {}^{}}$ ${\displaystyle c^{}}$,${\displaystyle }$…${\displaystyle }$, ${\displaystyle x^{}}$ n ${\$ x$^{c},\ldots, x^{n}$의 계수는 모두$$ 0이 아니며 부호로 번갈아 나타난다.
• $x{\displaystyle {}^{}}$ ${\displaystyle n^{}}$ ${\$의 계수는 1이다$$(다항식은 단항이다).
• $x{\displaystyle {}^{}}$ ${\displaystyle n^{}}$- ${\displaystyle 1^{}}$ ${\$ x$^{n-1}$의 계수는${\displaystyle }$- ${\displaystyle E}$( ${\displaystyle G}$) $displaystyle$- $E(G) }$ 입니다$.$

$우리$는 n ${\displaystyle n}$ 정점과$$ k ${\displaystyle k}$ 가장자리가$$ 있는 단순 그래프 G의 가장자리 수에 대한 유도를 통해 이를 증명한다.$k{\displaystyle }$= ${\displaystyle 0}$ ${\displaystyle k=0$일 때 G는 빈 그래프다.따라서 정의 $P{\displaystyle (G,}$ ${\displaystyle x}$)${\displaystyle }$= ${\displaystyle {}^{}}$ ${\displaystyle n^{}}$ ${\$ 따라서 ${\displaystyle x^{}}$ n${\displaystyle {}^{}}$- ${\displaystyle 1^{}}$ ${\$의 계수는 $0{\displaystyle \mathrm{}}$ ${\displaystyle 0}$이며$,$ 빈 그래프에 대한 문장이 참임을 의미한다.$k{\displaystyle }$= ${\displaystyle 1}$ ${\displaystyle k=1$ 에서와 같이 하나의 가장자리만 있으면 ${\displaystyle {}^{}(G}$, ${\displaystyle x}$)${\displaystyle }$= x${\displaystyle {}^{}}$-${\displaystyle n^{}}$ - ${\displaystyle 1^{}}${\$displaystyle P(G,x)=x^{n}-x^{n-1$Thus coefficient of ${\displaystyle x^{n-1}}$ is ${\displaystyle -1=- E(G) }$. So the statement holds for k = 1. Using strong induction assume the statement is true for ${\displaystyle k=0,1,2,\ldots ,(k-1)}$. Let G have ${\displaystyle k}$ edges.수축-삭제 원리에 의해

${\displaystyle P(G}$ ${\displaystyle ,}$ x${\displaystyle }$)${\displaystyle }$= ${\displaystyle P(}$ ${\displaystyle G}$- e${\displaystyle }$, ${\displaystyle x}$)${\displaystyle }$- ${\displaystyle P(G}$/ ${\displaystyle e}$, x${\displaystyle }$) ${\displaystyle P(G,x)=P(G-e,x)-P(G/e,x$

Let ${\displaystyle P(G-e,x)=x^{n}-a_{n-1}x^{n-1}+a_{n-2}x^{n-2}-\cdots }$, and ${\displaystyle P(G/e,x)=x^{n-1}-b_{n-2}x^{n-2}+b_{n-3}x^{n-3}-\cdots }$.
따라서 $P{\displaystyle (G}$, ${\displaystyle x}$)${\displaystyle }$= ${\displaystyle x^{}}$ n${\displaystyle {}^{}}$- (${\displaystyle n_{}}$- ${\displaystyle 1{}_{}}$+ 1${\displaystyle }$) ${\displaystyle {}^{}}$ ${\displaystyle n^{}}$- ${\displaystyle 1^{}}$+ ${\displaystyle \cdots }$ ${\displaystyle P(G,x)={n^{n1}+1)x^{n-1+\cdots$$}.$
${\displaystyle G}$- e ${\displaystyle G-e}$은(는) $하나$의 에지 e만 제거하면 G에서 얻으므로 ${\displaystyle {\mathrm{n}}_{}}$- 1${\displaystyle {}_{}}$= k${\displaystyle }$- ${\displaystyle 1}$ ${\displaystyle a_{n-1}=$${\displaystyle \mathrm{k-1}}$$\},$ ${\displaystyle {따라서}_{}}$ $n{\displaystyle {}_{}}$- ${\displaystyle 1_{}}$ +${\displaystyle {}_{}1}$= k ${\displaystyle a_{n-1}+1=k},$ 따라서$$ 문장은 k에 대해 참이다.

• $x{\displaystyle {}^{}}$ ${\displaystyle {1\mathrm{}}^{}}$ ${\$의 계수는 (${\displaystyle }$- 1${\displaystyle {}^{}}$) ${\displaystyle {\mathrm{n}}^{}}$- ${\displaystyle 1^{}}$ ${\$의 지정된 임의로 선택한 꼭지점에서 고유한 싱크(sink)가 있는 순환 방향의 횟수의 곱이다$$$$.^[5]
• 모든 색도 다항식 계수의 절대값은 로그-콘카브 시퀀스를 형성한다.^[6]
• ${\displaystyle \scriptstyle P(G,x)=P(G_{1},x)P(G_{2},x)\cdots P(G_{c}x)}$

${\displaystyle G_{}}$가 $G{\displaystyle {}_{}}$ 1 ${\$ 스타일 $G_{1$} 및 ${\displaystyle G_{}}$ $2{\displaystyle {}_{}}$ ${\$ 스타일 $G_{2}}($즉, k 정점에 있는 클라이크에서 두 개를 붙여서 얻은 그래프)의 k 클라이크섬인 경우, 마지막 속성은 일반화된다.

${\displaystyle P(G,x)={\frac {P(G_{1},x)P(G_{2},x)}{x(x-1)\cdots(x-k+1)}}.}$

정점이 n개인 그래프 G는 다음과 같은 경우에만 트리임

${\displaystyle P(G,x)=x(x-1)^{n-1}.}$

색도 등가성

두 개의 그래프는 동일한 색도 다항식을 갖는 경우 색도 등가라고 한다.이등형 그래프는 동일한 색다형 다항식을 가지지만, 비등형 그래프는 색다르게 동등할 수 있다.예를 들어, n 꼭지점의 모든 트리는 동일한 색도 다항식을 가진다.특히${\displaystyle }$( ${\displaystyle \mathrm{x}}$-${\displaystyle {}^{}}$1) ${\displaystyle {3\mathrm{}}^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle (x-1)^{3}x}$는 클로 그래프와 4정점 경로 그래프의 색다형 다항식이다.

그래프는 색다형 다항식, 이형성까지로 결정되면 색도적으로 고유하다.즉, G는 색채적으로 고유하며, 그러면 $P{\displaystyle }$( ${\displaystyle G}$, x${\displaystyle }$)${\displaystyle }$= ${\displaystyle P}$( ${\displaystyle H}$, ${\displaystyle x}$ $){\displaystyle P (G,x)=P(H,x)}$는 G와 H가 이형체라는 것을 의미할$$ 것이다.모든 사이클 그래프는 색상으로 고유하다.^[7]

색뿌리

한 색채 다항식의 뿌리의(또는 0),“색채 뿌리”P(G, x).Chromatic 뿌리가 매우 잘, 사실, 그 색채 다항식을 정의하기 위하버코프의 근본 동기가 평면 그래프에, P(G, x)을을 보여 주는 것이었습니다;0{\displaystyle P(G,x)>0를 공부해 왔다 0{P(G,x)=0\displaystyle} 일고 있는 값)라고 불렀다.}였을까r x x ≥ 4.이것으로 사색 정리가 성립되었을 것이다.

그래프는 0색이 될 수 없으므로 0은 항상 색의 근원이 된다.엣지 없는 그래프만 1색일 수 있으므로 1은 적어도 하나의 엣지를 가진 모든 그래프의 색 근이다.한편, 이 두 점을 제외하고, 어떤 그래프도 32/27보다 작거나 같은 실제 숫자의 색도 근을 가질 수 없다.^[8]Tutte의 결과는 황금비 ${\displaystyle \pi }$을(를) 색뿌리에 대한 연구와$$ 연결시켜 색뿌리가 ${\displaystyle {\varphi \mathrm{}}^{}}$ 2 ${\$: ${\displaystyle {Gn}_{}}$ ${\$가 구의 평면삼각형이라면 그때그때 나타난다.

${\displaystyle P(G_{n},\phi ^{2})\leq \phi ^{5-n}.}$

따라서 실제 선은 어떤 그래프에 대해서도 색의 뿌리를 포함하지 않는 큰 부분을 가지고 있지만, 복잡한 평면의 모든 점은 색의 뿌리가 복잡한 평면에 밀도 있는 그래프의 무한 계열이 존재한다는 점에서 색의 뿌리에 임의적으로 근접한다.^[9]

모든 색상을 사용한 색상

n 정점에 있는 그래프 ${\displaystyle G_{}}$의 경우$,$ $e{\displaystyle {}_{}}$ k {\$displaystyle e_{k}}$가 정확히 k 색상을 사용한 색상 수를 최대 개명으로 표시하도록 한다(그래서 색을 허용하여 서로 얻을 수 있는 색상은 하나로 계산되며, G의 자동화에 의해 얻은 색상은 여전히 별도로 계산된다).즉, $e{\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\$는 k(비어 있지 않은) 독립 집합으로 설정된 정점의 파티션 수를 카운트한다$$.그런 다음 $k{\displaystyle !}$ ${\displaystyle \cdot }$ ${\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\$ k$!\cdot e_{k}}}}$정확한 k 컬러(구분 가능한 컬러 포함)를 사용하여 컬러링 수를 셉니다$$.정수 x의 경우 G의 모든 x-색상은 정수 k ≤ x를 선택하고, 사용 가능한 x 중에서 사용할 k 색상을 선택하고, 정확히 그 k(distuishable) 색상을 사용한 색상을 선택하여 얻을 수 있다.따라서 다음과 같다.

$displaystyle P(G,x$$\cdot e_{k}=\sum _{k=0}^{x}(x)_{k}\cdot e_{k$

여기서${\displaystyle }$( ${\displaystyle x{}_{}}$) ${\displaystyle k{}_{}}$= ${\displaystyle x}$( ${\displaystyle x}$- 1${\displaystyle }$)${\displaystyle }$( x${\displaystyle }$- ${\displaystyle 2}$) ${\displaystyle \cdots }$( ${\displaystyle x}$- ${\displaystyle k}$+ ${\displaystyle 1}$) ${\displaystyle (x)_{k}=x$(1$)(x-1)\cdots (x-k+1)}$는 하강 요인(하향 요인)을 나타낸다$$.Thus the numbers ${\displaystyle e_{k}}$ are the coefficients of the polynomial ${\displaystyle P(G,x)}$ in the basis ${\displaystyle 1,(x)_{1},(x)_{2},(x)_{3},\ldots }$ of falling factorials.

${\displaystyle k_{}}$ ${\$${\displaystyle \{k}$$}}$을(를${\displaystyle )}$ 표준 기준 $1{\displaystyle \mathrm{}}$,${\displaystyle x}$, ${\displaystyle {}^{}}$ 2,${\displaystyle {}^{}{x\mathrm{}}^{}{}^{}{3}^{}}$에서$$P${\displaystyle (}$G,$x$)의 k번째 $계수로$ 두십시오${\displaystyle .}$ 다음과 같은 경우, ${\displaystyle 1,x,x^{2},x^{3},\ldots$ $\}:$

${\displaystyle P(G,x)=\sum _{k=0}^{n}a_{k}x^{k}}}}}}$

스털링 수치는 표준 기준과 하락 요인 간의 기본값을 변화시킨다.이는 다음을 암시한다.

${\displaystyle a_{k}=\sum _{j=0}^{n}(-1)^{j-k}{\begin{bmatrix}j\\k\end{bmatrix}}e_{j}}$ and ${\displaystyle e_{k}=\sum _{j=0}^{n}{\begin{Bmatrix}j\\k\end{Bmatrix}}a_{j}}$.

분류

색채 다항식은 호바노프 호몰로지(Kovanov homology)와 밀접하게 관련된 호몰로지 이론에 의해 분류된다.^[10]

알고리즘

색다항식
입력	정점이 없는 그래프 G.
출력	$P{\displaystyle (G}$, ${\displaystyle x}$)의 계수 ${\displaystyle P(G,x)}$
러닝타임	${\displaystyle {일부}^{}}$ 상수 $r{\displaystyle }$ ${\displaystyle r}$에 대한$$O ( 2n r ) {\$displaystyle$ O$(2^{n}n^{r}}}$
복잡성	#P-하드
로부터의 감소	3위 SAT

#k컬러링
입력	정점이 없는 그래프 G.
출력	$P(G,k)}$
러닝타임	In P for ${\displaystyle k=0,1,2}$. ${\displaystyle O(1.6262^{n})}$ for ${\displaystyle k=3}$. Otherwise ${\displaystyle O(2^{n}n^{r})}$ for some constant ${\displaystyle r}$
복잡성	#P-hard($k{\displaystyle }$= ${\displaystyle 0,}$ ${\displaystyle 1}$,${\displaystyle 2}$ ${\displaystyle$k=$0,1,$2}이$($가) 아닌 경우
근사성	$k$> ${\$displaystyle k >2}에 대한 $FPRAS$ 없음

색채 다항식과 관련된 계산 문제:

• 주어진 그래프 G의 색도 다항식 $P{\displaystyle (G}$, ${\displaystyle x}$) ${\displaystyle P(G,x)}$ 찾기
• 주어진 G에 대해 고정점 x에서 $P{\displaystyle }$( ${\displaystyle G}$, x${\displaystyle }$) ${\displaystyle P(G,x)}$을(를) 평가한다.

첫 번째 문제는 보다 일반적인데, 왜냐하면 만약 $우리$가 P${\displaystyle }$(${\displaystyle G}$, x $){\displaystyle$P ($G,x)}$의 계수를 안다면, 그 정도는$$ n이기 때문에 다항식의 어느 지점에서나 평가할 수 있기 때문이다.두 번째 유형의 문제의 난이도는 x의 가치에 따라 크게 달라지며 계산 복잡성에 대해 집중적으로 연구되어 왔다.x가 자연수일 때, 이 문제는 일반적으로 주어진 그래프의 x-색상 수를 계산하는 것으로 간주된다.예를 들어, 여기에는 계수 복잡성 연구의 표준적인 문제인 3-색상 수를 계수하는 #3-색상이 포함되며, 계수 클래스 #P에 대해 완료된다.

효율적인 알고리즘

일부 기본 그래프 클래스의 경우 색도 다항식의 폐쇄 공식이 알려져 있다.예를 들어, 이것은 위의 표에 열거된 나무와 패거리의 경우에 해당된다.

다항 시간 알고리즘은 화음 그래프와^[11] 경계 클라이크 폭의 그래프를 포함하여 더 넓은 등급의 그래프를 위해 색도 다항식을 계산하는 것으로 알려져 있다.^[12]후자 등급은 외부 평면 그래프와 같이 경계 트리 너비의 cograph와 그래프를 포함한다.

삭제-연락

삭제-접속 반복은 삭제-접속 알고리즘이라고 불리는 색소 다항식을 계산하는 방법을 제공한다.첫 번째 형태(마이너스 포함)에서는 빈 그래프 모음에서 반복이 종료된다.두 번째 형태(플러스 포함)에서는 완전한 그래프의 집합으로 종료된다.이것은 그래프 색칠을 위한 많은 알고리즘의 기초를 형성한다.컴퓨터 대수 시스템 매스매티카의 콤비나토리카 패키지에 있는 ChromaticPolynomial 함수는 그래프가 밀도일 경우 두 번째 재발을, 그래프가 희박할 경우 첫 번째 재발을 사용한다.^[13]두 공식 중 최악의 경우 실행 시간은 피보나치 숫자와 동일한 반복 관계를 만족하므로 최악의 경우 알고리즘은 다음 중 하나의 다항 계수 내에서 시간 내에 실행된다.

${\displaystyle \phi ^{n+m}=\좌({\frac {1+{\sqrt{5}}{5}}}\우)^{n+m}^{n+m}\in O\좌(1.62^{n+m}\우),}}$

꼭지점과 m 가장자리가 있는 ^[14]그래프에분석은 입력 그래프의 스패닝 트리의 $숫자$ t${\displaystyle }$( ${\displaystyle G}$) ${\displaystyle t(G)}$의 다항 계수 내에서 개선할 수 있다.^[15]실제로 일부 재귀적 호출을 피하기 위해 분기 및 바운드 전략과 그래프 이소모르프리즘 거부를 채택하고 있으며, 실행 시간은 정점 쌍을 선택하는 데 사용되는 휴리스틱에 따라 달라진다.

큐브법

각 꼭지점에 자연수를 할당하는 것으로서, 그래프 색상은 정수 격자의 벡터라는 것을 관찰함으로써 그래프 색상에 대한 자연스러운 기하학적 관점이 있다.동일한 색상이 주어지는$$ 두 개의 $꼭지점{\displaystyle }$ i ${\displaystyle i}$과 j ${\displaystyle j}$은(는) $색상{\displaystyle }$ 벡터에서 i ${\displaysty i$과(와) $j{\displaystyle }$ ${\$$displaysty$ $j}$과(와)$$같기 때문에, 각 가장자리는${\displaystyle }${${\displaystyle x{r}^{}}$ R${\displaystyle {}^{}}$d : ${\displaystyle x_{}}$ i${\displaystyle {}_{}}$= ${\displaystyle x_{}}$ j${\displaystyle {}_{}}$의 하이퍼플레인 형식과(와)이 연관될 수 있다$.$$스타일 \{x\in R^{d}x_{i}=x_{j$주어진 그래프에 대해 그러한 하이퍼플레인의 모음을 그래픽 배열이라고 한다.그래프의 적절한 색상은 금지된 하이퍼플레인을 피하는 격자점이다.$k{\displaystyle }$ ${\displaystyle k}$색상으로$$ 제한하여 격자 지점이${\displaystyle }$큐브 [${\displaystyle 0,}$ ${\displaystyle k}$ ${\displaystyle {}^n}$ ${\$에 포함되어 있다$.$ 이러한 맥락에서 색도 다항식은 그래픽 배열을 피한${\displaystyle }$[${\displaystyle 0}$, ${\displaystyle k}$ ${\displaystyle [0,$k] -cube에서$$ 격자 점의 수를 계산한다.

계산 복잡성

주어진 그래프의 3-색상 수를 계산하는 문제는 #P-완전성 문제의 표준적인 예이므로, 색도 다항식의 계수를 계산하는 문제는 #P-hard이다.마찬가지로 주어진 G에 대해$$ $P{\displaystyle (\mathrm{G}}$, 3${\displaystyle }$) ${\디스플레이$ 스타일 $P(G,3)}$을(를) 평가하는 것도 #P-완전하다.반면에 $k{\displaystyle }$ =${\displaystyle }$0${\displaystyle ,}$ ${\displaystyle 1}$, ${\$디스플레이 $스타일$ k=$0,1$,${\displaystyle 2}$$}$의 $경우$ P$($${\displaystyle G,}$ k $){\디스플레이$ 스타일 $P(G,k)}$을 계산하기 쉬우므로 해당 문제는 다항식 시간 계산이 가능하다.For integers ${\displaystyle k>3}$ the problem is #P-hard, which is established similar to the case ${\displaystyle k=3}$. In fact, it is known that ${\displaystyle P(G,x)}$ is #P-hard for all x (including negative integers and even all complex numbers) except for the three “easy points”.^[16]따라서 #P-강도의 관점에서 보면 색도 다항식 계산의 복잡성을 완전히 이해한다.

팽창중

${\displaystyle P(G,x)=a_{1}x+a_{2}x^{2}+\cdots +a_{n}x^{n}}}}$

${\displaystyle {계수}_{}}$ $a{\displaystyle {}_{}}$ ${\$는 항상 1과 같으며$$, 계수의 몇 가지 다른 속성이 알려져 있다.이는 일부 계수가 계산하기 쉬운지에 대한 의문을 제기한다.그러나 고정된 r 1 1과 주어진 그래프 G에 대해 a를_r 계산하는 계산상의 문제는 초당적인 평면 그래프에서도 #P-hard이다.^[17]

세 가지 쉬운 점을 제외하고 어떤 x에도 $P{\displaystyle (G}$, ${\displaystyle x}$) ${\디스플레이$ 스타일 $P(G,x)}$ 계산용 근사 알고리즘도 알려져$$ 있지 않다.정수점 $k{\displaystyle }$= ${\displaystyle 3}$,${\displaystyle }$4,${\displaystyle }$… ${\디스플레이$ 스타일 k=3,$4,\ldots }$에서 주어진 그래프가 k-색일 수 있는지 여부를 결정하는 해당 결정 문제는 NP-hard이다$.$그러한 문제는 NP = RP가 아닌 한 경계 오류 확률론 알고리즘에 의해 어떤 곱셈 인자에 근사치할 수 없다. 왜냐하면 어떤 곱셈 근사치라도 값 0과 1을 구별하여 한정 오류 확률론적 다항 시간 내에 결정 버전을 효과적으로 해결할 것이기 때문이다.특히, 동일한 가정 하에서, 이것은 완전한 다항 시간 무작위 근사 체계(FPRAS)의 가능성을 배제한다.다른 지적에 대해서는 좀 더 복잡한 주장이 필요한데, 문제는 적극적인 연구의 초점이다.2008년^[update] 현재, NP = RP가 보유하지 않는 한, 어떤 x > 2에 대해서도$$ $P{\displaystyle (G}$, x$){\디스플레이$ 스타일 $P(G,x)}$를 계산하기 위한 FPRAS는 없는 것으로 알려져 있다.^[18]

메모들

참조

외부 링크

• Weisstein, Eric W. "Chromatic polynomial". MathWorld.
• 플래닛매트릭스 색다항식
• 게리 해더드, 데이비드 J. 피어스, 고든 로일(Gordon Royle)의 Tutte, Chromatic 및 Flow Polyomials 계산 코드: [1]^{[permanent dead link]}