Главная Бухгалтерия в кармане Учет расходов Экономия на кадровиках Налог на прибыль Как увеличить активы Основные средства
Главная ->  Гамильтоновы циклы 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 [ 75 ] 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141

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

Основная теорема о существовании эйлеровых циклов формулируется так.

Теорема 4 (а). Связный неориентированный s-граф G содержит эйлеров цикл {эйлерову цепь) тогда и только тогда, когда число вершин нечетной степени равно О (О или 2).

Доказательство. Мы докажем эту теорему для случая цикла; случай цепи рассматривается аналогично.

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

Достаточность. Пусть G - связный неориентированный s-граф, все вершины которого имеют четную степень. Начнем путь из некоторой произвольной вершины Хо и пойдем по некоторому ранее не использованному ребру к следующей вершине, и так до тех пор, пока не вернемся в вершину х^ и не замкнем цикл. Если все ребра окажутся использованными, то нужный эйлеров цикл построен. Если же некоторые ребра не использованы, то пусть Ф - только что построенный цикл. Так как граф G связен, то цикл Ф должен проходить через некоторую вершину, скажем Xi, являющуюся конечной вершиной какого-либо до сих пор неиспользованного ребра. Если удалить все ребра, принадлежащие Ф, то в оставшемся графе все вершины по-прежнему будут иметь четную степень, так как в цикле Ф должно быть четное число ребер (О является четным числом), инцидентных каждой вершине.

Начиная теперь с Х;, получаем цикл Ф', начинающийся и оканчивающийся в Xi. Если все оставшиеся ранее ребра использованы для цикла Ф', то процесс окончен. Нужный эйлеров цикл будет образован частью цикла Ф от вершины х^ до xi, затем циклом Ф' и, наконец, частью цикла Ф от вершины до х^. Если же все еще остались неиспользованные ребра, то объединение построенных выше циклов Ф и Ф' дает новый цикл Ф. Мы снова можем найти вершину Xj, принадлежащую циклу и являющуюся концевой вершиной некоторого неиспользованного ребра. Затем мы можем приступить к построению нового цикла Ф', начинающегося в Xj, и так продолжать до тех пор, пока не будут использованы все ребра и не будет получен таким образом эйлеров цикл Ф. Это доказывает теорему.



1) В этой теореме, естественно, циклы и цепи - ориентированные.- Прим. ред.

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

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

Если G - ориентированный s-граф, то справедлива теорема, полностью аналогичная предыдущей, а именно

Теорема 4 (б). Связный ориентированный s-граф G содержит эйлеров цикл [эйлерову цепь) тогда и только тогда ), когда все полустепени захода dt [xi) и полустепени исхода d (х,) вершин удовлетворяют условиям:

для случая цикла dt {Xi) = dQ {Xi,)Xi 6 X,

для случая цепи dt(Xi) = do{Xi)Xi р или д, dt (д) - do (д) + 1 и dt (р) = do (р) - 1, где р - начальная, ад - конечная вершины эйлеровой цепи.

Флёри [16] дал очень простой алгоритм построения эйлерова цикла в неориентированном графе (если такой цикл существует). Этот алгоритм легко может быть распространен на ориентированные графы (см. также задачи 7 и 8) и состоит в следующем. Алгоритм нахождения эйлерова цикла. Начинать с некоторой вершины р и каждый раз вычеркивать пройденное ребро. Не проходить по ребру, если удаление этого ребра приводит к разбиению графа на две связные компоненты (не считая изолированных вершин).

5.1. Некоторые родственные задачи

Сразу же вспоминается ряд вопросов, связанных с тем, имеется ли в неориентированном графе эйлеров цикл. Например:

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

(ii) Ребрам графа G приписаны положительные веса. Требуется найти цикл, проходящий через каждое ребро графа G по крайней мере один раз и такой, что для него общий вес (а именно сумма величин njC (aj), где число П] показывает, сколько раз проходи-



лось ребро uj, а с (aj) - вес ребра) минимален. Очевидно, что если G содержит эйлеров цикл, то любой такой цикл будет оптимальным, так как каждое ребро проходится только один раз и вес

ЭТОГО цикла равен тогда 2! ij)-

Сформулированная выше задача (ii) называется задачей китайского почтальона [18], и ее решение имеет много потенциальных приложений, как например:

(A) Сбор мусора. Рассмотрим проблему сбора домашнего мусора. Допустим, что определенный район города обслуживается единственной машиной. Ребра графа G представляют дороги, а вершины - пересечения дорог. Величина с (aj) - вес ребра - будет соответствовать длине дороги. Тогда проблема сбора мусора в данном районе сводится к нахождению цикла в графе G, проходяш;его по каждому ребру G по крайней мере один раз. Требуется найти цикл с наименьшим километражем. В действительности емкость машины и продолжительность рабочего дня накладывают ограничения на число улиц, которые может обслужить одна машина за день. То, что действительно может требоваться,- это не нахождение отдельного цикла, а некоторого числа Q циклов, обслуживаемых по одному в день, скажем, за период в Q дней; при этом циклы могут быть выбраны так, что не нарушаются вышеупомянутые ограничения [1, 2, 4, 11, 22].

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

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

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

5.2. Алгоритм для задачи китайского почтальона

В случае когда веса всех ребер равны единице, задачу китайского почтальона рассмотрели Беллман и Кук [3] с использованием динамического программирования. Более общую задачу.



1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 [ 75 ] 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141

© 2024 Constanta-Kazan.ru
Тел: 8(843)265-47-53, 8(843)265-47-52, Факс: 8(843)211-02-95