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

Утверждение 1.

Если в графе имеется точка сочленения, то Гамильтонова цикла не существует.

Утверждение 2 (Достаточное условие Дирака).

Утверждение 3 (Достаточное условие Оре).

Покажем, что эти условия не являются необходимыми.

n=8. Условия Дирака и Оре не выполняются,

Гамильтонов цикл существует!

Замечание.

Существование Эйлерова и Гамильтонова циклов не связаны.

Существуют Эйлеров и Гамильтонов циклы.

Существует Гамильтонов цикл, но не существует Эйлеров цикл.

Существует Эйлеров цикл, но не существует Гамильтонов цикл.

Не существуют Эйлеров и Гамильтонов циклы.

Замечание.

Почти все графы не имеют Эйлерова или Гамильтонова цикла.

ДЕРЕВЬЯ И ОСТОВЫ.

Лемма 1.

Если граф связен, то соединение ребром любых двух несмежных вершин приводит к появлению цикла.

Лемма 2.

Если граф связен и его ребро входит в некоторый цикл, то удаление этого ребра не нарушит связанность графа.

Лемма 3.

Пусть граф G связен и имеет n вершин, m рёбер, k компонент связанности, тогда

1)

2) если в графе нет циклов, то

41) Пусть – граф, имеющий n изолированных вершин и не имеющий вообще рёбер. Будем m раз добавлять по 1 ребру, пока не получим граф G.

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

В другом случае: если соединяли ребром вершину из разных компонент, то число компонент уменьшится на единицу.

Сначала в было n компонент связанности, после m шагов добавления ребра стало .

2) Если G не имеет циклов, то на каждом шаге соединяем ребром вершины из разных компонент, иначе бы в силу леммы 1 получили бы цикл.3

Лемма 4.

Если число рёбер и вершин удовлетворяют неравенству , то граф не является связанным.

4

По лемме 3 , значит граф не связан. 3

Замечание.

Почти все графы связаны.

ДЕРЕВЬЯ.

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

Деревом называется связанный граф без циклов.

Теорема 1 (характеристические свойства дерева).

Условия эквивалентны:

(1)  Граф G является деревом;

(2)  и нет циклов;

(3)  и граф связен;

(4)  Граф связен и удаление любого ребра делает граф не связанным;

(5)  Граф связен, нет циклов, но добавление любого нового ребра приводит к циклу.

4

По лемме 3 .

Если бы граф не был связен, то , что противоречит .

По лемме 4.

Если в графе есть циклы, то применяем лемму 2, если нет – лемму 4.

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

Утверждение.

Дерево с вершин имеет висячих вершин (т. е. степени 1).

4 по крайней мере две вершины степени 1. 3

Лекция № 3.

ОСТОВЫ.

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

Подграф графа называется остовным, если .

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

Остовный подграф графа G, являющийся деревом называется остовом графа G (остовным деревом).

G остовы G

Теорема 1 (матричная теорема Кирхгофа).

Пусть А – матрица смежности графа, , тогда алгебраическое дополнение элемента матрицы М равно числу остовов графа G.

Пример.

Все 8 остовов графа:

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

Полным графом с n вершин – граф, который имеет все возможные рёбра, т. е. и смежны.

Теорема 2 (Кэли).

Число деревьев с n помеченными вершинами равно .

4Для n=1 и n=2 очевидно. Пусть число вершин , тогда каждое дерево является остовом полного графа и для подсчёта их числа используем матричную теорему Кирхгофа.

3

Пример.

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

В корневых деревьях выделяется одна вершина, которая является корневой.

Утверждение 1.

Число корневых деревьев с n помеченными вершинами равно .

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

Бинарное корневое дерево это (L, c, R), где L – левое поддерево, c – корень, R – правое поддерево.

Утверждение 2.

Число бинарных корневых деревьев с n вершинами равно .

Пример.

Лекция № 4.

ЗАДАЧА О МИНИМАЛЬНОМ ОСТОВЕ.

Дан связный граф и , называемое весом. Требуется найти остов с наименьшим суммарным весом.

Алгоритм.

Т – часть min остова.

1.  Пусть k=1 – число вершин в остове и в качестве остова Т – любая вершина.

2.  Рассмотрим все рёбра и найдём среди них рёбра min веса .