Вопросы для повторения.

1. Дерево. Лес. Теорема о дереве. Ориентированное дерево (ордерево). Теорема Кэли.

2. Остовный подграф. Остовное поддерево (остовный каркас). Теорема Кирхгофа. Теорема о числе рёбер неориентированного графа, которые необходимо удалить для получения остова и следствия из неё. Цикломатическое число (циклический ранг) графа. Коциклический ранг (коранг).

3. Алгоритм Прима (алгоритм ближайшего соседа).

4. Эйлеров граф. Гамильтонов граф. Необходимое и достаточное условие эйлеровости связного графа.

5. Алгоритм Флери. Перешеек.

6. Покрытие графа . Теорема о покрытии.

7. Достаточное условие гамильтоновости. Теорема Оре и следствие из неё. Теорема о связном орграфе. Необходимое и достаточное условие существования открытой эйлеровой цепи в связном орграфе.Достаточные условия гамильтоновости орграфа. Ветви и хорды остова. Фундаментальный цикл. Фундаментальное множество циклов.

8. Независимое (внутренне устойчивое) множество вершин графа. Максимальное независимое множество. Число (вершинной) независимости (неплотность) графа. Теорема о неплотности. Доминирующее (внешне устойчивое) множество вершин графа. Минимальное и наименьшее доминирующее множество. Число доминирования графа. Признак максимальности независимого множества. Клика. Максимальная и наибольшая клики. Кликовое число (плотность)графа. Признак клики. Алгоритм выделения клик в графе. Матрица клик.

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

1. Для графа G, заданного матрицей весов, построить минимальный по весу остов и найти его вес .

.

2. Используя матричную теорему Кирхгофа, найти число остовных деревьев в полном двудольном графе K_m,n.

3. Найти матрицу фундаментальных циклов, радиус и диаметр графа, изображённого на рис. 50. Является ли изображённый граф эйлеровым или гамильтоновым?

Рис. 50

4. Доказать, что если для любых двух несмежных вершин x и y связного n-вершинного графа выполняется условие то граф имеет гамильтонов цикл.

По алгоритму Флери найти эйлеров цикл в графе, изображённом на рис. 51.

x₃

x₁

x₂

x₄

x₅

x₆

Рис. 51

5. Н айти наибольшее независимое множество вершин в графе Петерсена (рис. 52).

Рис. 52

6. Показать, что граф Петерсена не гамильтонов.

7. Найти число доминирования и наименьшее доминирующее множество графа, представленного на рис. 53.

Рис. 53

8. Приведите пример графа, в котором наименьшее доминирующее множество не является независимым.

Глава 4. Планарные графы

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

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

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

Плоским графом называется граф, вершины которого являются точками плоскости, а рёбра – непрерывными плоскими линиями без самопересечений, причём никакие два ребра не имеют общих точек, кроме инцидентной им обоим вершины.

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

Все планарные графы укладываются на плоскости (имеют плоскую укладку). На следующем рисунке изображён планарный граф G и его плоская укладка .

Рис. 54

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

1. Всякий подграф планарного графа планарен.

2. Граф планарен тогда и только тогда, когда каждая компонента связности этого графа – планарный граф.

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

Границей грани называется множество вершин и рёбер, принадлежащих этой грани.

Например, граф на предыдущем рисунке имеет 8 граней: Г₁,Г₂,…,Г₈. Неограниченная грань Г₁ называется внешней, а остальные грани Г₂,…,Г₈ – внутренними.

Пусть n, m, f – соответственно число вершин, рёбер и граней планарного графа.

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

. (1)

Гомеоморфизм графов.

Рассмотрим операцию подразбиения ребра в графе . После разбиения ребра получается граф т.е. ребро заменяется на - цепь длины два.

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

Рис. 55

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

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

Рис. 56

Эквивалентная форма критерия планарности.

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

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

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

Теорема. Для числа планарности полного графа справедлива формула:

(2)

Толщиной t(G) непланарного графа G называется наименьшее число планарных подграфов графа G, объединение которых даёт сам граф. Толщина графа равна минимальному числу плоскостей ℓ, при котором граф G разбивается на плоские части G₁,G₂,…,G_ℓ. Толщина планарного графа равна 1.

Теорема. Для толщины связного (n,m) – графа справедливы оценки:

(3)

где в квадратных скобках записаны целые части указанных выражений.