삭제-접속식

그래프 이론에서 삭제-접속 공식/재귀식은 다음과 같은 재귀 형식의 공식이다.

$[\displaystyle f(G)=f(G\setminus e)+f(G/e)]}$

여기서 G는 그래프, f는 그래프 상의 함수, e는 G의 어떤 가장자리, G \ e는 에지 삭제를 나타내며 G / e는 수축을 나타낸다.Tutte는 그러한 기능을 W-기능이라고 한다.^[1]그 공식을 근본적 환원 정리라고 부르기도 한다.^[2]이 글에서 우리는 DC로 줄여서 쓴다.

R. M. 포스터는 이미 색도 다항식이 그러한 함수 중 하나라는 것을 관찰한 바 있었고, 투테는 함수 f = t(G)를 세어 그래프의 스패닝 트리 수를 계산하는 등 더 많은 것을 발견하기 시작했다(키르호프의 정리도 참조).나중에 그 흐름 다항식은 아직 또 다른 것이라는 사실이 밝혀졌다; 곧 투테는 DC를 만족시키는 투테 다항식(원래는 디크롬산염이라고 불림)이라고 불리는 모든 종류의 함수를 발견했다.^[1]

예

스패닝 트리

스패닝 트리 $t{\displaystyle }$ (${\displaystyle G}$) ${\디스플레이$ 스타일 $t(G)}$의 수가 DC를 만족한다$$.^[3]

증명. $t{\displaystyle }$( ${\displaystyle G}$ ${\displaystyle \setminus }$ ${\displaystyle e}$) ${\displaystyle t(G\setminus$ e$)}$은 e를 포함하지 않는 신장 트리의 수를 나타내는 반면 t$$ ( $G{\displaystyle }$/ ${\displaystyle e}$)${\displaysty$t$(G/e)}$은 e를 포함하는 숫자를 나타낸다.두 번째를 보기 위해, T가 G의 스패닝 트리인 경우, 계약 $e$가 G${\displaystyle }$/ ${\displaystyle e}${\$displaystyle G/e}$의 스패닝 트리 T를 생성한다$.$ 반대로, $만약{\displaystyle 우리}$가 G /$$e {\$displaystyle G/$e}의 스패닝 트리 T를 가지고 있다면$,$ 에지를 확장하면 두 개의 분리된 트리가 생긴다; e를 추가하면 e가 된다.

색다항식

G의 k-색상 수를 계산하는$$ 색도 다항식 ${\displaystyle {\chi }_{}}$ G${\displaystyle {}_{}}$( ${\displaystyle k}$) ${\displaystyle \chi _{G}(k)}$는 DC를 만족하지 않고 약간 수정된 공식(등가하게 만들 수 있음):^[1]

$\displaystyle \chi _{G}(k)=\chi _{G\setminus e}-(k)-\chi _{G/e}(k).}$

증명. e = uv일 경우, g의 k-coloring은 u와 v의 색이 다른 G \ e의 k-coloring과 동일하다.$\chi {\displaystyle {}_{}}$ ${\displaystyle G_{}}$ ${\displaystyle {\setminus }_{}}$ ${\displaystyle e_{}}$ (${\displaystyle {}_{}k}$) ${\displaystyle \chi _{G\setminus e}(k)}$ 총 G \ e 컬러링이 있다.우리는 이제 u와 v가 비슷하게 색칠된 것을 뺄 필요가 있다.그러나 그러한 색상은 u와${\displaystyle {}_{}}$v가 ${\displaystyle \mathrm{병합}}$되는${\displaystyle }${$$G / e ( k ) ${\displaystyle \chi _${G$$/e}(k$)}$의 k-색상에 해당한다.

위의 속성은 색도 다항식 $\chi {\displaystyle {}_{}}$ ${\displaystyle G_{}}$( ${\displaystyle k}$) ${\displaystyle \chi _{G}(k)}$이(가) 실제로$$ k의 다항식임을 보여주는 데 사용할 수 있다.가장자리 수에 대한 유도를 통해 이를 $수행$할 수 있으며 가장자리가 없는 베이스 케이스에는 k ${\displaystyle V^{}}$ (${\displaystyle G^{}}$ $displaystyle$ k$^{$ V$(G)}}}}}$ 가능한$$ 색상(k 단위의 다항식)이 존재한다는 점에 유의하십시오.

삭제-연락 알고리즘

이 구간은 비어 있다.덧대면 도움이 된다.(2019년 5월)

참고 항목

• 포함-제외원칙
• 투테 다항식
• 색다항식
• 무영역 흐름

인용구