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

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

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

Основные объекты графов

- носитель метаграфа (конечное множество вершин). .- сигнатура метаграфа (конечное множество связей между вершинами)..

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

Для графа:- множество ребер, связывающих две вершины..

Для орграфа (ориентированный граф):- множество дуг..

Для гиперграфа (мограф – модельный граф):- множество граней..Грань– подмножество вершин мографа.

Примеры

Граф:
Орграф:

Гиперграф:

Если вершины иявляются концевыми для некоторого ребра, то говорят, что онисмежны. Если два ребра имеют общую концевую вершину, то они такжесмежны. Если вершина является концевой для некоторого ребра, то говорят, что ониинцидентны.

Все введенные ранее графы можно было бы разделить на три категории.

некоторые множества

Способы задания графов

1. Графический способ задания графов.

2. Матрица смежности (для вершин). Для графа:Для орграфа:

3. Матрица инциденций. Для графа: Для орграфа:

4. Функциональный способ задания графов.,- функция окрестности вершин.Для орграфа:- функция положительной полуокрестности.- функция отрицательной полуокрестности.

Изоморфизм на графах

Два графа (орграфа) иизоморфны, если существует взаимнооднозначная функциятакая, что: 1) еслиисмежны в, тоисмежны в; 2) еслиисмежны в, тоисмежны в.

Изоморфизм обладает свойствами рефлексивности, симметричности, транзитивности, следовательно обладает свойством эквивалентности на множестве графов.

Примеры

Графы не являются изоморфными.

		Графы изоморфны.

Матрица инциденций и матрица смежности задают граф с точностью до изоморфизма.

Количественная или качественная характеристика, неизменная для всех изоморфных между собой графов называется инвариантом графа. Поиск этих инвариантов – основная задача теории графов.

Элементы графов

Пусть - некоторый граф. Графназываетсячастичным графомграфа, если, а. Графназываетсяподграфомграфа(), если: 1); 2) из смежности виследует смежностьив. Графназываетсячастичным подграфомграфа, если он является частичным графом подграфа графа.

Степень вершины. Степень графа

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

Пример

Теорема Сумма степеней вершин графа есть число четное:.СледствиеЧисло вершин с нечетными степенями – четно.

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

Пример

Регулярный граф степени 2

Для орграфов:

- полустепень исхода.-полустепень входа.

ТеоремаДля любого орграфа.

Пример

Распределение степеней вершин совпадает, но графы не изоморфны.

Типы графов

1. Граф и ограф.

2. -граф (граф, построенный на вершинах иребрах).

3. Полный граф на вершинах(все вершины смежны между собой).Пример ()

4. Тривиальный граф (граф, состоящий из одной вершины).

5. Пустой граф (граф навершинах, не содержащий ни одного ребра)

6. Двудольный граф (граф называется двудольным, еслиии).Примеры

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