오색정리

5색 정리는 국가별 정치지도 등 지역으로 분리된 평면을 볼 때 인접 두 지역이 동일한 색상을 받지 않도록 5색 이하로 색칠할 수 있다는 그래프 이론의 결과다.

오색 정리는 더 강한 사색 정리에 의해 함축되어 있지만, 증명하기가 상당히 쉽다.그것은 1879년 알프레드 켐페에 의한 네 가지 색깔의 증명에서 실패한 시도에 바탕을 두고 있었다.퍼시 존 히우드는 11년 후 오류를 발견했고, 켐페의 작품을 바탕으로 오색 정리를 증명했다.

모순에 의한 증거의 개요

우선, 간단한 평면 $그래프{\displaystyle }$ G ${\displaystyle G$}을 지정된 지도에$$ 연결한다. 즉, 지도 각 영역에 꼭지점을 넣은 다음 해당 지역이 공통 테두리를 공유하는 경우에만 두 개의 꼭지점을 에지와 연결한다.그런 다음 이 문제는 그래프 색칠 문제로 번역된다. 어떤 가장자리가 같은 색의 끝점을 가지지 않도록 그래프의 정점을 그려야 한다.

$G{\displaystyle }$ ${\displaystyle G}$이(가) 단순한 평면이기 때문에, 즉, 가장자리를 교차하지 않고 평면에 박혀 있을 수 있고, 둘 이상의 가장자리를 공유하는 두 개의 정점이 없으며, 루프가 없는 경우, 최대 5개의 가장자리에서 정점을 공유해야 한다는 것을 (평면의 오일러 특성을 사용하여) 보여줄 수 있다.(참고: 이곳만이 오색조건이 교정에서 쓰이는 곳이다.4색 정리를 증명하는 데 이 기법을 사용한다면 이 단계에서는 실패할 것이다.실제로, 이두상 그래프는 5-정규형 및 평면형이기 때문에 최대 4개의 가장자리가 공유하는 정점을 가지고 있지 않다.)이러한 꼭지점을 $찾아서{\displaystyle }$ v$${\$displaystyle v}$이라고 부르십시오$.$

이제 $G{\displaystyle }$ ${\$$displaystyle G}$에서 v ${\displaystyle$ $v$$}$을(를) 제거하십시오$.$ 이 $방법$으로 얻은$$ $그래프{\displaystyle {}^{}}$ G ${\displaystyle {\prime }^{}}$ ${\$$displaystyle G}$보다 정점이 하나 적으므로 유도하여 5가지 색상으로만 채색할 수 있다고 가정할 수 있다$.$만약 색상이 $v{\displaystyle }${\$displaystyle$v}의 다섯 개의 인접 정점에 있는 다섯 가지 색상을 모두 사용하지 않았다면$,$ 그것은 이웃들이 사용하지 않는 색상으로$$ $G{\displaystyle }$ ${\displaystyle G}$로 색칠할 수 있다.$이제$ v${\displaystyle v_$${1},$$$${\displaystyle {v\mathrm{}}_{}}$ 2 ${\$}}, v ${\displaystyle {3\mathrm{}}_{}}$ ${\$ $v{\displaystyle {}_{}}$ 4 ${\$ ${\displaystyle {v\mathrm{}}_{}}$ $5{\displaystyle {}_{}}$ ${\$를 주기적 순서로$$ 보십시오(G 작성 방법에 따라 다름).따라서 v $1{\displaystyle {}_{}}$ ${\$},$$v ${\displaystyle {2\mathrm{}}_{}}$ ${\$ v ${\displaystyle {3\mathrm{}}_{}}$ ${\$ v ${\displaystyle {4\mathrm{}}_{}}$ ${\$ $v_{4$$\},$ v ${\$ v_{$5}$는 각각 1, 2, 4, 5로 색상이 되어 있다고$$ 가정할 수 있다.

이제 색상 1과 색상 3으로만 색칠된 정점과 이들을 연결하는 가장자리로 구성된$$ $G{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$의 서브그래프 G ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle 3_{}}$ ${\$을 고려하십시오.확실히 하기 위해, 각 가장자리는 색 1 꼭지점과 색 3 꼭지점(이것을 캠퍼 체인이라고 한다)을 연결한다.$v{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$${\displaystyle {}_{}}$${\displaystyle v_{}}$ 3 ${\$의 서로 다른 ${\displaystyle {연결}_{}}$된 $구성{\displaystyle {}_{}}$ 요소에 놓여$$ 있다면$,$ ${\displaystyle {\mathrm{우리}}_{}}$는 $나머지{\displaystyle {}^{}}$ G ${\displaystyle {\prime }^{}}$ ${\$${1}{1$}를 포함하는 구성 요소에서 1과 3 색상을 교환할 수$$ 있다$.$$작업$을 완료하는$$ v ${\displaystyle$ v$}$에 대한 s프리 색상 1.반대로 $v$ ${\$ ${\displaystyle {\mathrm{v}}_{}}$ 3 ${\$이 ${\displaystyle {G1\mathrm{},}_{}}$ 3 ${\$의 연결된 구성 요소에 놓여$$ 있으면, $우리$는 1과 3 정점 만으로 구성된 ${\displaystyle {G1\mathrm{}}_{}}$,${\displaystyle 3_{}}$ ${\$1,$3}$의 결합 경로를 찾을 수 있다$.$

이제 2색과 4색으로만 색칠된 정점과 이들을 연결하는 가장자리로 구성된$$ $′{\$의 서브그래프 $G{\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$,${\displaystyle 4_{}}$ ${\$를 선택하고 이전과 동일한 인수를 적용한다.그러면 $우리$는 v ${\$2}}을$$$$ $포함$하고 있는 ${\displaystyle {\mathrm{G}}_{}}$$$2,$$4 {\$displaystyle$ $G_{2,4}$의 서브그래프에 있는 2-4 색상을 되돌릴 수 있고, $아니면{\displaystyle }$ ${\displaystyle {v\mathrm{}}_{}}$ $2{\displaystyle {}_{}}${\$displaystyle v_{2}}}$와 $v{\displaystyle {}_{}}$ ${\displaystyle {4\mathrm{}}_{}}$ ${\$를 colo로만 구성된 경로로$$ 연결할 수 있다.r 2와 4 정점.${\displaystyle {v\mathrm{}}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ {\$displaystyle$ v_${$1}에서 v $5$${\$까지 순환 순서로 되어 있기$$ 때문에 이러한 경로는 이전에 구성한 1-3 컬러 경로를 교차하게 된다.이것은 그래프의 평면성과 모순되기 때문에 명백히 불합리하다.

따라서 $G{\displaystyle }$ ${\displaystyle G}$은(는) 초기 추정과는 달리 사실상 5색일 수 있다$$.

선형 시간 5-색상 알고리즘

1996년, 로버트슨, 샌더스, 세이모어, 토마스는 "효율적으로 4가지 색상의 평면 그래프"에서 2차 색상의 4-색상 알고리즘을 설명했다.^[1]그들은 같은 논문에서 증상 없이 최적인 선형 시간 5-색상 알고리즘을 간략히 설명한다.여기서 설명한 알고리즘은 다중그래프 상에서 작동하며, 단일 꼭지점 쌍 사이에 여러 개의 가장자리 복사본을 가질 수 있는 기능에 의존한다.베르니케의 정리에 근거한 것으로, 다음과 같이 기술하고 있다.

베르니케의 정리:G가 평면이고 비어 있지 않으며 두 가장자리로 테두리가 있는 면이 없으며 최소 도 5를 가지고 있다고 가정하십시오.그 다음 G는 최대 6도 정점에 인접한 5도 정점을 가진다.

우리는 각 꼭지점이 시계방향 평면 순서로 인접 정점의 원형 링크 목록을 유지하는 그래프의 표현을 사용할 것이다.

개념적으로 알고리즘은 반복적이며, 그래프를 하나의 정점수가 적은 작은 그래프로 축소하고, 그 그래프를 5가지 색으로 채색한 다음, 그 색상을 사용하여 큰 그래프의 색상을 일정한 시간에 결정한다.실제로, 축소된 각 그래프에 대해 명시적인 그래프 표현을 유지하는 대신, 우리는 그래프에서 정점을 제거하고 그것들을 스택에 추가한 다음, 마지막에 그것들을 스택에서 다시 튀기면서 색을 칠할 것이다.우리는 다음과 같은 3가지 스택을 유지할 것이다.

• S₄: (다중 에지로 인해) 최대 4도 또는 5도, 최대 4개의 뚜렷한 인접 정점 중 하나를 가진 나머지 정점을 모두 포함한다.
• S₅: 5도, 5개의 뚜렷한 인접 정점 및 최대 6도인 최소 1개의 인접 정점이 있는 나머지 정점들을 포함한다.
• S_d: 지금까지 그래프에서 삭제된 모든 정점을 삭제된 순서대로 포함.

알고리즘은 다음과 같이 동작한다.

1. 첫 번째 단계에서는 그래프가 단순하도록 모든 다중 가장자리를 단일 가장자리로 축소한다.다음으로, 우리는 그래프의 정점 위에 반복해서 S 또는₄ S₅ 조건과 일치하는 정점을 적절한 스택에 밀어 넣는다.
2. 다음으로 S가₄ 비어 있지 않은 한 S에서₄ v를 팝핑하여 그래프에서 v를 삭제하여 S에_d 밀어넣고, 이 시점에서 S의 이웃의 목록도 함께 넣는다.우리는 v의 이전 이웃을 각각 확인하여, v가 현재 필요한 조건을 충족하는지 여부를₄ S나 S로₅ 밀어 넣는다.
3. S가₄ 비어 있을 때, 우리는 우리의 그래프가 최소 5도라는 것을 안다.그래프가 비어 있으면 아래 마지막 5단계로 이동하십시오.그렇지 않으면 베르니케의 '정리'는 S가₅ 비어 있지 않다는 것을 말해준다.Pop₅ v off S, 그래프에서 삭제한 다음₁ v₂, v₃, v₄, v, v, v를₅ 시계방향으로 v의 이전 이웃으로 두십시오. 여기서₁ v는 최대 6도 정도의 이웃입니다.v가₁ v에₃ 인접해 있는지 확인한다(v의₁ 정도 때문에 일정한 시간에 할 수 있는 것).두 가지 경우가 있다.
   1. v가₁ v에₃ 인접하지 않으면 이 두 꼭지점을 하나의 꼭지점으로 병합할 수 있다.이를 위해 두 개의 원형 인접 목록에서 v를 제거한 다음 이전에 v가 발견된 지점에서 두 목록을 하나의 목록으로 분할한다.v가 각 목록에서 자신의 위치에 대한 참조를 유지한다면, 이 작업은 일정한 시간에 수행될 수 있다.이렇게 하면 리스트가 함께 분할된 두 지점에서 두 가장자리로 둘러싸인 면들이 생성될 수 있다; 우리는 그러한 면들 중에서 하나의 가장자리를 삭제한다.이렇게 한 후 v가₁ 병합된 정점이라는 메모와 함께 v를₃ S에_d 밀어 넣는다.병합의 영향을 받는 모든 정점은 적절하게 스택에서 추가 또는 제거된다.
   2. 그렇지 않으면 v는₂ v, v, v로₁₃ 윤곽을 나타낸 얼굴 안에 놓여 있다. 따라서 v는₂ 이 얼굴 외부에 있는 v에₄ 인접할 수 없다.우리는 위의 v와₁ v와₃ 같은 방식으로 v와₂ v를₄ 병합한다.
4. 2단계로 이동하십시오.
5. 이때 S₄, S, 그래프는₅ 비어 있다.우리는_d S에서 정점을 찍는다.3단계에서 정점이 다른 정점과 병합되었다면, 정점과 병합된 정점은 이미 색이 칠해져 있고, 우리는 동일한 색상을 할당한다.이는 원래 그래프에 인접하지 않은 정점만 병합했기 때문에 유효하다.2단계에서 제거했다면, 제거 당시 주변은 모두 색상이 칠해져 있었고, 주변 어느 곳에서도 사용하지 않는 색상을 지정하면 된다.

참고 항목

• 사색정리

참조

추가 읽기

• Heawood, P. J. (1890), "Map-Colour Theorems", Quarterly Journal of Mathematics, Oxford, vol. 24, pp. 332–338