что такое грань в графе

§ 37. Грани плоского графа. Формула Эйлера

Гранью плоского графа называется максимальное по включению множество точек плоскости, каждая пара ко­торых может быть соединена жордановой кривой, не пересекающей ребра графа. Тем самым каждая точка плоскости принадлежит хотя бы одной грани плоского

графа. Границей грани будем считать множество вершин иребер, принадлежащих этой грани.

На рис. 37.1 изображен граф с четырьмя гранями. От­метим, что всякий плоский граф имеет одну, и притом единственную, неограниченную грань (на рис. 37.1 грань 4).

Такая грань называется внешней, а остальные грани — внутренними.

Легко видеть, что всякую внутреннюю грань плоско­го графа G можно

преобразовать во внешнюю с помощью стереографической проекции.

Для этого, воспользовав­шись теоремой 36.1, уложим граф G на сфере так,

чтобы северный полюс оказался внутри выбранной грани. Далее рассмотрим стереографическую проекцию G’ графа G на плоскость, касающуюся сферы в южном полюсе, т. е. в точке, диаметрально противоположной северному полюсу. Очевидно, что выбранная грань графа G станет при этом внешней в G’, а внешняя грань графа G — внутренней гранью графа G’, который изоморфен графу G. На рис. 37.2 представлен граф, получающийся из графа, изо­браженного на рис. 37.1, путем такого преобразования. При этом внутренняя грань 1 стала внешней.

Понятие грани естественным образом распространя­ется на псевдо- и мультиграфы (рис. 37.3).

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

Свойство 1. Всякий планарный граф допускает такую плоскую укладку, в которой любая выбранная вершина (ребро) графа будет принадлежать внешней грани.

Свойство 2. Пусть граф G состоит из двух связ­ных компонент G₁ и G₂, являющихся плоскими графами,

и произвольным образом выбраны вершины v₁  VG₁ и v₂  VG₂. Тогда граф G₀, полученный из G слиянием вер­шин v₁ и v₂в вершину v, имеет плоскую укладку. При этом вершина v является точкой сочленения графа G? (рис. 37.4).

Аналогично можно «склеивать» два плоских графа и по ребру.

Свойство 3. Всякие две вершины, принадлежащие границе некоторой грани плоского графа, можно соеди-

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

Отметим, что это свойство является следствием известной теоремы Жордана о кривой.

Свойство 4. Для любого плоского графа каждая точка плоскости, не лежащая на ребре, входит только в одну грань, а каждая точка ребра, не являющаяся вершиной, входит только в одну грань, если это ребро яв­ляется мостом, и точно в две грани, если оно не мост.

Далее будем пользоваться следующими обозначениями: n, m, f—соответственно число вершин, ребер и гра­ней плоского графа.

Теорема Эйлера (1758 г.). Для всякого связного плоского графа верно равенство

Равенство (1) называется формулой Эйлера.

Пусть G — связный плоский n-вершинный граф. Рассмотрим некоторый остов Т этого графа. Очевидно, что дерево Т имеет одну грань (внешнюю) и n вершин. В то же время известно (см. теорему 13.1), что число ребер дерева Т равно n— 1. Поэтому для графа Т фор­мула (1) верна. Теперь будем поочередно добавлять к Т недостающие ребра графа G. При этом на каждом шаге число вершин, естественно, не меняется, а число ребер и число граней увеличивается на единицу на основании свойства 3. Следовательно, формула (1) будет верна для всякого графа, получающегося в результате таких опера­ций (шагов), а поэтому она верна и для графа G, ко­торым заканчивается вся эта процедура.

Из теоремы Эйлера вытекает ряд интересных след­ствий.

Прежде всего, рассмотрим в трехмерном пространстве выпуклый многогранник с n вершинами, m ребрами и I гранями. Очевидно, что спроектировав этот многогранник на описанную около него сферу, далее уложив его так, чтобы северный полюс находился внутри одной из гра­ней, и произведя затем стереографическую проекцию, по­лучим связный плоский граф. Поэтому справедливо

Следствие 37. 1. У всякого выпуклого многогран­ника сумма числа вершин n и числа граней f без числа ребер m равна двум: n + f — m = 2.

Доказательство именно этой формулы и было впервые опубликовано Л. Эйлером в 1758 г. в «Записках Петер­бургской академии наук».

Следствие 37.2. Число граней любой плоский ук­ладки связного планарного (n, т)-графа постоянно и равно m — n + 2.

Не теряя общности, будем считать, что G — плоский граф. Прежде всего заметим, что всякое ребро плоского графа либо разделяет две различные грани, ли­бо является мостом (см. свойство 4). Поскольку G — граф без петель и кратных ребер, то всякая грань ограничена по крайней мере тремя ребрами (исключение составляет лишь случай, когда G — дерево с тремя вершинами, но для такого графа неравенство Зn — 6  т справедливо). Поэтому число 3 является оценкой снизу удвоенного чис­ла ребер графа G, т. е. 3f  2т. Отсюда, учитывая, что по формуле Эйлера f = т — n + 2, приходим к требуемомy неравенству.

Из этого следствия сразу же получаем

Утверждение 37.4. Граф К₅ не планарен.

Действительно, для графа К₅ n = 5, т = 10. По­тому неравенство Зn —6  т превращается в неверное:  10, т. е. граф К₅ не может быть планарным.

Утверждение 37.5. Граф Кз,з не планарен.

Для рассматриваемого графа n = 6, m =9. Поэтому, если бы он был планарным, то для любой его плоской кладки выполнялось бы f = 5 согласно следствию 37.2. В то же время всякая грань двудольного графа Кз,з должна быть ограничена по меньшей мере четырьмя ребрами, следовательно, 2m  4f, т. е. 18  20. Полученное противоречие доказывает утверждение 37.5.

Мы особо останавливаемся на графах K₅ и К_3,3, поскольку, как мы увидим в § 39, эти графы являются мишальными непланарными графами и играют важную роль во многих критериях планарности. Из теоремы Эйлера вытекает также

Следствие 37.6. Если в связном плоском (n,т)- графе граница каждой грани является r-циклом, r  3, m(r-2)=r(n-2).

Так как каждая грань графа ограничена r-циклом, каждое ребро принадлежит ровно

двум граням, т. е.=2m. Подставляя сюда f из формулы Эйлера, получаем искомый

Очевидно, что не всегда граница грани плоского графа является простым циклом (см.,

например, грань 2 на рис. 37.1). Однако для 2-связных графов это так. А именно верна

Теорема 37.7. Плоский граф двусвязен тогда и только тогда, когда границей всякой его грани является простой цикл.

Необходимость. Доказательство проведем от противного. Пусть существует плоский 2-связный граф G, в котором некоторая грань ограничена не простым циклом. Поскольку граф G содержит хотя бы один про­стой цикл, то существует такой максимальный 2-связный подграф Н графа G, что граница каждой его грани яв­ляется простым циклом. При этом Н  G. По лемме 34.7 в G существует H-цепь. Эта простая цепь должна разби­вать некоторую грань плоского графа G на две грани. Очевидно, что каждая из этих граней ограничена простым циклом. Однако это противоречит выбору подграфа G.

Достаточность. Допустим, что плоский граф, каждая грань которого ограничена простым циклом, появляется 2-связным. Тогда граф имеет точку сочленения. Но это значит, что существует грань, ограниченная не­простым циклом.

Теорема 37.8. Связный граф планарен тогда и толь­ко тогда, когда каждый его блок планарен.

Достаточность докажем индукцией по числу блоков k. Если k == 1, то утверждение очевидно. Пусть граф G со­стоит из k > 1 планарных блоков. Согласно утвержде­нию 34.6 существует хотя бы один концевой блок В имеющий точку сочленения v. Поскольку подграф G — — (В — v) содержит k — 1 блоков, то по предположению индукции он планарен. Следовательно, существует такая его плоская укладка, что вершина v находится на внеш­ней грани. Точно так же граф В имеет плоскую укладку с вершиной v на внешней грани. Поэтому объединение-(G — (В — v>) U B, изоморфное графу, имеет плоскую укладку на основании свойства 2.

Из теоремы 37.8 следует, в частности, что для выяс­нения вопросов, связанных с планарностью, достаточно рассматривать лишь 2-связные графы.

Источник

Грань (теория графов)

Плана́рный граф — граф, который можно изобразить на плоскости без пересечений рёбер не по вершинам. Какое-либо конкретное изображение планарного графа на плоскости без пересечения рёбер не по вершинам называется плоским графом. Иначе говоря, планарный граф изоморфен некоторому плоскому графу, изображённому на плоскости так, что его вершины — это точки плоскости, а рёбра — кривые на плоскости, которые если и пересекаются между собой, то только по вершинам. Области, на которые граф разбивает плоскость, называются его гранями. Неограниченная часть плоскости — тоже грань, называемая внешней гранью. Любой плоский граф может быть спрямлён, то есть перерисован на плоскости так, что все его рёбра будут отрезками прямых.

Содержание

Свойства

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

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

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

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

Общая формула также легко обобщается на случай несвязного графа:

Два примера непланарных графов

Полный граф с пятью вершинами

Лемма. Полный граф с пятью вершинами (К₅) нельзя уложить на плоскость.

«Домики и колодцы»

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

Лемма. Полный двудольный граф с тремя вершинами в каждой из долей (К_3,3) нельзя уложить на плоскость.

Доказательство. По формуле Эйлера граф имеет 5 граней.

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

Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных полному графу из пяти вершин (K₅) или графу «домики и колодцы» (K_3,3).

Теорему также можно сформулировать в следующем варианте (иногда его называют «теорема Вагнера»).

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

Компьютерная проверка на планарность

Признаки непланарных графов

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

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

Спрямление графа (теорема Фари). Любой плоский граф можно перерисовать так, чтобы он остался плоским, а рёбра стали отрезками прямых.

Обобщения

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

Тороидальный граф — граф, который можно уложить на тор.

Источник

Грани плоского графа. Формула Эйлера

Гранью плоского графа называется максимальное по включению множество точек плоскости, каждая пара ко­торых может быть соединена жордановой кривой, не пересекающей ребра графа. Тем самым каждая точка плоскости принадлежит хотя бы одной грани плоского

графа. Границей грани будем считать множество вершин и ребер, принадлежащих этой грани.

На рис. 37.1 изображен граф с четырьмя гранями. От­метим, что всякий плоский граф имеет одну, и притом единственную, неограниченную грань (на рис. 37.1 грань 4).

Такая грань называется внешней, а остальные грани — внутренними.

Легко видеть, что всякую внутреннюю грань плоско­го графа G можно

преобразовать во внешнюю с помощью стереографической проекции.

Для этого, воспользовав­шись теоремой 36.1, уложим граф G на сфере так,

чтобы северный полюс оказался внутри выбранной грани. Далее рассмотрим стереографическую проекцию G’ графа G на плоскость, касающуюся сферы в южном полюсе, т. е. в точке, диаметрально противоположной северному полюсу. Очевидно, что выбранная грань графа G станет при этом внешней в G’, а внешняя грань графа G — внутренней гранью графа G’, который изоморфен графу G. На рис. 37.2 представлен граф, получающийся из графа, изо­браженного на рис. 37.1, путем такого преобразования. При этом внутренняя грань 1 стала внешней.

Понятие грани естественным образом распространя­ется на псевдо- и мультиграфы (рис. 37.3).

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

Свойство 1. Всякий планарный граф допускает такую плоскую укладку, в которой любая выбранная вершина (ребро) графа будет принадлежать внешней грани.

Свойство 2. Пусть граф G состоит из двух связ­ных компонент G₁ и G₂, являющихся плоскими графами,

и произвольным образом выбраны вершины v₁ Î VG₁ и v₂ Î VG₂. Тогда граф G₀, полученный из G слиянием вер­шин v₁ и v₂в вершину v, имеет плоскую укладку. При этом вершина v является точкой сочленения графа G? (рис. 37.4).

Аналогично можно «склеивать» два плоских графа и по ребру.

Свойство 3. Всякие две вершины, принадлежащие границе некоторой грани плоского графа, можно соеди-

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

Отметим, что это свойство является следствием известной теоремы Жордана о кривой.

Свойство 4. Для любого плоского графа каждая точка плоскости, не лежащая на ребре, входит только в одну грань, а каждая точка ребра, не являющаяся вершиной, входит только в одну грань, если это ребро яв­ляется мостом, и точно в две грани, если оно не мост.

Далее будем пользоваться следующими обозначениями: n, m, f—соответственно число вершин, ребер и гра­ней плоского графа.

21. Свойства планарных графов

Простейшие свойства плоских графов

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

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

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

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

Общая формула также легко обобщается на случай несвязного графа:

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

Два примера непланарных графов

Полный граф с пятью вершинами

K₅, полный граф с 5 вершинами

Лемма. Полный граф с пятью вершинами (К₅) нельзя уложить на плоскость.

Доказательство. Для него не выполняется .

22. Свойства из теоремы Эйлера

Функция Эйлера показывает, сколько натуральных чисел из отрезка имеют c только один общий делитель — единицу. Функция Эйлера определена на множественатуральных чисел, и значения её лежат в множестве натуральных чисел.

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

В таблице справа представлены первые 99 значений функции Эйлера. Анализируя эти данные, можно заметить, что значение не превосходит , и в точности ему равно, если — простое. Таким образом, если в координатах провести прямую , то значения будут лежать либо на этой прямой, либо ниже её. Также, глядя на график, приведенный в начале статьи, и на значения в таблице, можно предположить, что существует прямая, проходящая через ноль, которая ограничивает значения снизу. Однако, оказывается, такой прямой не существует. То есть, какую бы пологую прямую мы ни провели, всегда найдется натуральное число такое что лежит ниже этой прямой. Ещё одной интересной особенностью графика, является наличие некоторых прямых, вдоль которых концентрируются значения функции Эйлера. Так, например, помимо прямой , на которой лежат значения , где — простое, выделяется прямая, примерно соответствующая , на которую попадают значения , где — простое.

Более подробно поведение функции Эйлера рассматривается в разделе #Асимптотические соотношения.

23. Алгоритм укладки графа на плоскости

Для плоской укладки графа и попутной проверки, планарен ли он, удобно пользоваться гамма-алгоритмом.

На вход подаются графы, обладающие следующими свойствами:

граф имеет хотя бы один цикл;

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

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

Если нарушено свойство (2), то граф — дерево и нарисовать его плоскую укладку тривиально.

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

Сначала изложим алгоритм на конкретном примере. Пусть дан граф G (см. рис. 3).

Инициализация алгоритма производится так: выбираем любой простой цикл; в нашем примере <1, 2, 3, 4, 5, 6, 7, 8>и получаем две грани: Γ₁ — внешнюю и Γ₂ — внутреннюю (см. рис. 4).

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

ребро, оба конца которого принадлежат G ′, но само оно не принадлежит G ′;

Те вершины, которые одновременно принадлежат G ′ и какому-то сегменту, назовем контактными. Для нашего примера сегменты и вершины изображены на рис. 5. Контактные вершины обведены в квадрат.

Если бы в каком-нибудь сегменте не было ни одной контактной вершины, то граф до разрезания был бы несвязный; если бы была только одна, то граф имел бы мостик. Эти возможности заранее исключены, так что каждый сегмент имеет не менее двух контактных вершин. Поэтому в каждом сегменте имеется цепь между любой парой таких вершин.

Общий шаг алгоритма следующий: обозреваются все сегменты S_i и определяются числа |Γ( S_i )|. Если хоть одно из них равно 0, то граф не планарен, конец. Иначе, выбираем сегмент, для которого число |Γ( S )| минимально, или один из множества, если таких сегментов несколько. В этом сегменте найдем цепь между двумя контактными вершинами и уложим ее в любую из граней множества Γ( S ), совместив контактные вершины сегмента с соответствующими вершинами грани. При этом данная грань разобьется на две. Уже уложенная часть графа G ′ по количеству ребер и вершин увеличится, а сегмент, из которого вынута цепь, исчезнет или развалится на меньшие с новыми контактными вершинами, ведущими к вершинам G ′.

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

Вернемся к нашему примеру. Пока для любого i : S_i ⊂<Γ₁, Γ₂>, |Γ( S_i )| = 2. Поэтому возьмем первый по номеру сегмент S_i и в нем первую попавшеюся цепь <4, 8>; вставим эту цепь в грань Γ₂. Получим увеличенную часть G ′ и уменьшенную систему сегментов (см. рис. 6 a, b).

Определим какие грани вмещают новые сегменты. Теперь сегменты S ₁ и S ₂ вмещаются только в одну грань Γ₁, в то время, как сегмент S ₃ вмещается в две грани Γ₁ и Γ₃. Поэтому берем S ₁. Возьмем в нем цепь между контактными вершинами, например, <2, 7>, и уложим ее в Γ₁. Получим увеличенную часть G ′ и уменьшенную систему сегментов (см. рис. 7 a, b).

Продолжая таким образом, в итоге получим плоскую укладку G (см. рис. 8).

Еще раз опишем гамма-алгоритм компактно и займемся его обоснованием.

Гамма-алгоритм

(Инициализация). Выберем любой простой цикл C исходного графа G ; изобразим его на плоскости в виде грани, которую примем за уже уложенную часть G ′; сформируем сегменты S_i ; если множество сегментов пусто, то перейти к п. 3.

(Общий шаг). Пока множество сегментов непусто:

Выбираем один из сегментов с минимальным числом, вмещающих его граней.

Выбираем одну из подходящих граней для выбранного сегмента.

В данном сегменте выбираем цепь между двумя контактными вершинами и укладываем ее в выбранной грани. Учтем изменения в структуре сегментов и перейдем к п. a).

Эйлеров путь (эйлерова цепь) в графе — это путь (цепь), проходящий по всем дугам (рёбрам) графа и притом только по одному разу. (ср. Гамильтонов путь)

Эйлеров цикл — это цикл графа, проходящий через каждое ребро (дугу) графа ровно по одному разу.

Эйлеров граф — граф, содержащий эйлеров цикл.

Полуэйлеров граф — граф, содержащий эйлеров путь (цепь).

Источник