Федоров В.Н. - Введение в теорию графов, страница 5

t – конец маршрута.

Ищем маршрут между s и t.

Прямая фаза

Сначала все вершины не имеют меток.

1. Положим i = 0, присвоим вершине s вес w(s) = i (т.е. w(s) = 0) .

2. Находим все не помеченные вершины, связанные ребром с вершиной (вершинами) с меткой i.

3. Если такие вершины есть, то помечаем их метками i = i + 1. Если вершина t помечена, то к п. 4. Если – нет, то к п. 2. Если таких вершин нет, а вершина t не помечена, то t недостижима из s. СТОП.

4. Длина кратчайшего маршрута от s к t равна w(t). СТОП.

Обратная фаза (начинается с конца)

Принадлежность вершин кратчайшему маршруту определяется из условий:

Конечная вершина v_k = t.

Для v_k–1 должно выполняться условие w(t) – w(v_k–1) = 1.

Для v_k–2 w(v_k–1) – w(v_k–2) = 1

и т.д. пока не придем в вершину s.

П
ример. На рис. 5.2 показан граф с разметкой вершин.

Маршрут найдите самостоятельно.

Рисунок 5.2

Длина маршрута (s, t) равна 3.

Вариант 2:

Каждое ребро имеет вес ℓ_ij – число, если ребро есть, или , если ребра нет. Петля имеет вес ℓ_ii = 0.

Ищем кратчайший маршрут между вершинами v₁ и v_k.

Прямая фаза

1. Пометить вершины с номерами 1…n метками ₁ = 0, _i = , i = , n – число вершин. Метки вершин v₂,…,v_n считаем временными.

2. Рассматриваем v₁. У вершин, смежных с v₁, временные метки меняем по следующему правилу:

– если _i – ₁  ℓ_1,i (ℓ_1,i – длина ребра, соединяющего вершину v₁ с вершиной v_i), то заменяем _i на _i =  ₁ + ℓ_1,i

• если _i – ₁  ℓ_1,i, то _i не изменяем.

Присвоенные метки вершин считаем временными.

1. Среди вершин с временными метками выбираем вершину v_i с минимальным значением метки _i. Метку этой вершины делаем постоянной.

2. Рассматриваем вершины v_j, смежные с v_i, и изменяем метки v_j:

– если λ_j – λ_ί > ℓ_ij, то λ_j = λ_ί + ℓ_ij,

– если λ_j – λ_ί  ℓ_ij, то не меняем.

1. Если метка конечной вершины v_k – постоянная, то к пункту 6, если нет, то к пункту 3.

Обратная фаза

1. Строим маршрут, начиная с v_k. λ_k – длина маршрута.

Принадлежность вершины v_k–1 маршруту определяется равенством

λ_k – _k–1 = ℓ_{k, k–1}

Вершина v_k–2 должна удовлетворять условию

_k–1 – _k–2 = ℓ_{k–1, k–2} и т.д. идем до вершины v₁.

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

Пример. Дан граф с весами ребер, показанными на рис. 5.3.

Найдите кратчайший маршрут (1,4) самостоятельно.

Ответ: 1,5,3,4; ℓ_1,4 = 2.

Р
исунок 5.3

5.2. Контрольные вопросы

1. Как определить кратчайший маршрут во взвешенном графе?

2. Как и почему можно упростить орграф при поиске кратчайшего маршрута? Почему нельзя так упростить неорграф?

3. Приведите первый вариант волнового алгоритма нахождения кратчайшего маршрута во взвешенном графе.

4. Приведите второй вариант волнового алгоритма нахождения кратчайшего маршрута во взвешенном графе.

5. Чем отличаются первый и второй варианты волнового алгоритма нахождения кратчайшего маршрута во взвешенном графе.

6. Эйлеровы графы

Понятия эйлеров граф, эйлеров цикл и эйлерова цепь были рассмотрены в п. 1.11. Рассмотрим алгоритмы построения эйлерового цикла и эйлеровой цепи, и их применение для нахождения покрытия графа непересекающимися по ребрам цепями.

6.1. Алгоритм построения эйлерова цикла

Предполагается, что граф связен и удовлетворяет условиям Эйлера. Все ребра графа не имеют индексов.

1. Положить i = 1. Построить простой цикл с началом в некоторой вершине w (в первый раз это будет вершина v_нач).

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

1. Всем ребрам построенного цикла присвоить индекс i. Если ребер без индекса больше нет, то к п. 4 , иначе к п. 3.

2. Положить i = i + 1, среди ребер без индекса выбрать ребро, смежное одному из ребер с индексом. Построить простой цикл из еще не помеченных ребер, содержащий выбранное ребро, и перейти к п. 2.

3. Строим эйлеров цикл с началом в v_нач последовательным обходом ребер графа. На каждом шаге выбираем ребро с наибольшим индексом. Если таких ребер несколько, то берем любое из них.

6.2. Алгоритм построения эйлеровой цепи

Если требуется построить эйлерову цепь, то

1. Сначала строится простая цепь между вершинами с нечетными степенями. ее ребрам присваиваются индексы i = 1.

2. Если ребер без индекса больше нет, то к п. 4 , иначе к п. 3.

3. Положить i = i + 1, среди ребер без индекса выбрать ребро, смежное одному из ребер с индексом. Построить простой цикл из еще не помеченных ребер, содержащий выбранное ребро, присвоить ребрам этого цикла индекс i и перейти к п. 2.

4. Строим эйлеров цикл с началом в v_нач последовательным обходом ребер графа. На каждом шаге выбираем ребро с наибольшим индексом. Если таких ребер несколько, то берем любое из них.

6.3. Модифицированный алгоритм построения эйлерова цикла

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

циклы, которые мы пытаемся построить, назовем основными. Циклы, которые возникают при некоторых вершинах в процессе построения основных, назовем частными.

Введем две переменные i и j. В i будем подсчитывать общее количество циклов, в j число частных циклов, появляющихся при построении одного основного цикла.

1. Полагаем i = 1 и j = 1.

2. Случайным блужданием из ребер без индексов строим основной цикл с началом в некоторой вершине w (в первый раз это будет вершина v_нач).

3. Если в процессе построения основного цикла возникает частный цикл при какой–либо вершине, то ребрам этого цикла присваиваем индексы in = i + j и полагаем j = j + 1.

4. Продолжаем строить начатый основной цикл. Если частный цикл не образуется, то к п. 5, иначе к п. 3.

5. После завершения строительства основного цикла, т.е. когда мы вернемся в вершину w, его ребрам присвоим индексы in = i и изменим значения i и j: i = i + j, j = 1.

6. Если ребер без индекса больше нет, то к п. 8, иначе к п. 7.

7. Среди оставшихся ребер без индексов выбираем ребро, инцидентное одной из вершин ранее построенного цикла (построенных циклов), пусть это будет вершина w, и к п. 2.

8. Строим эйлеров цикл с началом в v_нач последовательным обходом ребер графа. На каждом шаге выбираем ребро с наибольшим индексом. Если таких ребер несколько, то берем любое из них.

Аналогично изменяется и алгоритм построения эйлеровой цепи.

6.4. Покрытие графа непересекающимися по ребрам цепями

Количество таких цепей равно k/2, где k – количество вершин с нечетными степенями, оно всегда четно.

Если k = 2 , то получается эйлерова цепь.

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

Для преобразования графа в эйлеров граф можно

– продублировать все ребра (дуги) графа, или

– добавить фиктивную вершину и соединить ее ребрами с вершинами, имеющими нечетную степень; таких вершин четное число, поэтому степень введеной вершины будет четной и, следовательно, все вершины будут удовлетворять условиям Эйлера, или

– разбить множество вершин с нечетными степенями на пары и соединить вершины каждой пары ребром или маршрутом кратчайшей длины.

П
ример. Пусть задан граф G(8,13), показанный на рис. 6.1.

Требуется покрыть граф непересекающимися по ребрам цепями.

Рисунок 6.1

Решение:

Введем фиктивную вершину 9 и соединим ее с вершинами 1, 2, 5, 8, имеющими нечетные степени (см. рис. 6.2).

Первая фаза

Пусть v_нач= 9, i = 1, j = 1 (i – формирователь индексов ребер основных циклов, j – формирователь индексов ребер частных циклов, возникающих при построении очередного основного цикла).

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

2. Ребрам построенного основного цикла присвоим индексы, равные значению i = 1 (см. рис. 6.3).

Р
исунок 6.2

1. Выбираем вершину, принадлежащую построенному циклу и имеющую ребра без индексов. Пусть это будет опять вершина 9.

2. Полагаем i = i + j = 1 + 1 = 2, j = 1.Строим второй основной цикл с началом в вершине 9.

Р
исунок 6.3

1. Пусть построили такой маршрут 9r1a2c4f3d1. Замечаем, что при вершине 1 образовался частный цикл 1a2c4f3d1. Ребрам этого цикла присвоим индекс i + j = 2 + 1 = 3 и исключаем их из основного цикла. Переменной j присваиваем новое значение j = j + 1 =1 + 1 = 2.

2. Продолжаем строить основной цикл от вершины 1 – 9r1e4h6i5k7m8l5 – замечаем, что образовался второй частный цикл при вершине 5 – 5k7m8l5. Его ребрам присвоим индекс i + j = 2 + 2 = 4 и исключаем их из основного цикла, переменной j присвоим новое значение j = j + 1 = 2 + 1 =3.

3. Продолжаем строить основной цикл от вершины 5. Получаем 9r1e4h6i5s9. Частных циклов больше не образовалось.

4. Ребрам полученного основного цикла присвоим индекс, равный i = 2. Все ребра графа имеют индексы. Первая фаза закончена (см. рис. 6.4).

Р
исунок 6.4

Вторая фаза

1. Строим эйлеров цикл с началом в вершине 9:

9r₂1a₃2c₃4f₃3d₃1e₂4h₂6i₂5k₄7m₄8l₄5s₂9t₁8j₁6g₁3b₁2p₁9

2. Удалим введенную вершину 9 и инцидентные ей ребра. Получим две покрывающие граф цепи, не имеющие общих ребер