Теория графов

По предположению индукции в каждом из них существует эйлеров цикл . Строим теперь новый путь из A следующим образом:

– идем по старому пути до ;

– включаем в него новый путь ;

– идем по старому пути от  до ;

– повторяем процесс для вершины и т.д.

Для окончания доказательства (и построения алгоритма) заметим, что база индукции очевидна: если ребро одно, то оно – петля.

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

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

Program Euler;

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)

      );

Type

    list=^node;

    node=record

             i: integer;

          next: list

         end;

Var stack1, stack2: list;

        v, u, x, i: integer;

 

Procedure Push(x: integer; var stack: list);

Var temp: list;

Begin

   New(temp);

   temp^.i:=x;

   temp^.next:=stack;

   stack:=temp

End;

 

Procedure Pop(var x: integer; var stack: list);

Begin

   x:=stack^.i;

   stack:=stack^.next

End;

 

Function Peek(stack: list): integer;

Begin

   Peek:=stack^.i

End;

 

Procedure PrintList(l: list);

Begin

   Writeln;

   If l=nil then writeln('NIL');

   While l<>nil do

   Begin

     Write(l^.i:3);

     l:=l^.next

   End

End;

 

Begin

  stack1:=nil;

  stack2:=nil;

  Write('Начальная вершина: ');readln(v);

  Push(v, stack1);

  While stack1<>NIL do

  Begin

    v:=peek(stack1);

    i:=1;

    While (i<=n) and not m[v, i] do inc(i);

    If i<=n then

            Begin

              u:=i;

              Push(u, stack1);

              m[v, u]:=False;

              m[u, v]:=False;

            End

            else

            Begin

              pop(x, stack1);

              push(x, stack2)

            End

  End;

  PrintList(stack2)

End.

 

 

 

 

 

 

 

 

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

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

Или в терминах  теории графов:

Дан граф с n вершинами; длины ребер заданы матрицей. Найти остовное дерево минимальной длины.

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

Удивительно, но в задаче Прима–Краскала, которая не кажется особенно простой, жадный алгоритм дает точное оптимальное решение.

Как известно (это легко доказать по индукции), дерево с n вершинами имеет n-1 ребер. Оказывается, каждое ребро нужно выбирать жадно (лишь бы не возникали циклы). То есть n-1 раз выбирать самое короткое ребро из еще не выбранное ребро при условии, что оно не образует цикла с уже выбранными.

А как следить, чтобы новое ребро не образовывало  цикла со старыми? Сделать это просто. До построения дерева окрасим каждую вершину i в отличный от других цвет i. При выборе очередного ребра, например (i, j), где i и j имеют разные цвета, вершина j и все, окрашенные в ее цвет (т.е. ранее с ней соединенные) перекрашиваются в цвет i. Таким образом, выбор вершин разного цвета обеспечивает отсутствие циклов. После выбора n-1 ребер все вершины получают один цвет.

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

Если к дереву добавить ребро, то в дереве появится цикл, содержащий это ребро.

Действительно, пусть добавлено ребро (u, v) – “добавлено” означает, что ребро – новое, что раньше его в дереве не было. Поскольку дерево является связанным графом, то существует  цепь  C(u, …, v) из нескольких ребер, соединяющая вершины u и v. Добавление ребра (u, v) замыкает цепь, превращая ее в цикл.

Теорема. Алгоритм Прима–Краскала получает минимальное остовное дерево.

Доказательство. Результатом работы алгоритма является набор из n-1 ребер. Они не образуют цикла, ибо на каждом из n-1 шагов соединялись вершины разного цвета, т.е. ранее не связанные. Этот граф связный, потому что после проведения  1-го ребра осталось n-1 разных цветов, …, после проведения (n-1)-го ребра остался один цвет, т.е. одна компонента связности. Итак, полученный набор ребер образует связный граф без циклов, содержащий n-1 ребер и n вершин. Следовательно, граф есть остовное дерево. Осталось доказать, что оно имеет минимальную длину. Пусть { , , …, } ребра остовного дерева в том порядке как их выбирал алгоритм, т.е. £ . Предположим для простоты доказательства, что все ребра сети имеют разную длину, т.е.

                                                    < <…<                                          (1)

Если полученное дерево не минимально, то существует другое дерево, заданное набором из n-1 ребер { , , …, }, такое что сумма длин меньше суммы длин . С точностью до обозначений

                                                    < <…<                                       (2)

Может быть = , = и т.д., но так как деревья разные, то в последовательностях (1) и (2) найдется место, где ребра отличаются. Пусть самое левое такое место – k, так что ¹ . Поскольку выбиралось по алгоритму самым малым  из не образующих цикла с ребрами , , …, , то < . Теперь добавим к дереву (2) ребро ; в нем появится цикл, содержащий ребро и, может быть, какие-то (или все) ребра , , …, , но они сами не образуют цикла, поэтому в цикле будет обязательно ребро d из набора , …, , причем d> . Выбросим из полученного графа с одним циклом ребро d; мы снова получим дерево, но оно будет на d- короче минимального, что невозможно. Полученное противоречие доказывает теорему для сети со всеми разными ребрами.

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

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

  Color – массив цветов вершин;

  Ribs – в этом массиве запоминаются найденные ребра;

  a, b – вершины, соединяемые очередным минимальным ребром

  len – длина дерева.

Матрицу расстояний будем хранить в текстовом файле INPUT.MTR, где число на первой строке – количество вершин n, а остальные n строк по n чисел в каждой – матрица расстояний. Если расстояние равно 1000 (Infinity), то такого ребра нет.

 

Program Algorithm_PrimaKrascala;

Uses Crt;

Const MaxSize =100;

            Infinity =1000;

Var   Matrix: array[1..MaxSize, 1..MaxSize] of integer;

          Color: array[1..MaxSize] of integer;

            Ribs: array[1..MaxSize] of record

                                                        a, b: integer;

                                                    end;

   n, a, b, k, col, i, len: integer;

 

Procedure Init;

Var    f: text;

        i, j: integer;

Begin

   Assign(f, 'INPUT.MTR');

   Reset(f);

   Readln(f, n);

   For i:=1 to n do

   Begin

     For j:=1 to n do read(f, matrix[i, j]);

     Readln(f)

   End;

   For i:=1 to n do color[i]:=i;

   len:=0

End;

 

Procedure Findmin(var a, b: integer);

Var min, i, j: integer;

Begin

   min:=infinity;

   For i:=1 to n-1 do

     For j:=i+1 to n do

      If (Matrix[i, j]<min) and (color[i]<>color[j]) then

         Begin

           min:=Matrix[i, j];

           a:=i;

           b:=j

         End;

   len:=len+min

end;

 

Begin

  Clrscr;

  Init;

  For k:=1 to n-1 do

  Begin

    Findmin(a, b);

    Ribs[k].a:=a;

    Ribs[k].b:=b;

    col:=Color[b];

    For i:=1 to n do

      If color[i]=col then color[i]:=color[a];

  End;

  For i:=1 to n-1 do

     Writeln(ribs[i].a, ' –', ribs[i].b);

  Writeln('Length= ', len);

  Readkey

End.

Для такого входного файла

8

0        23      12    1000  1000  1000  1000  1000

23      0        25    1000  22      1000  1000  35

12      25      0       18      1000  1000  1000  1000

1000  1000  18      0       1000  20       1000  1000

1000  22      1000  1000  0       23       14      1000

1000  1000  1000  20     23    0         24      1000

1000  1000  1000  1000  14      24      0        16

1000  35      1000  1000  1000  1000 16      0

программа напечатает:

1–3

5–7

7–8

3–4

4–6

2–5

1–2

Length= 125.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

Дана дорожная сеть, где города и развилки будут вершинами, а дороги – ребрами. Требуется найти кратчайший путь между двумя вершинами.

Можно предложить много процедур решения этой задачи, например, физическое моделирование такого рода: на плоской доске рисуется карта местности, в города и в развилки вбиваются гвозди, на каждый гвоздь надевается кольцо, дороги укладываются веревками, которые привязываются к соответствующим кольцам. Чтобы найти кратчайшее расстояние между кольцом i и кольцом k, нужно взять i в одну руку, взять k в другую и растянуть. Те веревки, которые натянутся и не дадут разводить шире, и образуют кратчайший путь между i и k. Однако, математическая процедура, которая промоделирует эту физическую, выглядит очень сложно. Известны алгоритмы попроще, например, предложенный Дейкстрой еще в 1959 г. Этот алгоритм решает более общую задачу:

В ориентированной, неориентированной или смешанной сети найти кратчайший путь из заданной вершины во все остальные вершины.

Алгоритм использует три массива  из n чисел каждый. Первый массив Visited содержит метки с двумя значениями: False (вершина еще не рассмотрена) и True (вершина уже рассмотрена); второй массив Len содержит расстояния от – текущие кратчайшие расстояния от начальной до соответствующей вершины; третий массив C содержит номера вершин – k-ый элемент C есть номер предпоследней вершины на текущем кратчайшем пути из начальной вершины в k-ю. Используется также Matrix – матрица расстояний.

Опишем алгоритм Дейкстры:

1 (инициализация). В цикле от 1 до n заполнить значением False массив Visited; заполнить числом i массив C (i – номер стартовой вершины); перенести i-ю строку матрицы Matrix в массив Len;

Visited[i]:=True; C[i]:=0;

2 (общий шаг). Найти минимум среди неотмеченных (т.е. тех к, для которых Visitid[k]=False); пусть минимум достигается на индексе j, т.е. Len[j]£Len[k];

Затем выполнять следующие операции:

Visited[i]:=True;

если Len[k]>Len[j]+Matrix[j, k], то (Len[k]:=Len[j]+Matrix[j, k]; C[k]:=j)

{Если все Visited[k] отмечены, то длина пути от до равна C[k]. Теперь надо перечислить вершины, входящие в кратчайший путь}.

3 (выдача ответа). {Путь от до выдается в обратном порядке следующей процедурой:}

1. z:=C[k];
2. Выдать z
3. z:=C[z]. Если z =0, то конец,

иначе перейти к 3.2.

Теорема. Алгоритм Дейкстры – корректен.

Доказательство. Теорему докажем по индукции. Рассмотрим 1-й шаг, когда находится min Len[k] (k¹i), пусть минимум достигается на вершине j. Остальные (k¹i, j) пока лишь верхние оценки длин путей из в (они могут уменьшаться в ходе выполнения алгоритма, но Len[j] – окончательная длина пути [ … ], совпадающего с дугой [ , ]. Если бы существовал путь короче, он бы выглядел [ , … ], но уже первая его дуга не меньше, чем весь путь [ , ], а остальные дуги имеют положительную длину).

Мы разбили все вершины на два класса: С – неотмеченных вершин и С’ – отмеченных вершин. После 1-го общего шага , Î С’, и, очевидно, все кратчайшие пути (пока “все” – означает “один”) из v’ÎС’ не содержат vÎС в качестве промежуточной.

Теперь сделаем индуктивный шаг. Уже проделано s общих шагов, уже С’={ , , , …, }, при этом все кратчайшие пути из в v’ не содержат вершин из С в качестве промежуточных.

Найдем минимальное Len[l] в неотмеченных столбцах; пусть минимум достигается на вершине . Соответственный элемент , меняясь, мог принимать только номера отмеченных вершин, значит в вершину идет путь, где все вершины, кроме конечной , – штрихованные, т.е. принадлежащие С’. Любой другой путь [ … ], содержащий хотя бы еще одну не штрихованную  вершину, будет длиннее. Теорема доказана.