МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное образовательное учреждение

высшего профессионального образования

«Чувашский государственный университет им. И.Н. Ульянова»

Факультет информатики и вычислительной техники

Кафедра математическое и аппаратное обеспечение информационных систем

Курсовая работа по дисциплине

Дискретная математика

На тему:

«Обходы графов»

Выполнила студентка

Чебоксары  2007

Содержание

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

Обходы графа по глубине и ширине.

Алгоритм на псевдоязыке

Поиск в глубину.

Поиск в ширину

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

Опишем одну из задач, положивших начало теории графов, - задачу о кенигсбергских мостах. На рис.1  схематично изображена карта города Кенигсберг в 18 в. Город был расположен на берегах и двух островах реки Преголи. Острова между собой и берегами были связаны семью мостами. Возник вопрос: можно ли, выйдя из дома, вернуться обратно, пройдя по каждому мосту ровно один раз?

                          рис.1                                                             рис.2

Неориентированный мультиграф G, представляющий задачу, показанную на рис.2. Вершины , соответствуют берегам реки,- островам, ребра мультиграфа – мостам. Следовательно, на языке теории графов задача формулируется следующим образом: существует ли в мультиграфе цикл, содержащий все ребра данного мультиграфа?

Выдающимся математиком и механиком Л. Эйлером сформулирован и доказан критерий того, связный неориентированный мультиграф имеет цикл, содержащий все ребра данного мультиграфа. Цикл, содержащий все ребра мультиграфа, называется эйлеровым, и мультиграф, в котором имеется эйлеров цикл, также называется эйлеровым.

Теорема 1: Связный неориентированный мультиграф тогда и только тогда является эйлеровым, когда степень каждой из его вершин – четное число.

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

Опием алгоритм построения эйлерова цикла в эйлеровом мультиграфе. Этот алгоритм задается следующими правилами:

1. Выбрать произвольно некоторую вершину a.
2. Выбрать произвольно некоторое ребро, и инцидентное a, и присвоить ему номер один (назовем это ребро пройденным).
3. Каждое пройденное ребро вычеркнуть и присвоить ему номер, на единицу больший номера предыдущего вычеркнутого ребра.
4. Находясь в вершине x, не выбирать ребро, соединяющее x с a, если имеется возможность иного выбора.
5. Находясь в вершине x, не выбирать ребро, которое является перешейком (т.е. ребром, при удалении которого граф, образованный невычеркнутыми ребрами, распадается на две компоненты связности, каждая из которых имеет хотя бы по одному ребру).
6. После того, как в графе будут занумерованы все ребра, образуется эйлеров цикл, причем порядок нумерации соответствует последовательнотси обхода ребер

Теорема 2: Если связный граф содержит k вершин нечетной степени, то минимальное число покрывающих его реберно непересекающихся цепей равно .

В частности, при k=2 граф имеет цепь, которая соединяет вершины нечетной степени и содержит все ребра графа. Цепь, содержащая все ребра графа, называется эйлеровой.

Мы рассмотрели обходы ребер графа. Следующей нашей целью является изучение обходов вершин графа.

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

рис.3

Математическая постановка задачи выглядит так: требуется найти гамильтонов цикл минимального веса. Ниже изложены некоторые практические задачи, сводящиеся к задаче коммивояжера:

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

Обходы графа по глубине и ширине.

Теорема 3: Если граф G связен (и конечен), то поиск в ширину и поиск в глубину обойдут все вершины по одному разу.

Доказательство

1. Единственность обхода вершины. Обходятся только вершины, попавшие в T. В T попадают только неотмеченные вершины. При попадании в T вершина отмечается. Следовательно, любая вершина будет обойдена не более одного раза.
2. Завершаемость алгоритма. Всего в T может попасть не более p вершин. На каждом шаге одна вершина удаляется из T. Следовательно, алгоритм завершит работу не более чем через p шагов.
3. Обход всех вершин. От противного. Пусть алгоритм закончил работу, и вершина w не обойдена. Значит w не попала в T. Следовательно, она не была отмечена. Отсюда следует, что все вершины, смежные с  w, не были обойдены и отмечены. Аналогично, любые вершины, смежные с неотмеченными, сами не отмечены (после авершения алгоритма). Но G связен, значит, существует путь . Следовательно, вершина v не отмечена. Но она была отмечена на первом шаге.

ч.т.д.

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

Алгоритм на псевдоязыке

Вход: граф , представленный списками смежности Г.

Выход: последовательность вершин обхода.

  for do

    :=0 {вначале все вершины не отмечены}

  end for

  select {начало обхода – произвольная вершина}

  {помещаем в структуру данных …}

  :=1 {…и отмечаем вершину }

  repeat

    {извлекаем вершину из структуры данных …}

    yield {… и возвращаем ее в качестве очередной пройденной вершины}

    for do

      if =0 then

        {помещаем в структуру данных …}

        :=1  {… и отмечаем вершину }

      end if

    end for

  until =Ø

Если - это стек (LIFO – Last In First Out), то обход называется поиском в глубину. Если - это очередь (FIFO – First In First Out), то обход называется поиском в глубину.

Пример

В следующей таблице показаны протоколы поиска в глубину и в ширину для графа, диаграмма которого приведена на рис.4. Слева в таблице протокол поиска в глубину, а справа – в ширину. Предполагается, что начальной является вершина 1.

Поиск в глубину.

Идея метода. Поиск начинается с некоторой фиксированной вершины v. Рассматривается вершина u, смежная с v. Она выбирается. Процесс повторяется с вершиной u. Если на очередном шаге мы работаем с вершиной q и нет вершин, смежных с q и не рассмотренных ранее (новых), то возвращаемся из вершины q к вершине, которая была до нее. В том случае, когда это вершина v, процесс просмотра закончен. Очевидно, что для фиксации признака, просмотрена вершина графа или нет, требуется структура данных типа: Nnew: Array [1..N]Of Boolean.

Пример. Пусть граф описан матрицей смежности A. Поиск начинается с первой вершины. На рис.1 приведен исходный граф, а на рис.2 у вершин в скобках указана та очередность, в которой вершины графа просматривались в процессе поиска в глубину.

Логика.

Procedure Pg (v: Integer); {Массивы Nnew и A глобальные.}

   Var j: Integer;

  Begin

    Nnew [v]:=False;

    Write(v:3);

    For j:=1 To N Do

       If (A[v,j]<>0) And Nnew[j]

         Then Pg(j);

   End;

Фрагмент основной логики.

…

FillChar (Nnew, SizeOf(Nnew), True);

  For i:=1 To N Do If Nnew [i] Then Pg(i);

…

Рассмотрим рекурсивную реализацию данного алгоритма. Глобальные структуры данных прежние: A – матрица смежностей; Nnew – массив признаков. Номерf просмотренных вершин графа запоминаются в стеке St, указатель стека – переменная yk.

Procedure Pgn (v: Integer);

Var St: Array [1..N] Of Integer;

        yk,t, j: Integer;

        pp: Boolean;

Begin

  FillChar (St, SizeOf(St), 0); yk:=0;

  Inc (yk); St[yk]:=v; Nnew[v]:= False;

  While yk<>0 Do Begin {Пока стек не пуст}

    t:=St[yk]; {Выбор “самой верхней” вершины из стека}

    j:=1; pp:=False;

Repeat

    If (A[t,j]<>0) And Nnew [j] Then pp:=True

       Else Inc (j);

   Until pp Or (j>=N);  {Найдена новая вершина или все вершины, связанные с анной вершиной, просмотрены}

   If pp Then Begin

   Inc (yk);

   St[yk]:=j;

  Nnew [j]:= False; {Добавляем номер вершины в стек}

       End;

   Else Dec (yk); {“Убираем” номер вершины из стека}

End;

End;

Рис.1                                                                Рис.2

Поиск в ширину

Идея метода. Суть заключается в том, чтобы рассмотреть все вершины, связанные с текущей. Принцип выбора следующей вершины – выбирается та, которая была раньше рассмотрена. Для реализации данного принципа необходима структура данных очередь.

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

Логика просмотра вершин.

Procedure Pw (v: Integer);

Var Og: Array [1..N] Of 0..N; {Очередь}

        yk1, yk2:Integer; {Указатели очереди, yk1 – запись, yk2 - чтение}

        j: Integer;

Begin

   FillChar (Og, SizeOf(Og), 0);

    yk1:=0; yk2:=0; {Начальная инициализация}

           Inc (yk1); Og[yk1]:=v; Nnew[v]:= False; {В очередь – вершину v}

   While yk2<yk1 Do Begin {Пока очередь не пуста}

     Inc (yk2); v:= Og[yk2]; Write (v:3); {Берем элемент из очереди}

   For j:=1 To N Do {Просмотр всех вершин, связанных с вершиной v}

     If (A[v,j]<>0) And Nnew [j] Then Begin {Если вершина ранее не просмотрена, то заносим ее номер в очередь}

       Inc (yk1); Og [yk1]:=j; Nnew[j]:= False;

     End;

  End;

End;

    Рис.3

11