Любой планарный граф

Cтраница 1

Любой планарный граф - раскрашиваем. [1]

В любом планарном графе без петель и кратных ребер существует вершина, степень которой не больше пяти. [2]

Плоские колеса.| Две укладки двусвязного графа на плоскости. [3]

Теорема 11.7. Любой планарный граф изоморфен плоскому графу, у которого все ребра являются отрезками прямых. [4]

Интуитивно очевидно, что любой планарный граф можно уложить на сфере, и обратно. Это замечание позволяет понять, что планарный граф можно уложить на плоскости многими различными способами. [5]

Мы уже видели в теореме 11.11, что любой планарный граф с 9 вершинами имеет непланарное дополнение. Определим толщину 0 ( G) графа G как наименьшее число его планарных подграфов, объединение которых равно G. Действительно, толщина графа / С9 равна 3 и граф / С9 - критический относительно толщины, поскольку 0 ( К. [6]

Используйте исчерпывающий поиск для отыскания наименьшего значения п, такого, что дополнение любого планарного графа 0 ( V, Е) с I V n непланарно. [7]

Алгоритм последовательной раскра-спи вершин, основанный на ПН-упорядочении вершин с пошаговой перекраской, требует не более 5 цветов для раскраски любого планарного графа. [8]

Доказательство теоремы ведется индукцией по числу вершин. Для любого планарного графа с и 5 вершинами результат тривиален, так как любой граф п-раскрашиваем. Допустим, что все планарные графы с п вершинами, п 5, 5-раскрашиваемы. [9]

Будем доказывать индукцией по числу р вершин. Для любого планарного графа с р 5 вершинами результат тривиален, поскольку такой граф / - раскрашиваем. [10]

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

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

Карта и соответствующий ей граф. [13]

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

Страницы: 1