Плоская карта

Cтраница 1

Плоская карта, каждая грань к-рой ограничена тремя ребрами, наз. [1]

Каждая 4-связная плоская карта 4-раскрашиваема. [2]

На конечной плоской карте существует по крайней мере одна область, ограниченная не более чем пятью ребрами. При F - оо среднее число ребер достигает, но не превышает шести. [3]

Мы уже видели, что любая плоская карта 4 -раскрашиваема тогда и только тогда, когда справедлива гипотеза четырех красок. В свою очередь это эквивалентно предложению, что каждая плоская карта, не содержащая мостов, 4-раскрашиваема, так как элементарное стягивание с помощью отождествления висячих вершин моста не изменяет числа областей карты и не нарушает смежности любых ее областей. [4]

С этой целью была построена плоская карта северного полушария. Континенты были сделаны из гипса, океаны заполнялись водою. [5]

Теорема 4.21. Для раскраски граней плоской карты достаточно пяти цветов. [6]

Рассмотрим процесс построения граней на плоской карте, при котором каждая грань смежна с возможно большим числом других граней. [7]

Задача о раскрашивании областей на плоской карте в четыре цвета эквивалентна задаче о раскрашивании в четыре цвета вершин на двойственной карте, так что никакие две вершины, инцидентные с одним и тем же ребром ( так называемые смежные вершины) не могут быть одного цвета. Двойственная карта получается путем сопоставления вершины каждой области и связывания пары вершин ребром, если соответствующие области имеют общую границу. Если соответствующие области имеют кратные граничные линии, то используются кратные ребра. Углы исходной карты, в которых сходятся только два граничных ребра, должны быть преобразованы в единственное граничное ребро. [8]

Ясно, что если 4-раскрашиваема всякая плоская карта, не содержащая мостов, то и всякая кубическая плоская карта, не содержащая мостов, также 4-раскрашиваема. Чтобы проверить обратное, предположим, что G - плоская карта без мостов и что все кубические плоские карты без мостов 4-раскрашиваемы. Так как G не содержит мостов, то в ней нет висячих вершин. Если в G существует вершина v степени 2, инцидентная ребрам у и г, то произведем подразбиение ребер у и г, обозначая дополнительные вершины через и и w соответственно. [9]

Два 4-хроматических пленарных графа. [10]

Обратно, предположим, что каждая плоская карта 4-раскрашиваема. Пусть Я - любой планарный граф, а Я - граф, двойственный к графу Я и нарисованный так, что каждая его область содержит точно одну вершину графа Я. Связный плоский псевдограф Я можно перевести в плоский граф Я, добавляя две новые вершины на каждую петлю графа Я и одну новую вершину на каждое ребро из множества кратных ребер. Теперь 4-раскрашиваемость графа Я означает 4-раскрашиваемость графа Я. Таким образом, эквивалентность обеих формулировок доказана. [11]

Сначала предположим, что G - кубическая плоская карта без мостов, имеющая 4-раскраску. [12]

Два 4-хроматических пленарных графа. [13]

Таким образом, предположение, что каждая плоская карта 4-раскрашиваема, на самом деле эквивалентно приведенной только что формулировке гипотезы четырех красок. Чтобы убедиться в этом, предположим, что гипотеза четырех красок справедлива, и возьмем произвольную плоскую карту G. Пусть G - граф, являющийся основой карты, геометрически двойственной к карте G. Так как две области карты С смежны тогда и только тогда, когда соответствующие им вершины графа G смежны, то карта G 4-раскрашиваема, поскольку граф G 4-раскрашиваем. [14]

ЧЕТЫРЕХ КРАСОК ЗАДАЧА: можно ли области любой плоской карты ( см. Граф плоский) раскрасить четырьмя цветами так, чтобы любые две соседние области были раскрашены в различные цвета. [15]

Страницы: 1 2 3