Задачи для самостоятельного решения.

1. Оценить хроматическое число h(G) графа G = < V, U > , у которого

V = {1,2,3,4,5,6}, U= {(1,2),(1,6), (2,3), (2,4),(2,6) (3,4),(4,5), (4,6), (5,6)}.

2. Определить хроматическое число графа G, заданного в задаче 1.

3. Найти хроматический класс графа G, заданного в задаче 1.

4. Построить для графа G, заданного в задаче 1, граф = < , > и показать, что H(G)= h( ).

5. Построить граф F₅ и проверить на нем т.2.7.

3. Планарность графа.

Графы G и изоморфны, если для них сохраняется отношение инцидентности (коинцидентности).

Пример 1. Являются ли графы G (рис. 3.1а) и (рис. 3.1б) изоморфными?

v₃ u₄ v₄ u₃

u₃ u₅

u₁ u₆ u u₆ u₆

v₃ v₁

v₁ u₂ v₂

u₅ u₅ u₅ u₅

u₄ uu u₁

G

v₄

а)

б)

Рис. 3.1

Проверим, например, для этих графов сохранение отношения коинцидентности.

Граф G:

вершина v₁ коинцидентна ребрам u₁, u₂, u₃;

вершина v₂ коинцидентна ребрам u₂, u₅, u₆;

вершина v₃ коинцидентна ребрам u₃, u₄, u₆;

вершина v₄ коинцидентна ребрам u₁, u₄, u₅.

Граф :

вершина v₁ коинцидентна ребрам u₁, u₂, u₃;

вершина v₂ коинцидентна ребрам u₂, u₅, u₆;

вершина v₃ коинцидентна ребрам u₃, u₄, u₆;

вершина v₄ коинцидентна ребрам u₁, u₄, u₅.

Отношение коинцидентности выполняется, значит, графы G и

изоморфны. ■

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

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

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

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

Граф, гомеоморфный планарному графу, также является планарным.

Пример 2. Являются ли граф G (рис. 3.2а) и граф (рис. 3.2б) гомеоморфными?

v₃ u₄ v₆ u₇ v₄ v₅

u₂ u₉ u₈ u₃

v₅ v₇

u u₆ u₆

u₆ v₃ v₁

u₃ u₁

u₇7

u₅ u₅ u₅ u₅

v₁ u₂ v₂ u₄ u u₁

G

v₄

а)

б)

Рис. 3.2

Графы G и являются гомеоморфными, т.к. после удаления в графе G

вершин второй степени v₅, v₆, v₇ и объединения инцидентных этим вершинам ребер u₃ и u₈, u₄ и u₇, u₁ и u₉ и после удаления в графе вершин второй степени v₅, v₆ и объединения инцидентных этим вершинам вебер u₃ и u₈, u₅ и u₇ рафы G и оказываются изоморфными. Это следует из примера 1. ■

Теорема 3.1 (теорема Л.С. Понтрягина). Граф планарен тогда и только тогда, когда он не содержит подграфа, гомеоморфного F₅ или К_3,3.

Граф F₅ – минимальный полный граф, который не является планарным (рис. 3.3а). Удаление одного ребра делает этот граф планарным.

Граф К_3,3 – минимальный полный граф, который не является планарным (рис. 3.3б). Удаление одного ребра делает этот граф планарным.

Графы F₅ и К_3,3 называют часто запрещенными фигурами.

К_3,3

F₅

Рис. 3.3

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

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

Толщина планарного графа равна 1.

Нижняя оценка толщины t(G) графа G = < V, U > определяется неравенством

t(G) 1 + , (3.1)

где - ближайшее целое число, n=|v|, S_i - степень i–ой вершины.

Отметим, что для строгого доказательства планарности графа используется теорема Понтрягина, соотношение (3.1) лишь только нижняя оценка толщины графа.

Пример 3. Является ли граф G (рис. 3.4) планарным? Если нет, то определить, какие ребра необходимо удалить (реализовать на других плоскостях) для преобразования графа G в планарный.

G

Рис. 3.4

Согласно теореме 3.1 проверим графа G на содержание подграфа, гомеоморфного F₅.

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

В графе F₅ все вершины имеют степень, равную 4, значит, в графе

G можно удалить вершину 1 с инцидентным ей ребрами, т.к. степень вершины 1 равна 3. Дальнейшие преобразования показаны на рис. 3.5.

Рис. 3.5

В результате получили подграф, гомеоморфный F₅ , т.е. заданный

граф G не является планарным. Удаление любого ребра в полученном подграфе делает его (подграф) планарным.

Теперь проверим граф G на содержание подграфа, гомеоморфного

К_3,3. Попытаемся привести граф G к виду К_3,3.

В графе К_3,3 все вершины имеют степень, равную 3. В графе G степень вершин больше или равна 3, поэтому в процессе преобразования графа G вершины удалять не будем. Сведение графа G к виду графа К_3,3 показано на рис. 3.6.

Рис. 3.6

В результате получен подграф, гомеоморфный К_3,3. Удаление любого ребра в полученном подграфе делает его планарным.

Определим нижнюю оценку графа G:

t(G) 1+ =2, т.е. t(G) 2.

Вывод: заданный граф G содержит подграфы, гомеоморфные F₅ и К_3,3, толщина графа G не меньше двух, значит, граф G непланарный.

Так как удаление любого ребра выводит запрещенную фигуру (полученные подграфы) из класса подграфов, гомеоморфных F₅ и К_3,3, то граф G станет планарным; если удалить ребро, входящее как в подграф, гомеоморфный F₅ , так и в подграф, гомеоморфный К_3,3.

Такими общими ребрами являются ребра (2,3), (2,4), (3,6), (4,5),(4,6), (5,7). Удаление любого из этих ребер делает граф планарным.

После удаления, например, для определенности ребра (3,6) получаем планарный граф, плоское представление которого изображено на рис. 3.7. Соединение, которое соответствует удаленному ребру (показано пунктирной линией), реализуется на второй плоскости. Толщина t(G) графа G равна 2. ■

G

Рис.3.7

Задачи для самостоятельного решения.

1. И зоморфны ли графы, изображенные на рис. 3.8?

b

a d b f c

c c e

g e

g f d g d

b a a

e

G₁ G₂ G₃

Рис. 3.8

2. Покажите, что графы, изображенные на рис. 3.9., гомеоморфные.

Рис. 3.9

3. Покажите, что приведенные на рис. 3.9 графы непланарные. Какое минимальное число ребер необходимо удалить, чтобы они стали планарными.

4. Найти нижнюю оценку толщины графов, изображенных на рис. 3.9.

5. Задача о трех домах и трех колодцах: можно ли продолжить от домов к каждому колодцу дороги так, чтобы они не пересекались (враждующие соседи должны иметь возможность пользоваться всеми колодцами, но не хотят встречаться на дороге)?

СПИСОК ЛИТЕРАТУРЫ

1. Горбатов В.А. Основы дискретной математики. – М.: Высшая школа, 1986. – 311 с.

2. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат, 1986 – 480с.

3. Коршунов Ю.М. Математические основы кибернетики. – М.: Энергоатомиздат, 1987 – 496с.

4. Сигорский В.П. Математический аппарат инженера. – Киев: Технiка, 1975. – 768 с.

СОДЕРЖАНИЕ.

1. Устойчивость, покрытия, паросочетания…………………………….