• Определение №1: (Карта)
Карта - это связный плоский граф без мостов.
• Определение №2: (Смежные грани карты)
2 грани карты G называются смежными, если имеют, по крайней мере, одно общее ребро.
• Определение №3: (k-раскраска карты)
Ф-ция f явл-ся отображением граней карты на мн-во натуральных чисел {1,2,...,k} наз-ся k-раскраской карты (если цвета смежных граней различны).
В этом случае говорим, что карта k-раскрашиваемая.
f(Г) принадлежащее {1,2,...,k} наз-ся цветом грани Г.
*** Задача о 4-ех красках ***
В 1898 году А.Кэли сформулировал "гипотезу 4-ех красок":
всякая карта 4-раскрашиваемая.
• Определение №4: (Геометрический двойственный граф)
Пусть дана карта G.
Выберем в карте G внутри каждой грани по точке.
Граф G*, мн-вом в-н которого явл. мн-во выбранных точек в карте G и любые 2 в-ны которого смежны <=> когда они соответствуют точкам, принадлежащим смежным граням карты называется геометрически двойственным графом.
• Теорема №1:
Граф G являющийся картой k-раскрашиваем <=> когда геометрически двойственный граф G* вершинно k-раскрашиваем.
-> Док-во:
Пусть карта G k-раскрашиваема.
Каждой в-не графа G* присвоем цвет грани, в которой она расположена.
Т.к. 2 смежные в-ны графа G* соответствуют 2-ум смежным граням карты G, то в-ны раскрашены различными цветами.
Т.О. построенная вершинная раскраска графа G* будет правильной.
*** Теорема Хивуда ***
• Теорема №2: (Теорема Хивуда)
Любой планарный граф 5-раскрашиваемый.