켐페 체인

Kempe chain
파란색과 빨간색 정점이 번갈아 나타나는 캠퍼스 체인을 포함하는 그래프

수학에서 켐페 체인은 주로 4색 정리 연구에 사용되는 장치다.직관적으로 그래프에 점들이 서로 다른 색으로 연결된 체인이다.

역사

켐페 체인은 알프레드 켐페가 4색 정리 시도에 처음으로 사용하였다.[1]비록 그의 증거가 불완전한 것으로 판명되었음에도 불구하고, 켐페 체인의 방법은 성공적인 현대 교정(Appel & Haken, Robertson et al. 등)에 결정적이다.더욱이 이 방법은 4색 정리의 약한 형태인 퍼시 존 헤이워드에 의한 5색 정리의 입증에 사용된다.[1]

형식 정의

켐페 체인(Kempe chain)이라는 용어는 서로 다르지만 관련된 두 가지 방법으로 사용된다.

G가 정점이 V로 설정된 그래프라고 가정하고, 우리는 착색 함수를 얻게 된다.

여기서 S는 최소 두 개의 뚜렷한 색상 a와 b를 포함하는 유한한 색상 집합이다.v가 색상 a를 가진 정점이라면, v를 포함하는 G의 (a, b)-켐페 체인은 v를 포함하고 모든 정점이 a 또는 b 중 하나로 색칠된 V의 최대 연결 부분 집합이다.

위의 정의는 켐페가 작업한 것이다.전형적으로 세트 S는 네 가지 요소(네 가지 색상 정리 중 네 가지 색상)를 가지고 있으며, c는 적절한 착색이다. 즉, V에 인접한 정점의 각 쌍에는 구별되는 색상이 할당된다.

4색 정리의 현대적인 컴퓨터 기반의 증명에서 사용되는 보다 일반적인 정의는 다음과 같다.다시 한번 G가 엣지 세트 E가 있는 그래프라고 가정해 봅시다. 그리고 이번에는 컬러링 함수를 가지게 되었다.

e가 색상 a가 할당된 가장자리인 경우, e를 포함하는 G의 (a, b)-켐페 체인은 e를 포함하고 모든 가장자리가 a 또는 b로 색칠된 E의 최대 연결 부분 집합이다.

이 두 번째 정의는 일반적으로 S가 a, b, c라는 세 개의 원소를 가지고 있고, V가 입방 그래프인 경우, 즉 모든 정점에 세 개의 입사 모서리가 있는 경우에 적용된다.만약 그러한 그래프가 적절히 색칠된다면, 각각의 꼭지점들은 세 가지 뚜렷한 색상의 가장자리를 가져야 하며, 켐페 체인은 결국 경로로 되어버리게 되는데, 이것은 첫 번째 정의의 경우보다 간단하다.

지도 면에서는

4색 정리 적용

주요 기사:사색정리

네 가지 색 정리에서 켐페는 모든 그래프가 반드시 5개 이하의 정점을 가지거나, 또는 이웃이라고 불리는 다섯 개의 다른 정점을 건드리는 정점을 포함하고 있다는 것을 증명할 수 있었다.이와 같이 4색 정리를 증명하기 위해서는 5색 이하의 정점이 모두 4색이었음을 증명하기에 충분하다.켐페는 학위 4의 사례를 증명할 수 있었고, 켐페 체인을 이용하여 학위 5의 부분적인 증거를 제시할 수 있었다.[2]

이 경우, 켐페 체인은 어떤 꼭지점도 자신과 다른 네 가지 색, 즉 학위가 4가 되어야 한다는 생각을 증명하기 위해 사용된다.첫째, 정점 v와 정점 네 개를 이웃으로 하여 그래프를 만들 수 있다.정점 v를 제거하면 나머지 정점들을 4색 할 수 있다.우리는 빨강, 노랑, 파랑, 초록색 순으로 색상을 설정할 수 있다.이런 상황에서 붉은 색과 푸른 색의 이웃에 합류하는 켐페 사슬이나 녹색과 노란 색의 이웃에 합류하는 켐페 사슬이 있을 수 있지만, 이 두 길이 반드시 교차할 것이고, 그들이 교차하는 꼭지점은 색칠할 수 없기 때문에 둘 다 있을 수는 없다.만약 켐페 체인이 녹색과 노란색 이웃을 연결하고 있다고 가정한다면, 빨간색과 파란색은 반드시 켐페 체인을 사이에 두지 말아야 한다.그래서 원래의 꼭지점 v를 다시 그래프에 넣을 때, 우리는 단순히 빨간 꼭지점과 그 이웃들(빨간 꼭지점 포함, 파랑으로 만들기)의 색상과 색 꼭지점 v를 빨간색으로 반전시킬 수 있다.이것은 네 가지 색의 그래프를 만든다.[3]

기타 응용 프로그램

캠퍼 체인은 색소 확장 문제를 해결하기 위해 사용되어 왔다.[4][5]

참조

  1. ^ a b "Colorful Mathematics: Part I". American Mathematical Society. Retrieved July 10, 2020.
  2. ^ 아펠, 케네스; 하켄, 볼프강 (1989) Every Planar Map은 4색, 현대 수학, 98, J. Koch, Providence, RI: American Mathem Society, doi:10.1090/conm/098, ISBN 0-8218-5103-9, MR 10353
  3. ^ 켐페, A. B. (1879년), "4가지 색의 지리적 문제에 대하여" 미국 수학 저널, 존스 홉킨스 대학 출판부, 2: 193–220
  4. ^ Albertson, M. O. (1998). "You Can't Paint Yourself into a Corner". Journal of Combinatorial Theory, Series B. 73 (2): 189–194. doi:10.1006/jctb.1998.1827.
  5. ^ Albertson, M. O.; Moore, E. H. (1999). "Extending Graph Colorings". Journal of Combinatorial Theory, Series B. 77: 83–95. doi:10.1006/jctb.1999.1913.