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

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

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

На рис. 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 – G′, дополненную всеми ребрами графа G, один из концов которых принадлежит связной компоненте, а второй из графа G′.

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

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

Если все контактные вершины сегмента S имеют номера вершин какой-то грани Γ, то мы будем говорить, что грань Γ вмещает этот сегмент и обозначать S⊂Γ. Может быть имеется не одна такая грань, вмещающая сегмент S, множество таких граней обозначим Γ(S), а их число |Γ(S)|.

Общий шаг алгоритма следующий: обозреваются все сегменты 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.

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

Для каждого сегмента S найти множество Γ(S). Если существует сегмент S, для которого |Γ(S)| = 0, то граф не планарный, конец.

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

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

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

(Завершение). Построена плоская укладка G′ исходного графа G, конец.

 

24. Эйлеров граф

 

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

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

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

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

Теоре́ма Э́йлера в теории чисел гласит:

Если и взаимно просты, то , где — функция Эйлера.

 

 

Поделиться:

Воспользуйтесь поиском по сайту: