Дискретная математика: теория графов

Пример

Данный курс был прочитан для студентов второго курса факультета "К" групп К2-221, 222, 224, 281, 331 и 361 в весеннем семестре 2005/2006 учебного курса доц. каф. Кибернетики Порешиным П.П.

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

В этом файле содержится вторяя конспекта

:

:

Выделяем пустые подграфы:

Реберные графы. Графы со свойством реберности

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

Пример

(это преобразование можно выполнить всегда)

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

Пример

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

Замечание 1. Не для любого графа существует такое разложение ребер. 2. В разложении ребер каждое ребро принадлежит ровно одному подграфу.

Пример

Пример

не являются реберными

Если граф обладает свойством реберности, то как найти его образ (т.е. граф, для которого данный является реберным)?

Пример

:

:

Пример

Укладки графа. Планарность

Исследуются топологические свойства графа. Гомеоморфизм графов – еще одно отношение эквивалентности на графах. Два графа и гомеоморфны, если они изоморфны с точностью до цепей степени 2.

Пример

:	:
Гомеоморфны. Говорят, что они имеют одну и ту же топологию.

Пусть - некоторая поверхность. Род поверхности - это максимальное число простых замкнутых кривых, не разделяющих эту поверхность.

Род плоскости: 0
Род сферы: 0
Род тора: 1

Поверхности, которые имеют род 4:

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

Пример

Граф называется планарным (плоским), если .

• печатные платы – планарные графы;

• микросхемы (на уровне технологии их изготовления) – планарные графы.

Критерий планарности графа (критерий Понтрягина-Куратовского)

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

Алгоритм приведения графа к планарному

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

Раскраска графов

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

Хроматическое число пустого графа равно 1. Хроматическое число . Хроматическое число .