Найдем, например, кратчайшую цепь из вершины x2 в вершину

x1:

j1 = P21 = 4; j2 = P24 = 3; j3 = P23 = 2; M = [2; 3; 4; 1].

7.5 Обходы графа

Существует ряд задач на графах, в которых требуется найти маршрут, который содержит все вершины или ребра графа – обход. Часто требуется, чтобы длина этого маршрута была минимальной (для взвешенных графов), или ограничивается число проходов по одному и тому же элементу графа. Одна из задач заключается в том, чтобы обойти все вершины графа и в каждой из них только один раз выполнить какое-либо действие: в простейшем случае пронумеровать или пометить вершину; в более сложных случаях решить какую-либо задачу, связанную с этой вершиной. Эту задачу часто называют поиском на графе.

7.5.1 Поиск в глубину на графе

В процессе поиска будем различать вершины

²непросмотренные;

²просмотренные (пронумерованные), но не помеченные;

²помеченные.

Перед началом просмотра все вершины считаются непросмотренными и непомеченными.

Общая идея метода состоит в следующем.

1.Поиск начинается с некоторой фиксированной вершины x0, которой назначаем номер 0. Вершина x0 теперь просмотрена, но не помечена. Затем выбираем любую вершину x1, смежную с x0, нумеруем ее единицей 1, и процесс поиска продолжается от нее.

Считаем теперь вершину x1, которая просмотрена, но не помечена, текущей.

2.Пусть xi – текущая просмотренная вершина. Если существует еще непросмотренная вершина xi+1, смежная с xi, то поиск продолжается с вершины xi+1. Если нет непросмотренной вершины, смежной с xi, то вершина xi считается помеченной. Теперь делается возврат – (бэктрекинг, backtracking) в вершину xi¡1, ту, из которой в процессе поиска мы попали в xi. Вершина xi¡1 становится текущей и поиск продолжается из нее.

Поиск продолжается до тех пор, пока снова не вернемся в вершину x0 и x0 окажется помеченной.

Поиск в глубину на дереве. Нумерация на рисунках соответствует очередности просмотра вершин в процессе поиска в глубину. Номера в скобках соответствуют очередности разметки. J

З а м е ч а н и е. Метод поиска в глубину очевидным образом переносится на орграфы – переход к следующей вершине происходит по направлению ориентации дуги, а возврат – в противоположном направлении. Таким образом, при обходе графа мы

стремимся проникнуть в глубину графа так далеко, как это возможно, затем отступаем на шаг назад, снова стремимся пройти вперед и т.д. I

Алгоритм поиска в глубину имеет сложность порядка O(n + m), где n – число вершин, а m – число ребер графа. Действительно, каждая вершина просматривается один раз (всего n), а поиск смежных вершин (для всех n вершин) можно организовать за m просмотров.

Пример 7.11.

Поиск в глубину на произвольном графе. Нумерация вершин на рисунках соответствует очередности просмотра вершин в процессе поиска в глубину. Номера в скобках соответствуют очередности разметки.

7.5.2 Поиск в ширину на графе

1.Поиск начинается с некоторой фиксированной вершины s.

2.Последовательно просматриваются и помечаются вершины, находящиеся на расстоянии 1 от s (т.е. смежные с s).

3.k-й шаг. Просматриваются и помечаются все вершины, находящиеся на расстоянии k от s.

Процесс поиска продолжается до тех пор, пока все вершины не будут просмотрены и помечены.

Пример 7.12.

Поиск в ширину на дереве и на произвольном графе. Нумерация вершин на рисунках соответствует очередности просмотра вершин в процессе поиска в ширину.

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

Если граф G несвязен, то он может иметь (но не обязательно имеет) эйлерову цепь лишь в том случае, если все его компоненты связности, кроме может быть одной, представляют собой голые вершины.

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

Д о к а з а т е л ь с т в о . 1. °) Необходимость. Пусть эйлерова цепь существует и проходит из вершины x в вершину y. Если эта цепь – цикл (x = y), то в каждую вершину цепь должна зайти столько же раз, сколько и выйти (т.е. валентности всех вершин – четные). Если x =6 y, то из x цепь должна выйти на один раз больше, чем зайти; в y цепь должна зайти на один раз больше, чем выйти (т.е. валентности вершин x и y должны быть нечетными).

2. °( Достаточность. Пусть валентности всех вершин, за исключением может быть вершин x и y, четные.

Если все валентности четные: начнем цепь из некоторой произвольной вершины x и пойдем по некоторому еще не пройденному ребру к следующей вершине и так до тех пор, пока не вернемся в вершину x и не замкнем цикл. Если пройдены все ребра, то искомый эйлеров цикл C построен. Если в C входят не все ребра графа, то цикл C должен проходить через некоторую вершину z, инцидентную некоторому ребру, не вошедшему в C (т.к. граф связен).

Если удалить все ребра из C, то в оставшемся суграфе вершины будут по-прежнему иметь четные валентности, так как в суграфе C все валентности четные. Начиная теперь с вершины z построим цикл C0, начинающийся и кончающийся в z. Если в C0 пройдены все оставшиеся ребра, то процесс закончен. Нужный нам эйлеров цикл будет образован частью цикла C от x до z, затем циклом C0 и, наконец, частью цикла C от z до x.

Если циклы C и C0 содержат не все ребра графа, то строится следующий цикл, и так далее, до тех пор, пока не будет найден эйлеров цикл.

Если вершины x и y имеют нечетные валентности, то сначала находим цепь, соединяющую x и y; удалив ребра этой цепи, построим эйлеров цикл, начиная с вершины x. Эйлерова цепь выходит теперь из вершины x, проходит эйлеров цикл, а затем снова из вершины x по найденной цепи в вершину y. £

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

Описание алгоритма.

Шаг 1. Находим простую цепь P , соединяющую вершины с нечетной валентностью (если они есть) x и y. Если ее длина больше 0 (т.е. x 6= y), то все ребра этой цепи пометим меткой 0.

Шаг 2. Если еще есть непомеченные ребра, то выберем среди них такое u, которое инцидентно хотя бы одной вершине цепи P . В суграфе, порожденном всеми непомеченными ребрами найдем простой цикл, содержащий ребро u (например, с помощью алгоритма нахождения цепей) и все ребра этого цикла пометим меткой 1.

Шаг 3. Если в графе остались непомеченные ребра, то из них выбирается такое v, которое смежно хотя бы с одним помеченным. В суграфе, порожденном непомеченными ребрами выявляем простой цикл, содержащий v, и все ребра этого цикла помечаем меткой k + 1. Разметка продолжается до тех пор, пока не будут помечены все ребра графа.

Шаг 4. Маршрут строится следующим образом: за начальную вершину выбираем x0 = x. Если уже построен маршрут

x0u1x1 : : : xk¡1ukxk; (k ¸ 0), котором все ребра различны, то

1)в случае k = m процесс закончен (маршрут найден);

2)если k < m, то среди ребер, инцидентных xk и отличных от u1; : : : ; uk выбираем такое, которое помечено наибольшей меткой (или любое из них) и добавляем его к маршруту как ребро uk+1, а за xk+1 берем ту вершину, с которой uk+1 соединяет вершину xk (возможно xk+1 = xk, если uk – петля).

Сложность алгоритма нахождения эйлеровой цепи (цикла) имеет порядок O(m).

З а м е ч а н и О. чевидно, что обобщение задачи нахождения эйлеровой цепи (если она существует) на взвешенные графы не имеет смысла, так как сумма весов в этой цепи всегда одна и та же. I