ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Dmitry Volkov                        2:5015/185.5   12 Jun 2002  10:37:04
 To : All
 Subject : FAQ "Алгоритмы на графах" [2/4]
 -------------------------------------------------------------------------------- 
 

 Q:> Что такое каркас?
 A:> Еще немного определений:
 
     _Путем_, соединяющим вершины u и v,  называют  такую  последовательность 
  v[0], v[1], ..., v[n] (n>=0), что v[0]=u, v[n]=v и для любого i (0<=i<=n-1)
  вершины v[i] и v[i+1] - смежные.
     Граф  называется  _связным_, если  для любой  пары  вершин  существует 
  соединяющий их путь.
     _Деревом_ называют произвольный связный неориентированный граф без 
  циклов.
     Или, что одно и то же, связный граф содержащий N вершин и N-1 ребер.
     Для  произвольного  связного неориентированного графа G=(V, E) каждое 
  дерево (V, T), где T принадлежит E, называют _стягивающим деревом(каркасом,_
  _остовом)._
 
   * 5.1. _Поиск произвольного каркаса_ *
 
     С помощью процедуры поиска  в глубину или в ширину. Т.е. в каркасе есть 
  ребро (i,j),если мы с помощью одной из процедур попали либо из вершины i в 
  вершину j, либо наоборот из j в i.
 [...]
 // 5.2. Поиск всех различных каркасов - планируется в будующей версии //
 [...]
 
   * 5.3. _Поиск каркаса минимального веса_ *
 
     (Применяется для взвешенного графа)
     _Ограничения:_ дан связанный неориентированный граф,каждому ребру которого 
  приписан _неотрицательный_ вес.
     Здесь применим так называемый *"жадный алгоритм"*, который может реализован
  для этой задачи 2 способами:
 
   * 5.3.1. _метод Краскала_ *
 
     _Идея метода:_ Сортируются ребра по неубывания весов, а потом из них  по 
  порядку  выбераются те ребра, которые соединяют различные еще компоненты 
  связности.
     _Сложность  :_ _<время сортировки - в общем случае O( VlogV )>_ + O(V*N)
  Сложность можно уменьшить,  если  модифицировать  процедуру   объединения 
  компонент.
     _Реализация :_ Пусть Mark[i] (1<=i<=N) - номер  компоненты связности, к
  которой принадлежит вершина i, P[1..3,1..М] - массив ребер ( p[3,j] - вес
  ребра j, соединяющего вершины p[1,j] и p[2,j]).
 
     Тогда примерная схема алгоритма:
 
    { Объединить компоненты a и b }
    Procedure UniteComponents(a, b : integer);
    { за сложность O(n) - в простой реализации }
    Var i : integer;
    Begin
      If a > b Then Begin
        i := a; a := b; b := i;
      End;
      For i := 1 To N Do
        If Mark[i] = b Then
          Mark[i] := a;
    End;
   Procedure Craskal;
   Begin
     < Сортируются ребра >
       { произвольным методом - подробнее см. *[12]* или FAQ по сортировкам }
     { В начале каждая вершина - отдельная компонента связности }
     For v := 1 To N Do
       Mark[v] := v;
     For j := 1 To M Do  { цикл по ребрам }
       If Mark[ p[1,j] ] <> Mark[ p[2,j] ] Then Begin
         { если ребро соединяет вершины из разных компонент }
 
         < добавить ребро в каркас >
         UniteComponents(Mark[ p[1,j] ], Mark[ p[2,j] ]);
                                 { Объединить эти компоненты }
       End;
   End;
 
   * 5.3.2. _метод Прима_ *
 
     _Идея метода:_начинаем формировать остов с произвольной вершины.Первым в 
  каркас включается ребро мин. веса,выходящее из этой вершины. Hа каждом шаге 
  к  каркасу  добавляется  ребро мин. веса  среди ребер, соединяющих вершины 
  каркаса с вершинами, еще не вошедшими в остов. 
     _Сложность  :_ Простая реализация - O(N^3). Знаю способ за O(N^2).
     _Реализация :_ самое сложное - на каждом шаге  быстро выбирать требуемое 
  ребро.  Самый простой способ  -  перебор всех ребер, смежных уже включенным 
  вершинам - O(n^2), что дает, умножая на кол-во шагов, O(n^3). Чтобы добится 
  того же за сложность O(n), нужно завести два массива: d[i] - мин. вес ребра 
  до  вершины  i  от  каркаса,  res[i]  -  номер вершины (которая принадлежит 
  каркасу), смежной этому ребру.  Потом надо обновлять эти массивы при каждом 
  добавлении новой вершины в каркас.
     Procedure Calc(i : integer);
     Var j : integer;
     Begin
       For j := 1 To n Do 
         If Not Mark[j] Then
           If D[j] > A[i,j] Then Begin
             D[j] := D[i,j];
             Res[j] := i;
           End;
     End;
     Procedure Prim;
     var i, j , 
         imin : integer;
         min  : TVes;
     Begin
       For i := 1 To n Do 
         D[i] := MaxVes;
       Mark[1] := True;
       Calc(1);
       For j := 1 To n-1 Do Begin { каркас состоит из n-1 ребер }
         min := MaxVes;
         For i := 1 To n Do
           If Not Mark[i] Then
             If min > D[i] Then Begin
               Min := D[i]; imin := i;
             End;
         Mark[imin] := True;
         Calc(imin);
         < добавить ребро (imin, Res[imin]) в каркас >
       End;
     End;
 
 * 6. Связность. Достижимость *
 
     _Путь в орграфе_  -  последовательность дуг, в которой конечная вершина 
  всякой дуги, кроме последней, является начальной вершиной следующей дуги.
     _Простой путь_ - путь, в котором каждая дуг используется не более раза.
     _Элементарный путь_ -путь,в котором каждая вершина используется не более 
  раза.  
 
 [...]
 // Матрицы достижимости, контрдостижимости - планируется в будующей версии //
 [...]
 
     Граф называется _транзитивным_, если из существования дуг (v, u) и (u, t)
  следует существование дуги (v, t).
     _Транзитивным замыканием_ графа G=(V, E) является граф Gz(V, E U E'),где
  E' - мин. кол-во дуг необходимых для того, чтобы граф Gz - стал транзитивным.
 
   * 6.1. Связность. *
 
 Q:> Что такое связный граф?
 A:> 
 
     1 случай)
     Hеориентированный граф G называется _связным_, если существует хотя бы
  один путь между каждой парой вершин.
     Определить связен ли неориентированный граф просто: запускаем поиск в 
  глубину или ширину от любой вершины - если все вершины станут помеченными,
  значит граф связен.
     Или, используя алгоритм Дейкстры,находим расстояние от любой вершины до 
  всех остальных - оно у связного графа должно быть конечно.
     2 случай)
     Ориентированный граф _связен_, если неориентированный граф, получающийся 
  из него заменой всех дуг на ребра является связным.
     Как сделать замену - если граф не взвешенный, то просто 
       A(G) [i,j] = max ( A(oG) [i,j], A(oG)[j,i] ). 
     Если граф взвешенный, нужно делать семантическое допущение - например,
  что в соответствующем неориентированном графе ребра будут иметь наименьший 
  или наибольший (отдельно  обрабатывать  случай  *+oo* ) вес из двух  дуг, 
  соединяющих одни и те же вершины в разных направлениях.
     3 случай)
     Орграф - _сильно связен_, если для каждой пары вершин i и j существует
  хотя бы один путь i->j и хотя бы один j->i.
     Максимальный связный подграф графа *oG* называется _связной компонентой_
  графа oG.
     Максимально сильно связный подграф графа  *oG*  называется _сильно связной_
  _компонентой_ или просто _сильной компонентой_.
     Для определения сильной связности можно использовать алгоритм Флойда.      
 [...]
 // Конденсация, база графа, двусвязность, компоненты двусвязности и их //
 //  поиск - планируется  в будующей версии                             //
 [...]
 
 * 7. Циклы. *
 
   * 7.1. Эйлеровы циклы. *
                                   "Откуда есть пошла Земля Русская..." (с)
 
     Дело в том, что основателем теории графов называют русского математика
  Л. Эйлера, доказавшего неразрешимость задачи "о кенингсберских мостах".
  Эта задача, собственно, сводилась к нахождению эйлерова цикла в заданном
  графе. 
 
     Путь v[0],...,v[n] называют _замкнутым_, если v[0]=v[n].
     Замкнутый путь называют _циклом_, если v[i]<>v[j] (1<=i,j<=n-1, i<>j).
     _Эйлеровым_ называют цикл, содержащий _все_ ребра _ровно один раз_.
     _Эйлеровым_ называют путь, содержащий _все_ ребра _ровно один раз_.
     Количество ребер, инцидентных вершине, называют степенью этой вершины.
 
     * Теорема *.Связный неориентированный граф содержит эйлеров цикл тогда и 
  и только тогда, когда число вершин нечетной степени равно нулю.
 
 Q:> А если дан ориентированный граф? Или эйлеров путь?
 A:> Связный неориентированный граф содержит эйлеров путь тогда и 
 
  только тогда, когда число вершин нечетной степени 0 или 2. Можно расширить
  теорему и на орграфы. Тогда  необходимо считать разность "выходящих" и 
  "входящих" дуг для каждой вершины.Чтобы существовал эйлеров цикл в орграфе,
  нужно разность у всех вершин равна 0, а чтобы существовал путь нужно,чтобы
  у  одной  вершины разность  равна 1 (начало пути), у другой -1 (конец), у 
  остальных 0(промежуточные вершины) или предыдущее условие - т. е. мы цикл
  можем разорвать в любой "точке".
 
     _Алгоритм(рекурсивный)._ Берем начальную вершину (исходя из условий - см. 
  выше) и рекурсивно  спускаемся "до упора" - до тех пор, пока не будет дуг, 
  выходящих  из текущей вершины (дуги,  по  которым  прошли - естественно, 
  "удаляем" - помечаем или т.п). В этом случае, возвращаемся  "наверх"  по 
  рекурсии.
     _Реализация:_
         Procedure Search(v : integer);
         var j : integer;
         begin
           for j := 1 to n do 
             if a[v, j] <>0 then begin
               a[v, j] := 0;     
               a[j, v] := 0;     
               Search ( j );     
             end;
           _< Добавить вершину v последней в текущий "путь" - массив >_
         end;     
 
   * 7.2. Гамильтоновы циклы. *
 
     Граф называется _гамильтоновым_, если в нем есть цикл, содержащий каждую 
  вершину этого графа.
     Этот цикл также называется _гамильтоновым_.
     Hе все связные графы - гамильтоновы.
 
     Известная NP-трудная задача "коммивояжера" в терминах теории графов 
  звучит  так: _"Hайти гамильтонов цикл минимального суммарного веса"._
 
 [...]
 // Фундаментальное множество циклов - планируется  в будующей версии //
 [...]
 --- WP/95 Rel 1.78E (215.0) Reg.
  * Origin: Windows(r) MS - "Выхода нет" (c) Сплин (2:5015/185.5)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор