켐페의 사슬(영어 잘하시는 분도 답변 가능)

[안광준]

4색정리를 증명할 때 '켐페의 사슬'이라는 논법을 썼다고 하는데,

위키피디아에서 쳐보니 밑처럼 나오네요.

Kempe chain

From Wikipedia, the free encyclopedia

Jump to: navigation, search

In mathematics, a Kempe chain is a device used mainly in the study of the four colour theorem.

Contents

• 1 History
• 2 Formal definition
• 3 In terms of maps
• 4 Application to the four colour theorem

//

 History

Kempe chains were first used by Alfred Kempe in his attempted proof of the four colour theorem. Even though his proof turned out to be incorrect, the method of Kempe chains is crucial to the successful modern proofs (Appel & Haken, Robertson et al, etc). Furthermore, the method is used in the proof of the five-colour theorem, a weaker form of the four-colour theorem.

Formal definition

The term "Kempe chain" is used in two different but related ways.

Suppose G is a graph with vertex set V, and we are given a colouring function

 c : V  → S

where S is a finite set of colours, containing at least two distinct colours a and b. If v is a vertex with colour a, then the (a, b)-Kempe chain of G containing v is the maximal connected subset of V which contains v and whose vertices are all coloured either a or b.

The above definition is what Kempe worked with. Typically the set S has four elements (the four colours of the four colour theorem), and c is a proper colouring, that is, each pair of adjacent vertices in V are assigned distinct colours.

A more general definition, which is used in the modern computer-based proofs of the four colour theorem, is the following. Suppose again that G is a graph, with edge set E, and this time we have a colouring function

 c : E → S 

If e is an edge assigned colour a, then the (a, b)-Kempe chain of G containing e is the maximal connected subset of E which contains e and whose edges are all coloured either a or b.

This second definition is typically applied where S has three elements, say a, b and c, and where V is a cubic graph, that is, every vertex has three incident edges. If such a graph is properly coloured, then each vertex must have edges of three distinct colours, and Kempe chains end up being paths, which is simpler than in the case of the first definition.

해석잘하시는 분 혹은 이런 분야에 관심이 있으신분 답변 자세히 부탁드립니다.

[허걱~]

점마다 색이 칠해진(또는 a, b, c등의 이름이 붙어 있는) 그래프에서 어떤점 v가 a색이 칠해져있다고 생각할때 v 를 포함하는 (a, b) kempe chain은 간단히 말해서 v에서 시작해서 a 또는 b로 칠해진 점들만 따라가면 됩니다. 아주 concrete한 정의군요.