Поиск эйлерова пути в графе. 


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Поиск эйлерова пути в графе.



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

Теорема 1. Эйлеров путь в неориентированном графе существует тогда и только тогда, когда граф связан и содержит не более двух вершин нечетной степени.

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

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

 

v:=произвольная вершина графа, обычно первая;

STACK<=v;{вершина заносится в стек}

while (STACK не пуст) do

begin

v:=верхний элемент стека STACK;

if (в графе еще есть вершины,

связанные с v) then

begin

u:=любая вершина, связанная с v;

STACK<=u;

удаляем ребро {v,u} из графа;

end

else

begin

v<=STACK;{вершина удаляется из стека}

RES<=v{вершина заносится в результат}

end

end;

 

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

 

procedure search(v:byte);

var j:byte;

begin

for j:=1 to n do

if a[v,j]=1 then

begin

a[v,j]:=0;a[j,v]:=0;

search(j)

end;

inc(p);

res[p]:=v

end;

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

Теорема 2. Эйлеров путь в ориентированном графе существует тогда и только тогда, когда граф связан, все вершины, кроме быть может двух, имеют нулевую степень. Допустимым является лишь наличие одной вершины степени 1 и одной — степени –1.

Очевидно, что при наличии двух вершин ненулевой степени в ориентированном графе, начинаться эйлеров путь должен в вершине со степенью 1, а заканчиваться — в вершине со степенью –1. Интересно, что схема поиска самого пути при этом остается неизменной. А в процедуре search следует лишь убрать обнуление элемента матрицы смежности a[j,v], т.к. в ориентированном графе каждому ребру соответствует один элемент матрицы, а не два.

Задача 1. Для решения транспортной проблемы в некотором городе до недавнего времени использовались N (N ≤100) автобусных маршрутов. Каждый маршрут начинался на одной из M (M ≤200) площадей и там же заканчивался. В процессе проезда по маршруту автобус мог несколько раз проезжать одну и ту же площадь, но не мог проезжать более одного раза по одной и той же улице в том же самом направлении.

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

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

Раздел 4



Поделиться:


Последнее изменение этой страницы: 2017-02-07; просмотров: 168; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.232.66.188 (0.007 с.)