Лекции. Теория графов и комбинаторика (стр. 1 )

МОСКОВСКИЙ ЭНЕРГЕТИЧЕСКИЙ ИНСТИТУТ

(ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)

Лекции

ТЕОРИЯ ГРАФОВ И КОМБИНАТОРИКА

3 семестр

Лектор

Москва, 2009/2010

Содержание.

Лекция № 1.	Основные понятия теории графов .................................................................... 2
Лекция № 2.	Эйлеровы циклы ................................................................................................. 3 Гамильтоновы циклы ......................................................................................... 8 Деревья и остовы .............................................................................................. 10 Деревья .............................................................................................................. 11
Лекция № 3.	Остовы ............................................................................................................... 12
Лекция № 4.	Задача о минимальном остове ......................................................................... 15 Фундаментальные циклы и разрезы ............................................................... 16
Лекция № 5.	Независимые и доминирующие множества вершин .................................... 18
Лекция № 6.	Изоморфные, плоские и планарные графы .................................................... 21
Лекция № 7.	Раскраска графа ................................................................................................ 26
Лекция № 8.	Правильный граф ............................................................................................. 28 Паросочетания в двудольных графах ............................................................. 30
Лекция № 9.	Способы построения совершенного паросочетания ..................................... 33
Лекция № 10.	Задача о кротчайшем пути ............................................................................... 35 Потоки в транспортных сетях ......................................................................... 38
Лекция № 11.	Потоки в сетях .................................................................................................. 39
Лекция № 12.	Комбинаторный анализ .................................................................................... 43
Лекция № 13.	Производящие функции .................................................................................. 47
Лекция № 14.	Экспоненциальные производящие функции ................................................. 50
Лекция № 15.	Линейные рекуррентные уравнения ............................................................... 53
Лекция № 16.	Методы включений-исключений .................................................................... 59
Экзаменационная программа.	......................................................................................... 62

Лекция № 1.

ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ.

Определение 1.

Граф обозначается , где – множество вершин графа, а – множество ребер, причем .

Определение 2.

Ребра бывают неориентированные , для которых порядок вершин не важен, и ориентированные – ориентированное ребро, или дуга. Стрелка от вершины к показывает направление ориентации дуги.

Определение 3.

Вершины называются смежными, если существует ребро, которое их соединяет. Смежными называются ребра, имеющие общую вершину.

Определение 4.

Пусть , тогда и называются инцидентными.

Определение 5.

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

Определение 6.

Петлей называется ребро с совпадающими началом и концом.

Определение 7.

Граф называется простым, если он не содержит петель и кратных ребер.

Псевдограф – граф без кратных ребер.

Мультиграф – граф, содержащий петли и кратные ребра.

Определение 8.

Степенью вершины называется число ребер, инцидентных вершине . Петля в степени вершины учитывается дважды.

Теорема 1. (О сумме степеней вершин)

В любом графе, включая псевдограф и мультиграф, .

4 – число ребер, соединяющих и . Тогда . Каждое ребро в этой сумме содержится в двух слагаемых и .3

Следствие (лемма о рукопожатиях).

Число вершин нечетной степени четно.

4Сумма степеней вершин чётной степени всегда чётно. А сумма степеней ВСЕХ вершин также должна быть чётной (по теореме о сумме степеней вершин). Следовательно, и сумма степеней вершин с нечётной степенью должна быть чётна, что возможно лишь в случае, когда чётно их число (сумма чётного числа нечётных слагаемых всегда чётна, а сумма нечётного числа нечётных слагаемых всегда нечётна).3

Определение 9.

Маршрут – чередующаяся последовательность инцидентных друг другу вершин и ребер, начинающаяся и заканчивающаяся в вершине. Длина маршрута – число ребер в нем.

Определение 10.

Цикл – замкнутый маршрут, начинающийся и заканчивающийся в одной вершине.

Определение 11.

Цепь – маршрут без повторяющихся ребер.

Простая цепь – маршрут без повторяющихся вершин и ребер.

Пример.

– маршрут (не цепь!) длиной 3.

– цепь, но не простая.

– простой цикл, длины 3.

Определение 12.

Матрица смежности простого графа ,

, где

Свойства матрицы смежности:

1.  Симметричность.

2.  Элементы главной диагонали .

3.  Число единиц в строке (столбце) равно .

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