Жазық карталарға бес түс жеткілікті

Кіріспе

Жоспарлы карталар ең көп дегенде бес түс қажет етеді.

Бес түсті теорема – график теориясының бір нәтижесі. Оған сәйкес, аймақтарға бөлінген жазықтық, мысалы, әлем елдерінің саяси картасы, екі жанындағы аймақтардың түсі бір-бірінен өзгеше болуын қамтамасыз ететіндей етіп, бес түстен артық емес түспен боялуы мүмкін. Бес түсті теорема төрт түсті теоремадан неғұрлым күшті, бірақ оны дәлелдеу әлдеқайда оңай. Ол 1879 жылы Альфред Кемпенің төрт түсті теореманы дәлелдеуге жасаған сәтсіз тынысының нәтижесінде туындады. Перси Джон Хьювуд 11 жыл өткен соң қателік тапты және Кемпенің жұмысына сүйене отырып, бес түсті теореманы дәлелдеді.

Қайшылық арқылы дәлелдеудің тұжырымдамасы

Ең алдымен, берілген картаға қарапайым жазық граф сәйкестендіріледі, атап айтқанда, картаның әр аймағына төбе қойылады, содан кейін екі төбе шетпен байланыстырылады, егер және тек қана сәйкес аймақтар ортақ шекараны бөлісе алса. Бұл мәселе графты бояу мәселесіне аударылады: графтың төбелерін бояу керек, сондықтан ешбір шеттің соңғы нүктелері бірдей түсте болмауы тиіс. Өйткені бұл қарапайым жазық граф, яғни, ол қиылысатын шеттері жоқ жазықтықта орналасуы мүмкін, және оның екі төбесі бір шетті бөліспейді, және оның циклдары жоқ, онда оның (жазықтықтың Эйлер сипаттамасын пайдалана отырып) ең көп дегенде бес шетпен ортақ төбесі болуы мүмкін екенін көрсетуге болады. (Ескерту: Бұл дәлелдемеде бес түстік талаптың қолданылған жалғыз жері. Егер осы техника төрт түстік теореманы дәлелдеу үшін қолданылса, онда ол осы қадамда сәтсіздікке ұшырайды. Шын мәнінде, икосаэдрлік граф 5-реттік және жазық, сондықтан ең көп дегенде төрт шетпен ортақ төбесі жоқ.) Мұндай төбеді табыңыз және оны деп атаңыз.
Енді -ден жойыңыз. Осылайша алынған графының төбелері -ден бір кем, сондықтан индукция бойынша оны тек бес түспен бояуға болады деп болжауға болады. Егер бояу -ның бес көршілес төбесіндегі бес түстің барлығын қолданбаса, оны көршілері қолданбаған түспен бояуға болады. Енді -мен циклдік ретпен (G қалай жазылғандығына байланысты) жалғасқан , , , , бес төбесіне қараңыз. Содан кейін , , , , төбелері 1, 2, 3, 4, 5 түстерімен боялған деп есептейік. Енді -ның 1 және 3 түстерімен боялған төбелерінен және оларды байланыстыратын шеттерден тұратын -ның ішкі графына қарастырайық. Нақтырақ айтқанда, әр шет 1 түсті төбесін 3 түсті төбесімен байланыстырады (бұл Кемпе тізбегі деп аталады). Егер және -ның әртүрлі байланысқан компоненттерінде жатса, онда құрайтын компонентте 1 және 3 түстерін ауыстыруға болады, қалған бөлігінің бояуына әсер етпейді. Бұл -ді 1 түспен бояуға мүмкіндік береді, тапсырманы орындайды. Керісінше, егер және бір байланысқан компонентте жатса, онда оларды 1 және 3 түстерінен ғана тұратын жолмен байланыстыра аламыз. Енді -ның 2 және 4 түстерімен боялған төбелерінен және оларды байланыстыратын шеттерден тұратын ішкі графына көшіңіз және бұрынғы аргументтерді қолданыңыз. Содан кейін біз құрайтын ішкі графтың 2 және 4 түстерін ауыстыра аламыз және -ді 2 түспен бояй аламыз, немесе және -ні тек 2 және 4 түстерінен тұратын жолмен байланыстыра аламыз. Мұндай жол арқылы циклдік ретпен болғандықтан, бұрын салған 1-3 түсті жолмен қиылысады. Бұл графтың жазықтығына қайшы келеді, сондықтан бұл абсурд. Осылайша, шынымен бес түспен боялуы мүмкін, бастапқы болжамға қайшы.

First of all, one associates a simple planar graph to the given map, namely one puts a vertex in each region of the map, then connects two vertices with an edge if and only if the corresponding regions share a common border. The problem is then translated into a graph coloring problem: one has to paint the vertices of the graph so that no edge has endpoints of the same color. Because is a simple planar, i. e. it may be embedded in the plane without intersecting edges, and it does not have two vertices sharing more than one edge, and it does not have loops, then it can be shown (using the Euler characteristic of the plane) that it must have a vertex shared by at most five edges. (Note: This is the only place where the five color condition is used in the proof. If this technique is used to prove the four color theorem, it will fail on this step. In fact, an icosahedral graph is 5 regular and planar, and thus does not have a vertex shared by at most four edges.) Find such a vertex, and call it
Now remove from The graph obtained this way has one fewer vertex than , so we can assume by induction that it can be colored with only five colors. If the coloring did not use all five colors on the five neighboring vertices of , it can be colored in with a color not used by the neighbors. So now look at those five vertices , , , , that were adjacent to in cyclic order (which depends on how we write G). So we can assume that , , , , are colored with colors 1, 2, 3, 4, 5 respectively. Now consider the subgraph of consisting of the vertices that are colored with colors 1 and 3 only and the edges connecting them. To be clear, each edge connects a color 1 vertex to a color 3 vertex (this is called a Kempe chain). If and lie in different connected components of , we can swap the 1 and 3 colors on the component containing without affecting the coloring of the rest of This frees color 1 for completing the task. If on the contrary and lie in the same connected component of , we can find a path in joining them that consists of only color 1 and 3 vertices. Now turn to the subgraph of consisting of the vertices that are colored with colors 2 and 4 only and the edges connecting them, and apply the same arguments as before. Then either we are able to reverse the 2 4 coloration on the subgraph of containing and paint color 2, or we can connect and with a path that consists of only color 2 and 4 vertices. Such a path would intersect the 1 3 colored path we constructed before since through were in cyclic order. This is clearly absurd as it contradicts the planarity of the graph. So can in fact be five colored, contrary to the initial presumption.

Қосымша дәлелдеу

Кейнен (1974) бес түсті теореманың қарапайым дәлелін келтіреді, ол K6 (6 төбесі бар толық граф) жазық еместігі мен граф минорларына негізделген. Бұл дәлел 2 қабырғаны жою арқылы жазықтыққа келтірілетін графтарға да қатысты қолданылады.