Теория графов и ее применение

Федеральное агентство по образованию 

ГОУ ВПО «Уральский государственный технический университет - УПИ»

Институт образовательных информационных технологий

Факультет дистанционного образования

 

 

 

 

Курсовая работа

по   ТИС  № 1

^{(ДИСЦИПЛИНА)}

   на тему: Теория графов и её применение 

 

 

 

 

 

 

 

 

 

 

 

Преподаватель  Александров О.Е. 

^{(ученое звание, ФИО)}

Студент гр. № ДО43019д Соловьев В.В. 

^(ФИО)

 

 

 

 

 

Екатеринбург

2007

 

Содержание.

 

 

 

1. Элементы теории графов

 

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

 

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

 

4. Эйлеровы циклы

 

5. Задача Прима–Краскала

 

6. Алгоритм Дейкстры

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Элементы теории графов.

Граф - совокупность точек  и линий, в которой каждая линия  соединяет две точки. Точки называются вершинами, или узлами, графа, линии - ребрами графа. Если ребро соединят две вершины, то говорят, что оно им инцидентно; вершины, соединенные ребром называются смежными.  Две вершины,  соединенные ребром,  могут совпадать; такое ребро называется петлей.  Число ребер, инцидентных вершине, называется степенью  вершины.  Если  два ребра инцидентны одной и той же паре вершин,  они называются  кратными;  граф,  содержащий кратные ребра, называется мультиграфом. 

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

  Граф однозначно  задан,  если заданы множество  его вершин,  множество ребер и указаны все  инцидентности  (т.е.  указано,  какие вершины какими ребрами соединены). Наиболее наглядно граф задается рисунком;  однако не все детали  рисунка  одинаково  важны;  в частности, несущественны  геометрические  свойства ребер (длинна, кривизна и т.д.) и взаимное расположение вершин на плоскости.

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

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

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

  Задача состоит  в том,  найти путь из вершины  A в вершину B. Будем задавать граф матрицей смежности,  т.е.  квадратной  таблицей NxN,  в которой на пересечении i-й строки и j-го столбца значение TRUE, если i и j соединены ребром, и FALSE в противном случае.

 

 

 

 

 

 

 

 

 

 

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

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

  Для реализации  алгоритма понадобятся: 

  матрица m[1..n, 1..n] - матрица смежности графа;

  вспомогательный  массив  queue[1..n],  в  котором  будет формироваться очередь, т.е. тип данных первый вошел – первый вышел (FIFO). Размер его достаточен,  так как мы не посещаем вершины дважды. С массивом queue связаны две переменные - head и tail. В переменной head будет находиться номер текущей вершины,  из которой идет волна, а при помощи  переменной  tail  новые  вершины  помещаются  в "хвост" очереди queue;

  вспомогательный  массив visited[1..n],  который нужен  для  того, чтобы отмечать уже пройденные вершины (visited[i]=TRUE <=> вершина i пройдена);

  вспомогательный массив  prev[1..n] для хранения пройденных вершин. В этом массиве и будет сформирован искомый путь;

  переменная f,  которая  примет  значение TRUE,  когда путь будет  найден.

  Кроме того, мы введем несколько  вспомогательных переменных, которые  понадобятся при организации  циклов.

  Program breadth_first_search;

  Const n=9;

        m:array[1..n, 1..n] of boolean =

        (

           (False, True,  True,  False, False, False, False, False, False),

           (True,  False, True,  False, False, False, True,  True,  False),

           (True,  True,  False, True,  True,  False, False, False, False),

           (False, False, True,  False, True,  False, False, False, False),

           (False, False, True,  True,  False, True,  False, True,  False),

           (False, False, False, False, True,  False, True,  True,  True ),

           (False, True,  False, False, False, True,  False, True,  True ),

           (False, True,  False, False, True,  True,  True,  False, False),

           (False, False, False, False, False, True,  True,  False, False)

        );

  Var A, B: integer;

 

   Procedure A_to_B(A, B: integer);

   Var

        Visited: array[1..n] of boolean;

           Prev: array[1..n] of integer;

           c: array[1..n] of integer;

     head, tail: integer;

              f: boolean;

        i, v, k: integer;

   Begin

     head:=1;

    tail:=1;

     f:=False;

     For i:=1 to n do

     Begin

       Visited[i]:=False;

       Prev[i]:=0

     End;

     C[tail]:=A;

     Visited[A]:=True;

     While (head<=tail) and not f do

-

       v:=C[head];

       head:=head+1;

       For k:=1 to n do

         if m[v, k] and not Visited[k] then

                                       Begin

                                         tail:=tail+1;

                                         C[tail]:=k;

                                         Visited[k]:=True;

                                         Prev[k]:=v;

                                         if k=B then

                                                Begin

                                                  f:=true;

                                                  break

                                                End

                                       End

     End;

     if f then

          Begin

            k:=B;

            Write(B);

            While Prev[k]<>0 do

            Begin

              Write('<-', Prev[k]);

              k:=Prev[k]

            end

          End

          else

               Write('Пути из ', A, ' в ', B, ' нет')

   end;

 

  Begin

    Write('A= '); readln(A);

    Write('B= '); readln(B);

    A_to_B(A, B)

  End.

 

 

 

 

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

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

  Заметим, что построенный  таким образом алгоритм способен  находить все пути из A в B,  но первый найденный необязательно должен быть кратчайшим.

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

  матрица m[1..n, 1..n] - матрица смежности  графа;

  вспомогательный массив visited[1..n],  который мы будем для того, чтобы  отмечать  уже  пройденные  вершины (visited[i]=TRUE <=> вершина i пройдена);

  переменная f,  которая  примет  значение TRUE,  когда путь будет  найден.

 

  Program depth_first_search;

  Const n=9;

        m:array[1..n, 1..n] of boolean =

        (

           (False, True,  True,  False, False, False, False, False, False),

           (True,  False, True,  False, False, False, True,  True,  False),

           (True,  True,  False, True, True,  False, False, False, False),

           (False, False, True,  False, True,  False, False, False, False),

           (False, False, True,  True,  False, True,  False, True,  False),

           (False, False, False, False, True,  False, True,  True, True ),

           (False, True,  False, False, False, True,  False, True,  True ),

           (False, True,  False, False, True,  True,  True,  False, False),

           (False, False, False, False, False, True,  True,  False, False)

        );

  Var A, B: integer;

 

   Procedure A_to_b(A, B: integer);

   Var

      Visited: array[1..n] of boolean;

             f: boolean;

             i: integer;

 

    Procedure Depth(p: integer);

    var k: integer;

    Begin

      Visited[p]:=True;

      For k:=1 to n do

        If not f then

          If m[p, k] and not Visited[k] then

            If k=B then

                   Begin

                     f:=True;

                     Write(B);

                     Break

                   End

                   else Depth(k);

      If f then write('<=', p);

    End;

 

   Begin

     For i:=1 to n do Visited[i]:=False;

     f:=false;

     Depth(A);

     If not f then write('Пути из ', A, ' в ', B, ' нет')

   End;

 

 

  Begin

    write('A= '); readln(A);

    write('B= '); readln(B);

    A_to_B(A, B)

  End.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Эйлеровы циклы.

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

  Задача возникла из предложенной  Эйлеру головоломки,  получившей  название "проблема кенигсбергских мостов". Река Прегель, протека ющая через  Калининград  (прежде  город  назывался Кенигсбергом), омывает два острова. Берега реки связаны с островами так, как это показано на  рисунке.  В  головоломке  требовалось найти маршрут, проходящий по всем участкам суши таким образом,  чтобы каждый  из мостов был пройден ровно один раз,  а начальный и конечный пункты маршрута совпадали.

 

 

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

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