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

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

Матрица инциденций простого графа

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

1.  В каждом столбце ровно 2 единицы.

2.  Число единиц в строке равно степени вершины.

3.  Каждый минор равен либо 0, либо +1, либо -1.

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

Подграф графа :

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

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

Граф	Орграф
Ребро	Дуга
Степень вершины	Полустепень исхода Полустепень захода
Маршрут	Путь
Цикл	Контур
Матрица смежности
Матрица инцидентности

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

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

Замечание.

Вершина удаляется из графа со всеми инцидентными рёбрами.

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

Вершина называется точкой сочленения, если её удаление увеличивает число компонент связности. Ребро называется мостом, если его удаление увеличивает число компонент связности.

Лекция № 2.

ЭЙЛЕРОВЫ ЦИКЛЫ.

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

Цикл называется Эйлеровым, если в него входят все рёбра графа, причем, строго по одному разу.

Теорема 1 (Эйлер, 1748) для неориентированных графов.

Следующие условия эквивалентны:

4 Очевидно.

Докажем методом математической индукции по числу рёбер. Базис индукции m=1,2,3… Рассмотрим индуктивный переход. Пусть выполнено условие (2). Возьмём . Выйдем из вершины по любому инцидентному ребру, попадём в другую вершину . Из неё выйдем по следующему ребру, попадём в другую вершину и т. д. пока не вернёмся в одну из пройденных вершин.

Найдём простой цикл . Удаляем из графа все рёбра этого цикла . Оставшийся граф разобьётся на несколько компонент связанности. Каждая компонента связанности является связанным подграфом и степень каждой вершины осталась чётной.

Имеем рёбер. По индуктивному предположению в Эйлеровы циклы. Склеим эти циклы в по общим вершинам и получим Эйлеров цикл во всём графе. 3

1	4
2	4
3	4
4	4
5	4
6	4
7	2
8	4

Пример.

 

 

 

 

и имеют общую вершину и имеют общую вершину и имеют общую вершину

 

Теорема 2 (для ориентированных графов).

Следующие условия эквивалентны:

Пример.

1	2	2
2	2	2
3	2	2
4	2	2
5	1	1
6	1	1

ГАМИЛЬТОНОВЫ ЦИКЛЫ.

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

Гамильтоновыми называются циклы, проходящие через каждую вершину ровно один раз.

Неизвестны условия (необходимые и достаточные) для существования Гамильтонова цикла.