1-й сем-ДМ-слайды-ДГТУ / Графы-3,4 лекции / Эйлеровы и гамильтоновы графы

Эйлеровы и Гамильтоновы графы.

Граф G – Эйлеров, если замкнутая цепь, проходящая через каждое ребро + ребро проходящее лишь 1 раз! Если снять ограничение на замкнутость цепи, то граф – полуэйлеров. Каждый Эйлеров граф – полуэйлеров.

1 – не Эйлеров

1 a 2

d b

4 c 3

2 – полуэйлеров

1 2

5

4 3

3 – Эйлеров

4 – нет

Лемма

Если степень каждой вершины графа G не меньше двух, то G содержит цикл.

Доказательство:

Если в G имеется петли или кратные рёбра, то утверждение очевидно. Пусть G – построен по индивидуальному маршруту …, выбираем вершину смежной вершине , а для ≥ 1 – выбираем +1 смежной и отличной от -1. Т.к. G имеет конечное число вершин, то в конце концов придём к вершине, выбранной ранее. Пусть – первая такая вершина, тогда часть маршрута, лежащая между двумя входящими , и является искомым циклом.

Теорема

Связный граф G является Эйлеровым тогда и только тогда, когда каждая вершина в G имеет чётную степень.

Доказательство:

Пусть P – Эйлерова цепь в G. Тогда при каждом прохождении цепи через любую из вершин графа степень этой вершины увеличивается на два. А т.к. каждое ребро встречающееся в P равно 1 рад, то каждая вершина должна иметь четную степень.

В силу связности G, степень каждой вершины не меньше двух, и по лемме цикл, что при G содержит цикл C. Если C проходит через каждое ребро G, то доказательство завершено, если нет, то удаляем из G ребра, принадлежащие, получаем новый (может быть несвязный) граф H. Число рёбер в H меньше, чем G и любая вершина H имеет чётную степень. В каждой компоненте H существует Эйлерова цепь. В силу связанности графа G, каждая компонента имеет, по крайней мере, одну общую вершину с циклом C, поэтому искомую Эйлерову цепь графа G можно получить так: идёт по рёбрам цикл C до тех пор, пока не встречаем неизолированную вершину графа H, затем следуя по Эйлеровой цепи той компоненте в H, которая содержит указанную вершину; далее продолжаем путь по рёбрам цикла C, пока не встречаем вершину принадлежащую другой компоненте графа H и т.д. Процесс закончен, когда каждую обратишь в начальную вершину.

Сводят граф Эйлеров тогда и только тогда, когда семейство его рёбер можно разбить на непересекающиеся циклы.

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

Алгоритм построения Эйлеровой цепи(цикла) в Эйлеровом графе.

Алгоритм Флери

Выходим из произвольной вершины, идём по рёбрам, произвольным образом соблюдая правила:

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

• На каждом этапе идём по мосту только тогда, когда нет других возможностей.

Задача

С помощью алгоритма Флери найти Эйлерову цепь в графе.

Гамильтоновы графы.

Прохождение ребра один раз через каждую вершину G – Гамильтонова цепь или цикл. Граф, содержащий цепь через каждую вершину – полугамильтонов. Всякий гамильтонов граф – полугамильтонов!

1 – не гамильтонов

2 – полугамильтонов

4(1)

3(4)2(3)

3 – Гамильтонов

Теорема Дирака

Если в простом графе с n﴾≥3﴿ вершинами ρ﴾V﴿≥n/2 для любой вершины V, то граф G – гамильтонов.

Задача

Может ли шахматный конь побывать на каждой клетке шахматной доски 8 х 8 ровно один раз и возвратиться в исходную точку? А если доска 7 х 7?

Задача

Показать, что любой полный симметричный граф содержит гамильтонов цикл.

Если в графе G с n вершинами для любой пары вершин и ρ﴾﴿+ρ﴾﴿≥n-1, то G имеет гамильтонову цепь.

Если же ρ﴾﴿+ρ﴾﴿≥n, то G имеет гамильтонов цикл.

Пусть G имеет p≥3 вершин.

Если для всякого n, 1≤n≤, число вершин со степенями, не превосходящими n, меньше, чем n и для нечётного p числа вершин степени , не превосходящей , то G гамильтонов граф.

Задачи

1 – Эйлеров

2 – Неэйлеров

2 3 4 5

1 6

8 7

3 – Негамильтонов

4

3 1

2