Обходы графов. Глава 3

Существует ряд задач на графах, в которых требуется найти маршрут, который

Одна из задач заключается в том, чтобы обойти все вершины графа

3.1. Поиск в ширину (breadth-first search, BFS)
1. Поиск начинается с некоторой

3.1. Эйлеровы цепи и циклы

Определение. Эйлеровой цепью (циклом) называется цепь (цикл), содержащая (содержащий) все ребра

Теорема. Эйлерова цепь (цикл) существует тогда и только тогда, когда число

 
На этом доказательстве основан алгоритм нахождения эйлеровой цепи.

В 1736 г. Л.Эйлер опубликовал эту теорему, носящую
в литературе его

Алгоритм Хирхольцера

В 1873 г. вышла статья немецкого математика К. Хирхольцера
(Carl

Алгоритм Хирхольцера выполняется в точном соответствии
с доказательством достаточности теоремы Эйлера.
Рассмотрим

Шаг 0.
Выбрать начальную вершину s;
/* Поместить s в C

Шаг 2. /* Поиск цикла */
– /* выбрать не

Пример.

Выберем начальную вершину
и поместим ее в список C:
Выполнив нужное

На поиск вершин, инцидентных еще не пройденным ребрам, понадобится самое большее

Алгоритм 2 [Липский].
Задан обыкновенный связный граф
без вершин с

Шаг 1.
если то {Выход – C искомый эйлеров цикл}.
/*

Пример.

3

1

4

2

5

6

3

2

4

1

3

2

4

6

1

3

5

3

6

3

5

S

C

4

2

1

(для всех вершин, кроме s и t, полувалентности исхода и
полувалентности

Задача китайского почтальона

В графе с неотрицательными весами ребер найти циклический маршрут

3.1. Гамильтоновы цепи и циклы

Постановка задачи

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

Граф Гамильтона

Додекаэдр:
12 граней,
20 вершин,
30 ребер

Гамильтонов цикл

В 1859 г. Гамильтон изобрел

Мы рассмотрим два простейших переборных алгоритма поиска гамильтоновой цепи (цикла), пригодных

Поиск в ширину

2

- бесперспективное (тупиковое ) множество вариантов

- множество вариантов стоит исследовать

Поиск в глубину

2

- прямой ход по дереву поиска

- обратный ход (back

Задача коммивояжера

Задача коммивояжера (travelling seller problem, TSP) формулируется следующим образом: во

Пример. Столицы 48 штатов

Длина пути 16675 миль. Алгоритм LMatrix

http://lmatrix.ru/news/problems