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

Алгоритмы поиска эйлеровых циклов

ребер, начинающаяся и заканчивающаяся вершиной
Маршрут в котором все ребра различны,

называется цепью

Цепь называется простой, если и все вершины в ней различны

Путь – это … ориентированная цепь, в которой дуги имеют одинаковое направление

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

называется односторонне связным, если для любых двух различных вершин хi и xj существует, по крайней мере, один путь из хi в хj или из xj в хi или оба одновременно.
Орграф называют слабо связным, если для любых двух различных вершин графа существует, по крайней мере, один маршрут (неориентированный двойник пути), соединяющий их.

Простая цепь?
Что такое путь? Чем он отличается от цепи?
Что такое

цикл? Простой цикл?
Какой граф называется связным?
Какая вершина называется точкой сочленения?
Какое ребро (дуга) называется мостом (перешейком)?

Вопросы

abdbc
abdcb
abcde
abdbca
abfedbca
abca

один раз
Эйлеровым циклом называется цикл, содержащий все рѐбра графа и

притом по одному разу.

Граф, обладающий эйлеровым циклом, называется эйлеровым графом.

Задача китайского почтальона
Почтальон должен разнести почту по вверенному ему району, для чего он проходит по всем без исключения улицам района и возвращается в исходную точку (на почту). Требуется найти кратчайший маршрут
почтальона.

имеется лив графе путь, проходящий через все его ребра (напомним,

что путь, по определению, не может дважды проходить по одному ребру). Такой путь называется эйлеровым путем, а если он замкнут, то эйлеровым циклом. В графе, изображенном на рис. 1, эйлеров цикл существует -например, последовательность вершин 1,2,4,5,2,3,5,6,3,1 образует такой цикл. В графе же на рис. 2 эйлерова цикла нет, но есть эйлеровы пути, например, 2, 4, 5, 2, 1, 3, 5, 6, 3.

рис. 1

рис. 2

степени всех вершин четны
В ориентированном графе эйлеров цикл – это

ориентированный цикл, проходящий через все ребра

3 эйлеров путь, цикла нет
Если граф G(V,E) обладает эйлеровым циклом,

то он связный и все его вершины четные

Если граф G(V,E) связный и все его вершины четные, то он обладает эйлеровым циклом

когда в нем имеется не более двух вершин нечетной степени
добавлено

ребро 3-5

3 – 2 – 4- 3 – 5 – 4 – 6 – 0 – 2 – 1 – 0 – 5

0 – 1 – 2 – 0 – 6 – 4 – 2 – 3 – 4 – 5 – 0

ребро е, инцидентное текущей вершине.
3 Назначить текущей вторую вершину, инцидентную

e.
4 Удалить e из текущего графа и внести в список.
5 Если в текущем графе еще остались ребра, вернуться на шаг 2
Ограничение: если степень текущей вершины больше 1, нельзя выбирать ребро, удаление которого из текущего графа увеличит число компонент связности в нем.

ребро е, инцидентное текущей вершине.
3 Назначить текущей вторую вершину, инцидентную

e.
4 Удалить e из текущего графа и внести в список.
5 Если в текущем графе еще остались ребра, вернуться на шаг 2

1 Выберем произвольную вершину v1
2 Выберем произвольное ребро е{v1,v5}, инцидентное текущей вершине.
3 Назначим текущей вторую вершину, инцидентную e – вершину v5.

v1-

ребро е, инцидентное текущей вершине.
3 Назначить текущей вторую вершину, инцидентную

e.
4 Удалить e из текущего графа и внести в список.
5 Если в текущем графе еще остались ребра, вернуться на шаг 2

4 Удалим из текущего графа ребро е{v1,v5} и внесем в список.
5 Так как в текущем графе еще остались ребра, возвращаемся на шаг 2

v1-v5-

ребро е, инцидентное текущей вершине.
3 Назначить текущей вторую вершину, инцидентную

e.
4 Удалить e из текущего графа и внести в список.
5 Если в текущем графе еще остались ребра, вернуться на шаг 2

v1-v5-

1 Текущая вершина – v5
2 Выберем произвольное ребро е{v5,v2}, инцидентное текущей вершине.
3 Назначим текущей вторую вершину, инцидентную e – вершину v2.

ребро е, инцидентное текущей вершине.
3 Назначить текущей вторую вершину, инцидентную

e.
4 Удалить e из текущего графа и внести в список.
5 Если в текущем графе еще остались ребра, вернуться на шаг 2

4 Удалим из текущего графа ребро е{v5,v2} и внесем в список.
5 Так как в текущем графе еще остались ребра, возвращаемся на шаг 2

v1-v5-v2-

ребро е, инцидентное текущей вершине.
3 Назначить текущей вторую вершину, инцидентную

e.
4 Удалить e из текущего графа и внести в список.
5 Если в текущем графе еще остались ребра, вернуться на шаг 2

v1-v5-v2-

1 Текущая вершина – v2
2 Выберем произвольное ребро е{v2,v6}, инцидентное текущей вершине.
3 Назначим текущей вторую вершину, инцидентную e – вершину v6.

ребро е, инцидентное текущей вершине.
3 Назначить текущей вторую вершину, инцидентную

e.
4 Удалить e из текущего графа и внести в список.
5 Если в текущем графе еще остались ребра, вернуться на шаг 2

4 Удалим из текущего графа ребро е{v2,v6} и внесем в список.
5 Так как в текущем графе еще остались ребра, возвращаемся на шаг 2

v1-v5-v2-v6-

ребро е, инцидентное текущей вершине.
3 Назначить текущей вторую вершину, инцидентную

e.
4 Удалить e из текущего графа и внести в список.
5 Если в текущем графе еще остались ребра, вернуться на шаг 2

v1-v5-v2-v6-

1 Текущая вершина – v6
2 Выберем ребро е{v6,v4}, инцидентное текущей вершине. РЕБРО {v6,v3} ВЫБИРАТЬ НЕЛЬЗЯ!
3 Назначим текущей вторую вершину, инцидентную e – вершину v4.

ребро е, инцидентное текущей вершине.
3 Назначить текущей вторую вершину, инцидентную

e.
4 Удалить e из текущего графа и внести в список.
5 Если в текущем графе еще остались ребра, вернуться на шаг 2

4 Удалим из текущего графа ребро е{v6,v4} и внесем в список.
5 Так как в текущем графе еще остались ребра, возвращаемся на шаг 2
... И ТАК ДАЛЕЕ

v1-v5-v2-v6- v4- v5- v6- v3- v2- v1

вершины графа
v1→v2→v3→v8→v4→v9→v12→v11→v7→v6→v10→v5→v1

задачи гамильтонов.
Задача коммивояжера:
Дан список городов, соединенных дорогами, длины которых

известны. Коммивояжер должен объехать все города, побывав в каждом по одному разу, и вернуться в свой город. Требуется найти кратчайший маршрут коммивояжера.

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

существовании эйлерова цикла в графе достаточно выяснить, все ли его

вершины четные.
Критерий же существования гамильтонова цикла на произвольном графе до сих пор не найден.

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

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

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

Теорема Дирака. Если в графе G(V,E) c n вершинами (n ≥ 3) выполняется условие d(v) ≥ n/2 для любого v  V, то граф G является гамильтоновым.

граф называют гамильтоновым?
Существует ли эйлеров граф, обладающий висячей вершиной?
Чем отличается

эйлеров путь от гамильтонова?