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

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

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

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

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

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

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

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

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

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

Примеры

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

Гиперграф:

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

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

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

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

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

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

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

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

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

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

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

Примеры

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

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

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

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

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

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

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

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

Пример

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

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

Пример

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

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

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

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

Пример

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