Планарность

Планарность

Планарный граф — граф, который может быть изображен на плоскости без пересечения ребер.

Более строго: Граф укладывается на некоторой поверхности, если его можно на ней нарисовать без пересечения ребер. Уложенный граф называется геометрическим, его вершины это точки плоскости, а ребра линии на ней, области, на которые граф разбивает поверхность называются гранями. Плоский граф — граф уложенный на плоскость. Граф называется планарным, если он изоморфен некоторому плоскому графу.

Содержание

Критерий непланарности

K5, полный граф с 5 вершинами
K3,3, граф, иллюстрирующий задачу о трех колодцах
  • достаточное условие — если граф содержит двудольный подграф K3,3 или полный подграф K5, то он является не планарным;
  • необходимое условие — если граф не планарный, то он должен содержать больше 4 вершин, степень которых больше 3, или больше 5 вершин степени больше 2.

Теорема Понтрягина-Куратовского

Граф планарен тогда и только тогда, когда не содержит подграфов, гомеоморфных K5 или K3,3.

  • Вариант

Граф планарен тогда и только тогда, когда он не содержит подграфов, стягиваемых в K5 или K3,3.

Формула Эйлера

Для связного плоского графа справедливо следующее соотношение между количеством вершин V, ребер E и граней F:

VE + F = 2

Оно было найдено Эйлером в 1736 г.[1] при изучении свойств выпуклых многогранников. Это соотношение справедливо и для других поверхностей с точностью до коэффициента, называемого эйлеровой характеристикой. Это инвариант поверхности, для плоскости или сферы он равен двум.

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

E \le 3V-6

то есть, при большем числе ребер граф заведомо непланарен. (Обратное утверждение не верно, пример.) Отсюда следует, что в планарном графе всегда можно найти вершину степени не более 5.

Планарные графы в задачах

Задача о трех колодцах. Есть три дома и три колодца. Доказать, что невозможно так проложить дорожки между домами и колодцами, чтобы от каждого дома к каждому колодцу вела дорожка, и никакие две дорожки не пересекались бы. (Мосты строить нельзя.)

Раскраска карты. Необходимо раскрасить плоскую карту заданным числом красок так, что любые две страны имеющий общий участок границы имели различные цвета. Оказывается, что при отсутствии анклавов, всегда достаточно четырех красок, но это утверждение чрезвычайно сложно доказать, см. Проблема четырёх красок.

См. также

Примечания

  1. Ф. Харари Теория графов УРСС стр. 126

Ссылки



Wikimedia Foundation. 2010.

Поможем студентам с решением задачи

Полезное


Смотреть что такое "Планарность" в других словарях:

  • Киприанов, Андрей Иванович — [р. 4 (16) июля 1896] сов. химик органик, акад. АН УССР (с 1945). В 1919 окончил Харьков. ун т, где работал до 1941 (с 1940 проф.). С 1944 проф. Киев. ун та; одновременно (с 1945) дир. Ин та органич. химии АН УССР. Осн. работы выполнены в области …   Большая биографическая энциклопедия

  • ИНТЕГРАЛЬНАЯ СХЕМА — твердотельное устройство, содержащее группу приборов и их соединения (связи), выполненное на единой пластине (подложке). В И. с. интегрируются пассивные элементы (ёмкости, сопротивления) и активные элементы, действие к рых основано на разл. физ.… …   Физическая энциклопедия

  • ГИПЕРГРАФ — обобщение понятия графа. Г. задается множеством V, элементы к рого наз. вершинами, и семейством подмножеств множества V, называемых ребрами Г.; Г. обозначается Понятие Г. является вариантом давно известных понятий комплекса, блок схемы, а также… …   Математическая энциклопедия

  • Теория графов — Граф с шестью вершинами и семью рёбрами Теория графов  раздел дискретной математики, изучающий свойства графов. В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами. В строго …   Википедия

  • Планарный граф — Планарный граф  граф, который может быть изображен на плоскости без пересечения ребер. Более строго: Граф укладывается на некоторой поверхности, если его можно на ней нарисовать без пересечения ребер. Уложенный граф называется геометрическим …   Википедия

  • Гамма-алгоритм — Гамма алгоритм  алгоритм плоской укладки графа и проверки его на планарность. Содержание 1 Определения 2 Алгоритм 3 Реализация …   Википедия

  • Гипотеза Хадвигера — Не следует путать с проблемой Нелсона  Эрдеша  Хадвигера. Гипотеза Хадвигера  одна из неразрешённых гипотез теории графов. Она формулируется следующим образом: всякий k хроматический граф стягиваем к полному графу на вершинах.… …   Википедия

  • Система графов — Системой графов является такая совокупность или множество графов, где между элементами зафиксировано соотношение. Графы систематизируются исходя из характеристик, чаще всего, таких как планарность, регулярность, транзитивность и т.д. Большая… …   Википедия

Книги



Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»