수학 역사상 가장 위대한 일화 중 하나는 23년 1852월 XNUMX일에 시작되었습니다. William Rowan Hamilton 경에게 보낸 편지에서 Augustus De Morgan은 이렇게 썼습니다. 모른다는 것은 사실이며 아직은 모릅니다.” 오늘날까지도 그 "사실"은 계속해서 학자들을 매혹시키고 도전하게 합니다.

학생은 Frederick Guthrie였으며 문제의 "사실"은 원래 그의 형제 Francis에서 나왔습니다. 영국 카운티 지도를 본 후, 그는 XNUMX개 이하의 색상을 사용하여 지도에 색상을 지정하는 동시에 경계를 공유하는 지역(모퉁이 지점 이상)이 다른 색상이 되도록 하는 것이 항상 가능한지 궁금했습니다.

이것이 항상 가능한 것처럼 보였습니다. 드 모건은 "생각할수록 더 분명해 보인다"고 적었다. 하지만 그 문제는 해밀턴을 흥분시키지 못했습니다. 그는 "나는 당신의 '쿼터니언 색상의 '곧. 그리고 다른 사람들의 관심을 끌기 위한 De Morgan의 노력도 실패했습니다.

이 문제는 1878년 Arthur Cayley가 London Mathematical Society 회원에게 증명을 찾은 사람이 있는지 물을 때까지 대부분 잠복해 있었습니다. 얼마 지나지 않아 증거가 나타나기 시작했습니다. 가장 중요한 것으로 판명된 것은 1879년 변호사 알프레드 켐페(Alfred Kempe)가 처음으로 한 것입니다. 그 증거는 설득력이 있었고, XNUMX년 넘게 옳은 것으로 받아들여졌습니다. 불행히도 Kempe의 증명은 다음 세기에 나타날 다른 모든 증거와 마찬가지로 결함이 있었습니다. 그러나 그것은 독창적이었고 최종 증명에 나타날 핵심 아이디어를 포함했습니다.

Kempe와 대부분의 수학자들이 이 문제를 어떻게 보았는지 이해하려면 지도에 각 지역의 모양, 크기 및 정확한 위치와 같이 색칠 문제와 관련 없는 많은 정보가 포함되어 있음을 인식하는 것이 도움이 됩니다. 모든 지역이 연결되어야 하지만 중요한 것은 어떤 지역이 경계를 공유하는가입니다. 별도의 상부 반도가 있는 미시간은 실제로 미국 지도가 XNUMX색으로 표시되는 것을 막지는 못하지만 수학적으로는 가능합니다.

중요한 정보에 집중하기 위해 점(정점)이 선(가장자리)으로 연결되는 네트워크라고도 하는 그래프를 사용하여 이러한 관계를 인코딩할 수 있습니다. 지도의 각 영역을 꼭지점으로 교체하고 주변 지역의 꼭짓점을 가장자리로 연결합니다. 도움이 된다면 정점이 수도이고 가장자리가 이들을 연결하는 도로라고 상상할 수 있습니다.

이런 식으로 지도 색칠 문제는 그래프 색칠 문제가 됩니다. 이웃이 다른 색이 되도록 꼭짓점을 색칠합니다. 색상의 최소 수를 그래프의 색채수라고 합니다. 우리는 그래프의 색수에 대해 물을 수 있지만 지도에서 나오는 그래프에는 특별한 속성이 있습니다. 이 그래프는 단순합니다. 즉, 동일한 꼭지점(루프라고 함)에서 시작하고 끝나는 가장자리가 없으며 두 꼭지점은 하나의 가장자리로만 연결될 수 있습니다. 그래프는 또한 평면형이므로 가장자리가 교차하지 않도록 그릴 수 있습니다.

우리는 이제 Francis Guthrie의 문제를 다시 말할 수 있습니다. 모든 단순 평면 그래프의 색수가 최대 XNUMX임을 증명하십시오.

다음은 맵이 아닌 그래프를 사용하여 현대 용어로 설명된 Kempe의 주장에 대한 스케치입니다. 그는 정점이 하나인 그래프(아마도 지도가 고립된 섬일 수 있음)에는 단 하나의 색상만 필요하다는 사실을 관찰하면서 시작했습니다. 그런 다음 그는 기껏해야 XNUMX개의 색상을 사용하여 XNUMX개의 꼭지점, XNUMX개의 꼭지점 등으로 그래프를 색칠하는 것이 가능하다고 주장하면서 거기에서 위쪽으로 구축하기 위해 영리한 주장을 사용했습니다. 방법은 다음과 같습니다.

모든 간단한 평면 그래프를 다음과 같이 채색할 수 있다고 가정합니다. n 최대 XNUMX개의 색상을 가진 꼭지점 — 이것은 사소한 일입니다. n 5 이하 - 그리고 우리는 다음으로 하나를 건네받습니다 n + 1 정점. 최대 XNUMX가지 색상으로 색칠할 수 있다는 것을 어떻게 보여줄 수 있습니까?

첫째, Kempe는 신중한 계산 인수를 사용하여 모든 간단한 평면 그래프에는 공통점이 있음을 보여주었습니다. 즉, 최대 XNUMX개의 이웃과 함께 적어도 하나의 꼭짓점을 포함해야 합니다. 모든 옵션을 고려하면 맵을 기반으로 하는 모든 가능한 그래프에는 정점의 XNUMX가지 특수 구성 중 하나가 포함됩니다.

이 정점과 이에 연결된 모든 가장자리를 제거하면 다음과 같은 그래프가 남습니다. n 꼭지점 — 우리가 이미 알고 있는 네 가지 색상을 사용하여 색상을 지정할 수 있습니다. 우리는 실제로 다음 단계로 그렇게 합니다. 이제 제거된 정점에 인접한 정점을 살펴봅니다. XNUMX개 이하의 색상을 표시하는 경우 제거된 정점을 나머지 색상 중 하나로 채색할 수 있습니다. n + 1 꼭지점은 네 가지 색상으로 색칠할 수 있습니다. 인접한 정점에 네 가지 색상이 모두 포함된 경우 Kempe는 제거된 정점에 대한 색상을 확보하기 위해 특정 정점을 다시 칠하는 영리한 방법을 고안했습니다. n + 1 정점에는 XNUMX가지 색상만 필요합니다.

1890년에 수학자 Percy Heawood는 Kempe의 오류를 확인했습니다. Kempe의 영리한 방법이 실패한 특별한 경우가 있었습니다. Heawood는 자신의 작업이 "건설적이라기보다는 파괴적"으로 보였지만 Kempe의 기술이 모든 지도를 XNUMX개 이하의 색상으로 채색할 수 있음을 증명할 수 있음을 보여주었다고 말했습니다. 원래 목표는 아니지만 여전히 인상적입니다.

Heawood는 더 복잡한 표면에 그려진 지도도 조사했습니다. 그는 도넛 위의 지도가 g 구멍은 $latex frac{mathrm 1}{mathrm 2} left( 7+sqrt{ 1+48g} right) $ 색상만큼 필요할 수 있습니다(이 값은 가장 가까운 정수로 내림됨). 따라서 일반 도넛을 장식하려면 최대 1968가지 색상의 프로스팅이 필요할 수 있습니다. 그러나 패턴이 되고 있는 것에서 일반적인 표면에 대한 그의 증명은 불완전했고 우리는 XNUMX년까지 완전한 증명이 없었습니다.

그러나 일반 곡면에 대한 Heawood의 정리가 증명되었을 때에도 XNUMX색 문제는 풀리지 않은 채로 남아 있었습니다. 하지만 수십 년간의 노력 덕분에 증거가 눈에 들어왔습니다.

Guthrie가 문제를 제기한 지 1976년 후인 124년 회의에서 Wolfgang Haken은 Kenneth Appel과 대학원생 John Koch의 도움을 받아 증명을 발표했습니다. 반응은 엇갈렸다. “관객들이 큰 박수를 보낼 것으로 예상했습니다.” 돈 앨버스를 썼다, 누가 이야기에 참석했습니다. "대신 그들은 정중한 박수로 화답했습니다!" 연필과 종이로 논쟁을 벌이는 것보다 팀이 컴퓨터에 크게 의존했기 때문입니다.

무한히 많은 평면 그래프가 가능하고 컴퓨터가 모든 그래프를 확인할 수 없기 때문에 질문에 직접 답하는 기계가 없었습니다. 그러나 Kempe가 모든 그래프에 꼭짓점의 1,936가지 특수 구성 중 하나가 포함되어 있음을 증명한 것처럼 Appel과 Haken은 모든 그래프에 1,936개의 특수 구성 중 하나가 있어야 함을 보여주었습니다. 정리를 증명하는 것은 이러한 하위 그래프를 포함하는 그래프를 색칠하는 데 1,000가지 색상만 필요하다는 것을 보여주는 것과 같습니다. Kempe의 XNUMX가지 특수 사례를 XNUMX개의 하위 사례로 세분화하여 더 세밀한 제어가 가능하고 각 사례를 확인하기가 더 쉬워졌습니다. 총 수가 너무 많아 사람이 도움 없이 확인할 수 없었습니다. 실제로 계산을 완료하는 데 XNUMX시간 이상의 컴퓨터 시간이 필요했습니다.

수학적 커뮤니티는 증거가 전적으로 인간에 의해 이해되고 검증될 수 있어야 한다고 믿으며 결과를 마지못해 받아들였습니다. 컴퓨터가 일상적인 산술을 수행하는 것은 허용되었지만 수학자들은 컴퓨팅 장치에 논리적 추론을 양도할 준비가 되어 있지 않았습니다. 이러한 보수주의와 시간 절약형 발전을 받아들이지 않으려는 태도는 새로운 것이 아닙니다. 17세기에 일부 수학자들이 기하학 문제를 풀기 위해 최신 대수 기법을 사용했을 때 비슷한 항의가 있었습니다. 유사한 드라마가 머신 러닝의 부상: 불투명한 알고리즘이 발견하고 증명한 정리를 수학자들이 받아들일 것인가?

1998색 문제의 증명은 물론 수학에서 컴퓨터 혁명의 시작에 불과했습니다. XNUMX년 Thomas Hales는 컴퓨터를 사용하여 유명한 것을 증명했습니다. 요하네스 케플러의 추측 구체를 쌓는 가장 효율적인 방법은 식료품점에서 오렌지를 쌓는 데 일상적으로 사용되는 방법입니다. 그리고 최근에는 컴퓨터가 "신의 수"를 찾는 데 도움을 주었습니다. 루빅스 큐브를 푸는 데 필요한 최대 비틀기 수입니다(20면 회전 또는 반 회전이 26로 계산되는 경우 XNUMX).

지도에 대한 XNUMX색 문제는 해결되었지만 그래프 색상 지정에 대한 많은 기본 질문은 답이 없거나 지금 막 해결 중.

표면에 대한 Heawood의 작업은 비평면 그래프에 대한 색상 가능성 질문을 할 수 있음을 보여주었습니다. 그리고 실제로 특정 그래프의 색수는 등가지도가 그려진 표면에 의존하지 않습니다. 예를 들어, 모든 정점이 다른 모든 정점에 연결되어 있는 그래프를 완전 그래프라고 하고, 완전한 그래프의 색수는 n 정점은 n. 따라서 큰 그래프에 다음과 같은 완전한 그래프가 포함된 경우 n 꼭지점, 그러면 큰 그래프의 반음계 수가 적어도 n.

이 관찰은 그래프의 색채 수가 다음과 같다는 것을 의미하지 않습니다. n, 그런 다음 완전한 그래프를 포함합니다. n 정점. 그러나 1943년에 Hugo Hadwiger는 매우 유사한 것을 추측했습니다. 그는 루프가 없는 그래프에 반음계가 있으면 n, 그런 다음 $latex K_n$ 마이너라고 하는 정점 배열이 있습니다. 여기서 일부 정점과 가장자리를 삭제하고 다른 정점을 그룹화하면 다음과 같은 완전한 그래프가 생성됩니다. n 정점. 바꿔 말하면 이 추측은 그래프에 $latex K_n$ 마이너가 없으면 n 그림 물감. 그래프 이론에서 가장 중요한 공개 문제 중 하나인 Hadwiger의 추측은 평면 그래프가 $latex K_5$ 마이너를 포함할 수 없기 때문에 XNUMX색 정리를 일반화합니다.

그래프 채색은 지도 제작의 질문에서 시작되었지만 지도나 색상과 관련이 없는 문제도 그래프 채색 프레임워크에 적합할 수 있습니다. 예를 들어 스도쿠는 위장한 그래프 색칠 문제입니다. 각 셀을 꼭지점으로 보고 20개의 숫자를 색상으로 봅니다. 각 꼭짓점에는 3개의 가장자리가 있습니다. 행, 열 및 3x81 하위 사각형의 각 셀에 하나씩 있습니다. 810개의 꼭짓점과 XNUMX개의 가장자리로 구성된 이 그래프는 부분 색칠(주어진 단서)로 시작합니다. 게임의 목표는 나머지 꼭짓점을 색칠하는 것입니다.

이러한 색칠 문제가 받은 모든 관심에도 불구하고 우리는 여전히 인간이 읽을 수 있는 원래의 XNUMX색 정리에 대한 증거를 가지고 있지 않습니다. 노력이 부족해서가 아닙니다. 오늘날에도 새로운 증명이 나타나 약간의 열정을 불러일으키고 Kempe의 증명처럼 오류가 있는 것으로 나타났습니다.

수학자 Paul Erdős는 모든 정리의 가장 우아한 증명을 포함하는 가상의 책인 "The Book"에 대해 말하곤 했습니다. The Book에 XNUMX색 정리에 대한 인간이 읽을 수 있는 증명이 포함되어 있는지, 그렇다면 우리가 그것을 볼 수 있을지 궁금합니다.