Циклы Эйлера

Под циклом Эйлера понимается простой цикл из всех ребер графа.

Цикл Эйлера может в графе не существовать, но если он существует, то весь граф может быть нарисован на бумаге без отрыва карандаша от бумаги таким образом, что по каждому ребру карандаш пройдет ровно один раз и начальная вершина совпадёт с конечной. Условие существования цикла Эйлера определяется следующей теоремой.

Теорема. Цикл Эйлера существует тогда и только тогда, когда в нем нет вершин нечётной степени.

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

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

2.5.6. Поток в транспортной сети

Транспортной сетью называют связный граф без контуров, в котором:

- существует единственная вершина x₀, из которой дуги только выходят, называемая входом сети;

- существует единственная вершина z, в которую дуги только заходят, называемая выходом сети;

- каждая дуга (i,j) взвешена неотрицательным целым числом с_ij, называемым пропускной способностью дуги.

Потоком в сети j называется целочисленная функция, заданная на дугах графа, такая, что:

- для любой дуги 0£j_ij £ с_ij;

- для любой вершины i, кроме входа и выхода сети, имеет место равенство
Sj_ij = Sj_ji,
jÎP jÎQ

где Р - множество вершин, связанных с вершиной i по исходящим, Q -по заходящим дугам.

Последнее равенство означает, что суммарный поток, входящий в вершину, равен суммарному потоку, выходящему из неё. Из этого равенства и из того, что в сети нет контуров, следует, что суммарный поток, исходящий из вершины x₀, равен суммарному потоку, заходящему в вершину z, т.е. Sj_0j=Sj_zi=j. Эта величина называется величиной потока.

Задача состоит в том, чтобы для заданной сети определить поток, имеющий максимальную величину.

Назовем дугу насыщенной, если для нее величина потока равна пропускной способности дуги: j_ij=с_ij. Путь между вершинами x₀ и z назовём полным, если он содержит хотя бы одну насыщенную дугу. Поток назовем полным, если в нём любой путь полный.

Рассмотрим алгоритм решения этой задачи, предложенный Фордом и Фалкерсоном.

Алгоритм Форда и Фалкерсона.

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

2. Проведем последовательную разметку графа:

- вершину x ₀ пометим символом 0;

- если вершина х_i отмечена, то непомеченные вершины, связанные с ней по исходящим дугам, пометим как + i, если дуга не насыщена, и связанные по заходящим дугам как - i, если поток в дуге не равен нулю. Если в результате разметки будет помечен выход сети, то переходим к пункту 3, иначе - конец алгоритма.

3. Разметка выделяет цепь между входом и выходом сети. Будем двигаться по ней от входа к выходу и изменять поток в проходимых дугах по правилу: если направление движения совпадает с направлением дуги, то значение потока увеличим на единицу, если противоположен, то уменьшим на единицу. Так как для дуги цепи, исходящей из входа, и дуги, заходящей в выход сети, направление дуги и направление движения всегда совпадают, то в результате величина потока увеличится.

После этого переходим к пункту 2.

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

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

Пример. Рассмотрим транспортную сеть, приведенную на рис 2.11. Здесь цифрами в скобках отмечена величина потока по дугам, без скобок - пропускные способности. Нетрудно убедиться, что поток является полным, т.е. по каждому пути его увеличить нельзя. Жирными линиями выделена цепь, полученная после разметки графа в соответствии с п. 3 алгоритма. По этому пути поток по дугам (х 1, х 4), (х 4, х 6),(х 2, х 7) и (х 7, х 8) увеличится на единицу, поток по дуге (х 2, х 6) уменьшится на единицу, общий поток увеличится на единицу.

Повторная разметка графа невозможна, значит, полученный поток максимален.

Разобьем множество вершин А сети на два подмножества, А 1 и А 2, при котором в первое подмножество включен вход сети, во второе - её выход. Множество дуг, начинающихся в А 1 и заканчивающихся в А 2, называется разрезом сети, а сумма пропускных способностей этих дуг называется величиной разреза.

Разрез, величина которого минимальна, называется минимальным разрезом.

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

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

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

Дата добавления: 2014-01-07