방전법(분리수학)

방전법은 구조 그래프 이론에서 레마(Lemmas)를 증명하기 위해 사용되는 기법이다.방전은 4색 정리의 증명에서 중심적인 역할로 가장 잘 알려져 있다.방전 방법은 특정 클래스의 모든 그래프가 지정된 리스트의 일부 하위 그래프를 포함하고 있음을 증명하는 데 사용된다.원하는 하위 그래프의 존재는 종종 색칠 결과를 증명하기 위해 사용된다.

가장 일반적으로 방전은 평면 그래프에 적용된다.처음에는 그래프의 각 면과 정점에 전하가 할당된다.요금은 적은 양의 숫자로 합치도록 할당된다.방전 단계 동안 각 면 또는 꼭지점의 충전은 일련의 방전 규칙에서 요구하는 대로 근처의 면과 정점에 재분배될 수 있다.그러나 각 퇴원 규정은 요금 합계를 유지한다.규칙은 방출 단계 후 양전하를 가진 각 면 또는 정점이 원하는 하위 그래프 중 하나에 놓이도록 설계된다.전하의 합이 양이므로 어떤 얼굴이나 꼭지점에는 양전하가 있어야 한다.많은 방전 인수는 몇 가지 표준 초기 충전 기능 중 하나를 사용한다(이러한 기능은 아래에 나열되어 있다).방전 방법을 성공적으로 적용하려면 방전 규칙의 창의적인 설계가 필요하다.

예

1904년 베르니케는 다음과 같은 정리를 증명하기 위해 방전법을 도입하였는데, 이는 4색 정리를 증명하려는 시도의 일환이었다.

정리:평면 그래프가 최소 도 5를 갖는 경우, 도 5 또는 도 5와 도 6의 끝점을 모두 가진 가장자리가 있다.

$증명{\displaystyle }$: $V{\displaystyle }$ ${\displaystyle V$ F ${\displaystyle F}$ 및$$$E{\displaystyle }$ ${\displaystyle E}$을 사용하여$$ 각각 정점, 면 및 가장자리 집합을 표시한다.끝점이 모두 5도 또는 5도 및 6도인 경우 가장자리 조명을 부른다.그래프를 평면에 삽입하십시오.정리를 증명하기 위해서는 평면 삼각측량만 고려하는 것으로 충분하다(삼각형을 유지하면 원래 그래프로 돌아가기 위해 노드를 제거할 때 원하는 에지의 어느 쪽 노드는 5 이하의 그래프의 최소도를 줄이지 않고는 제거할 수 없기 때문이다).우리는 삼각 측정이 될 때까지 임의로 그래프에 가장자리를 추가한다.원래 그래프는 최소 도 5를 가졌기 때문에 새 에지의 각 끝점은 최소 6도를 가진다.그래서, 새로운 가장자리 중 어느 것도 가볍지 않다.따라서 삼각측량에서 가장자리가 가벼운 경우 그 가장자리가 원래 그래프에 있었을 것이다.

We give the charge ${\displaystyle 6-d(v)}$ to each vertex ${\displaystyle v}$ and the charge ${\displaystyle 6-2d(f)}$ to each face ${\displaystyle f}$, where ${\displaystyle d(x)}$ denotes the degree of a vertex and the length of a face. (Since the graph is a triangulation, the각 면에 대한 충전량은 0).그래프의 모든 도 합계가 가장자리 수의 두 배와 같다는 것을 상기하십시오. 마찬가지로 모든 면 길이의 합도 가장자리 수의 두 배와 같다는 것을 기억하십시오.오일러의 포뮬러를 사용하면 모든 혐의의 합이 12:00이라고 쉽게 알 수 있다.

${\displaystyle {\begin{aigned}\sum _{f\in F}6-2d(f)+\\\6 F -2(v)=&\2(2 E)+6 V -2 E =&#6(F - E + V )=&12.\end{정렬}}}$

우리는 단 하나의 방전 규칙만 사용한다.

• 각 도 5 꼭지점은 각 이웃에 1/5의 전하를 준다.

우리는 어떤 정점이 긍정적인 최종 전하를 가질 수 있는지 고려한다.양의 초기 충전이 있는 정점은 도 5의 정점뿐입니다.각 도 5 꼭지점은 각 이웃에 1/5의 전하를 준다.So, each vertex is given a total charge of at most ${\displaystyle d(v)/5}$. The initial charge of each vertex v is ${\displaystyle 6-d(v)}$. So, the final charge of each vertex is at most ${\displaystyle 6-4d(v)/5}$. Hence, a vertex can only have positive final charge if it ha최고 7도이제 우리는 양의 최종 전하를 가진 각 꼭지점이 광선 가장자리의 끝점에 인접해 있다는 것을 보여준다.

$정점{\displaystyle }$ v ${\displaystyle v}$이(가) 도 5 또는 6이고 양의 최종 전하를 갖는 경우 $v{\displaystyle }$ ${\displaystyle v}$이(가) 인접한 도 5 정점 $u{\displaystyle }$ ${\displaystyle u$로부터 전하를 받았으므로$$ $엣지{\displaystyle }$ ${\displaystyle u}$v {\$displaystystyle u}$이(가)가 가볍다$$.정점 $v{\displaystyle }$ ${\displaystyle$ v$}$이(가) 도 7을 가지고$$ 있고 양의 최종 전하를 갖는 경우 v ${\displaystyle$ v}이$($가) $최소{\displaystyle }$ 6개의 인접 도 5 정점으로부터 전하를 받았다$$.그래프가 삼각형이기 때문에 $v{\displaystyle }$ ${\$$displaystyle$ $v}$에 인접한 정점들이 주기를 형성해야$$ 하며, 도 7에 불과하므로 도 5 이웃들은 더 높은 도들의 정점으로 모두 분리될 수 없으며$,$ 이 $주기$에서는 도 5 이웃들 중 적어도 두 이웃이 서로 인접해야 한다$$.이렇게 하면 가장자리가 가벼워진다.

참조

• Appel, Kenneth; Haken, Wolfgang (1977), "Every planar map is four colorable. I. Discharging", Illinois Journal of Mathematics, 21: 429–490, doi:10.1215/ijm/1256049011.
• Appel, Kenneth; Haken, Wolfgang (1977), "Every planar map is four colorable. II. Reducibility", Illinois Journal of Mathematics, 21: 491–567, doi:10.1215/ijm/1256049012.
• Hliněný, Petr (2000), Discharging technique in practice. (Combinatorics에 대한 Spring School의 선택 텍스트).
• Robertson, Neil; Sanders, Daniel P.; Seymour, Paul; Thomas, Robin (1997), "The four-color theorem", Journal of Combinatorial Theory, Series B, 70: 2–44, doi:10.1006/jctb.1997.1750.
• Wernicke, P. (1904), "Über den kartographischen Vierfarbensatz" (PDF), Math. Ann. (in German), 58 (3): 413–426, doi:10.1007/bf01444968.