Как определить является ли граф планарным

Как доказать планарность графа

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

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

Содержание

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

• достаточное условие — если граф содержит двудольный подграфK_3,3 или полный подграфK₅, то он является не планарным;
• необходимое условие — если граф не планарный, то он должен содержать больше 4 вершин, степень которых больше 3, или больше 5 вершин степени больше 2.

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

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

• Вариант

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

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

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

V − E + F = 2

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

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

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

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

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

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

См. также

Примечания

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

Ссылки

• А. Ю. Ольшанский. Плоские графы,СОЖ, 1996, No 11, с. 117—122.
• Ф. Харари. Теория графов. М.: «Мир». 1973

Wikimedia Foundation . 2010 .

Полезное

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

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

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

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

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

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

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

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

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

Проверка графа на планарность

Определение. Любой граф, гомеоморфный плоскому, называется планарным. Говорят, что граф допускает плоскую укладку, если его можно изобразить как плоский. Например, граф, показанный на рис.1, плоский.

Рис. 1

Существуют также и непланарные графы. На рис.2 показаны два таких графа: полный пятивершинник и полный двудольный граф. Для них есть специальные обозначения: K₅ и K_3,3 соответственно.

Рис. 2

Теорема. Граф является планарным, если не содержит в себе подграфов, гомеоморфных K₅ или K_3,3.

52. Планарные графы. Критерий планарности.

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

Рис. 1.24. Примеры планарного и непланарных графов: а — планарная укладка с непрямолинейными ребрами; б — планарная укладка того же графа с прямолинейными ребрами; в — непланарный граф K₅;

г — непланарный граф K_3,3

Теорема. Граф планарен тогда и только тогда, когда он не содержит в качестве подграфа графа или.До появления этой теоремы определение планарности графа считалось одной из труднейших задач теории графов.

На рис. 1.25 приведен непланарный граф Петерсена.

Рис. 1.25. Непланарность графа Петерсена:

а — граф Петерсена; б — граф Петерсена, стянутый к K₅; в — один из подграфов графа Петерсена, гомеоморфный K_3,3

Граф Петерсена не имеет подграфов, гомеоморфных K₅, но легко стягивается к K₅. Сложнее увидеть, что граф Петерсена имеет подграф, гомеоморфный K_3,3.

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

Доказательство: необходимости. С геометрической точки зрения, добавление вершины степени 2 — это добавление точки на ребре, а стирание такой вершины объединяет два ребра с общим концом в одно.

Очевидно, что любая из этих операций, примененная к плоскому графу, снова даст плоский граф. Значит, по следствиям из теоремы Эйлера, никакой плоский (а следовательно, и планарный) граф не гомеоморфен графам K₅ и K_3,3. С учетом замечания о непланарных подграфах, необходимость доказана.

Граф Петерсена

54.Двухполюсные сети. Параллельно-последовательные сети. Поток в сети.

Опр. (k,l) – полюсником называется сеть имеющая k+l полюсов разбитых на два класса: k-входных полюсов, l – выходных полюсов.

(1,1)-полюсник называется двухполюсной сетью.

Цепью называют простую цепь между полюсами сети(S). – входной, выходной полюс. Полюсные ребра-Z.

Сеть состоящая из n параллельных ребер, соединяющих полюса обозначается через.

Сеть, которая может быть получена из сетей иприменением конечного числа операций подстановки сети вместо ребра называетсяпараллельно-последовательной сетью.

Опр. Сетью называется связный ориентированный граф G(V, E) без петель с выделенными вершинами  истоком и  стоком, причем каждой дуге поставлено в соответствие некоторое натуральное число –пропускная способность дуги.

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

Поток в сети определяет способ пересылки некоторых объектов из одной вершины графа в другую по направлению дуги. Число объектов (количество вещества) , пересылаемых вдоль дуги, не может превышать пропускной способностиэтой дуги:. Будем считать, что если существует дуга изв, то нет дуги изв. Таким образом, рассматривается поток вещества только в одну сторону.

52. Планарные графы. Критерий планарности.

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

Рис. 1.24. Примеры планарного и непланарных графов: а — планарная укладка с непрямолинейными ребрами; б — планарная укладка того же графа с прямолинейными ребрами; в — непланарный граф K₅;

г — непланарный граф K_3,3

Теорема. Граф планарен тогда и только тогда, когда он не содержит в качестве подграфа графа или.До появления этой теоремы определение планарности графа считалось одной из труднейших задач теории графов.

На рис. 1.25 приведен непланарный граф Петерсена.

Рис. 1.25. Непланарность графа Петерсена:

а — граф Петерсена; б — граф Петерсена, стянутый к K₅; в — один из подграфов графа Петерсена, гомеоморфный K_3,3

Граф Петерсена не имеет подграфов, гомеоморфных K₅, но легко стягивается к K₅. Сложнее увидеть, что граф Петерсена имеет подграф, гомеоморфный K_3,3.

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

Доказательство: необходимости. С геометрической точки зрения, добавление вершины степени 2 — это добавление точки на ребре, а стирание такой вершины объединяет два ребра с общим концом в одно.

Очевидно, что любая из этих операций, примененная к плоскому графу, снова даст плоский граф. Значит, по следствиям из теоремы Эйлера, никакой плоский (а следовательно, и планарный) граф не гомеоморфен графам K₅ и K_3,3. С учетом замечания о непланарных подграфах, необходимость доказана.

Граф Петерсена

54.Двухполюсные сети. Параллельно-последовательные сети. Поток в сети.

Опр. (k,l) – полюсником называется сеть имеющая k+l полюсов разбитых на два класса: k-входных полюсов, l – выходных полюсов.

(1,1)-полюсник называется двухполюсной сетью.

Цепью называют простую цепь между полюсами сети(S). – входной, выходной полюс. Полюсные ребра-Z.

Сеть состоящая из n параллельных ребер, соединяющих полюса обозначается через.

Сеть, которая может быть получена из сетей иприменением конечного числа операций подстановки сети вместо ребра называетсяпараллельно-последовательной сетью.

Опр. Сетью называется связный ориентированный граф G(V, E) без петель с выделенными вершинами  истоком и  стоком, причем каждой дуге поставлено в соответствие некоторое натуральное число –пропускная способность дуги.

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

Поток в сети определяет способ пересылки некоторых объектов из одной вершины графа в другую по направлению дуги. Число объектов (количество вещества) , пересылаемых вдоль дуги, не может превышать пропускной способностиэтой дуги:. Будем считать, что если существует дуга изв, то нет дуги изв. Таким образом, рассматривается поток вещества только в одну сторону.

Проверка планарности графа

Проверка планарности графа — это проверка возможности отображения данного графа на плоскости без пересечения ребер.

Введение

Проблема определения планарности графа может быть отнесена к самым важным задачам систем автоматизированного проектирования (САПР), она заключается в определении специального представления графа, при котором ребра исследуемого графа не имеют взаимных пересечений.

Это означает, что формирование рисунка плоского графа и визуализация его изображения считаются одними из самых важных подзадач, которые возникают при разрешении большинства актуальных прикладных проблем. К примеру, это может потребоваться для визуализации разных производственных задач, а также при формировании систем автоматизации проектирования плоских конструктивов. Здесь под плоским конструктивом следует понимать техническое устройство, то есть конструкцию, в которой непересекающиеся соединения среди элементов устройства и сами элементы располагаются в параллельных (эквидистантных) плоскостях.

В качестве такого устройства может выступать печатная плата, интегральная микросхема, БИС, СБИС и так далее. Существует метод проверки планарности графа с одновременным формированием математических структур, предназначенных для описания топологического рисунка графа с целью его визуализации. Метод базируется на создании системы изометрических циклов, понятии вращения вершин графа, а также задании операции определения пересечения ребер в виде пересечения их проекций на координатно-базисную систему, в качестве которой может использоваться опорный цикл DFS-дерева (Depth-first search, то есть, поиска в глубину) графа.

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

где m является количеством вершин графа.

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

Проверка планарности графа

Предположим, что имеется произвольный граф G. Путем последовательного просмотра всех вершины графа, следует удалить петли, «висячие» вершины и кратные ребра, если они присутствуют в графе. Далее следует удалить мосты и точки сочленения, что позволяет получить несколько компонент связности, которые могут рассматриваться по отдельности. Пара ребер, которые соединены одной вершиной, имеющей локальную степень равную двум, следует заменить одним ребром. Подразумевается, что эти преобразования необходимо запомнить, для того чтобы впоследствии можно было восстановить первоначальный вида графа G после его проверки.

Несепарабельным графом G называется связный неориентированный граф, не имеющий петель и кратных ребер, а также не имеющий мостов и точек сочленения, вершин с локальной степенью меньшей или равной двум. К подобным несепарабельным графам, для того чтобы определить их планарность, может быть использован критерий планарности Маклейна, а также операция кольцевого суммирования суграфов в подпространстве циклов.

Пусть G = (X,U) является несеперабельным графом, имеющим пронумерованные множество ребер:

При этом card X = n и card U = m.

Как правило, граф G может быть представлен матрицей инциденций или матрицей смежностей. Графически граф можно представить в виде диаграммы, в которой вершины изображены точкой или кружком, а ребра представлены отрезками линий, которые соединяют вершины. На рисунках ниже представлены различные возможные диаграммы графа G.

Рисунок 1. Диаграмма графа G. Автор24 — интернет-биржа студенческих работ

Рисунок 2. Диаграмма графа G. Автор24 — интернет-биржа студенческих работ

Рисунок 3. Диаграмма графа G. Автор24 — интернет-биржа студенческих работ

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

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

Цикломатическое число должно определять число независимых циклов графа:

Кольцевая сумма независимых циклов способна определить обод. На рисунке ниже показано задание направления обхода ребер в циклах.

Рисунок 4. Задание направления обхода ребер в циклах. Автор24 — интернет-биржа студенческих работ

Если выполнить задание направления обхода ребер в циклах, соблюдая условия планарности Маклейна, то тогда следует записывать циклы как кортежи вершин:

Рисунок 5. Циклы как кортежи вершин. Автор24 — интернет-биржа студенческих работ

Но если взглянуть с обратной стороны, то задаваемое подмножество циклов, имеющее заданное направление обхода ребер, способно породить (индуцировать) некоторый циклический порядок распределения смежных вершин для каждой из вершин. На рисунке ниже показано вращение вершины $х_1$.

Рисунок 6. Вращение вершины х1. Автор24 — интернет-биржа студенческих работ

Для заданного графа G вращением вершины А графа G является ориентированный циклический порядок (или циклическая перестановка) всех ребер, которые являются инцидентными к вершине А. Вращение графа следует описать и представить следующим образом. Введем обозначения вершин как $x_1, x_2, . x_n$. Далее запишем циклическую перестановку соседей для всех вершин $x_i$. Эта перестановка определяется вращением вершины $x_i$, являющимся циклической перестановкой ребер, которые инцидентны вершине $x_i$.

Проверка графа на планарность

Определение. Любой граф, гомеоморфный плоскому, называется планарным. Говорят, что граф допускает плоскую укладку, если его можно изобразить как плоский. Например, граф, показанный на рис.1, плоский.

Рис. 1

Существуют также и непланарные графы. На рис.2 показаны два таких графа: полный пятивершинник и полный двудольный граф. Для них есть специальные обозначения: K₅ и K_3,3 соответственно.

Рис. 2

Теорема. Граф является планарным, если не содержит в себе подграфов, гомеоморфных K₅ или K_3,3.