ru.algorithms

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

 |   Данный текст представляет очередную версию FAQ по алгоритмам на графах. |
 |Все замечания, доработки и т. д. только приветствуются.  Все предложения по|
 |доработке FAQ  (исправления неточностей, ошибок, свои варианты алгоритмов и|
 |реализации на других языках) отправляйте автору по указанным адресам.      |
 |   Этот  текст  распространяется  в  электронной  форме с ведома и согласия|
 |автора  на  некоммерческой  основе  при  условии  сохранения  целостности и|
 |неизменности текста, включая сохранение настоящего уведомления.            |
 |   Любое коммерческое использование  настоящего текста,  а также публикации|
 |в  эхоконференциях  и  в  Internet  без ведома  и  прямого  согласия автора|
 |HЕ ДОПУСКАЕТСЯ.                                                            |
 |   (С) Дмитрий Волков, 2002 г.                                             |
 |         FidoNet: 2:5015/185.5 (предпочтительней)                          |
 |         e-mail : dnvolkov@mail.nnov.ru                                    |
 \---------------------------------------------------------------------------+
 
 [ Версия 1.0b - от 31.05.2002 ]
 
                 FAQ " Алгоритмы на графах. "
 
  * 0.Содержание *
 
  0. Содержание.
  1. Введение.
  2. Терминология.
  3. Способы задания и структуры для хранения информации о графе.
   3.1. Матрица смежности.
   3.2. Список ребер.
   3.3. Перечислители.
  4. Поиск в графе.       
   4.1. Поиск "в глубину".
   4.2. Поиск "в ширину".
  5. Каркас минимального веса. Методы Прима и Краскала.
   5.1. Поиск произвольного каркаса.
   5.2. Поиск всех различных каркасов.
   5.3. Поиск каркаса минимального веса.
    5.3.1. Метод Краскала.
    5.3.2. Метод Прима.
  6. Связность. Достижимость.
    6.1. Связность
  7. Циклы. 
    7.1. Эйлеровы циклы.
    7.2. Гамильтоновы циклы.
  8. Кратчайшие пути. 
    8.1. Постановка задачи. 
    8.2. Построение самого пути 
    8.3. Алгоритм Дейкстры (Дийкстры) 
     8.3.1. Доказательство верности алгоритма:
    8.4. Пути в бесконтурном графе 
    8.5. Кратчайшие пути между всеми парами вершин 
  9. Потоки в сетях.
    9.1. Задача. 
    9.2. Теорема Форда-Фалкерсона
    9.3. Решение. 
  10. Максимальное паросочетание.
    10.1. Определение
    10.2. Решение 1 (максимальный поток)
    10.3. Решение 2 (чередующая цепочка)
    10.4. Решение 3 (задача о "стабильных" браках)
  11. Используемая и рекомендуемая литература.
  12. От автора.
  13. Список планируемых тем.
  14. Благодарности.
 
  * 1. Введение. *
 
 Q:> Что такое "граф" и для чего он нужен?
 A:> Дело  в  том, что  часто   некоторую   задачу   можно   сформулировать 
 
  (формализовать) так: дано множество объектов, дано множество связей, которые
  соединяют пары вершин между собой, нужно сделать что-то. Тогда можно 
  сказать, что нам задан //граф// .
     Может оказаться, что заданная нам задача уже известна и решена эффективно
  (например, нужно построить максимальное паросочетание,  обойти граф и т.п.),
  известна, но ( //NP-трудная//, т.е., вероятно, не имеет эффективного решения) 
  или может быть разбита на такие подзадачи.
 
  * 2. Терминология. *
 
     _Граф_ - пара G=(V,E),   где V - множество _вершин_ (вершинами могут быть 
  объекты произвольной природы) и E - множество _ребер_, соединяющих их.
     Обозначим мощности множеств через N - для V, M - для E.  V, E - конечные 
  множества).  ( _Мощность_  конечного  множества   совпадает  с   количеством 
  элементов в нем).
 
     _Ребро_ - неупорядоченная пара вершин графа  (т.е.  если из одной вершины 
  можно "дойти" по этому ребру  до  какой-то другой, то  из этой второй можно 
  "дойти" в первую по этому же ребру.) - аналогия: "Двустороннее движение".
     _Дуга_ - упорядоченная пара вершин графа. ("Одностороннее движение").
 
  Hазовем: 
     Граф, содержащий только ребра - _неориентированным_,
                      только дуги  - _ориентированным(орграфом)_;
     Вершины, соединенные ребром   - _смежными_;
     Ребра, имеющие общую вершину  - также _смежными_;
     Ребро и любая из его вершин   - _инцидентными_;
     Ребро или дуга, которая соединяет одну и ту же вершину - _петлей_;
     
     Граф, дугам  или ребрам которого приписаны  некоторые параметры (веса) - 
  _взвешенным_.
     Граф, все вершины которого смежны всем остальным - _полным_.
 
  * 3. Способы задания и структуры для хранения информации о графе. *
 
 Q:> Какая разница, как задавать граф?
 A:> Сложность алгоритмов может существенно зависеть от структуры хранения 
 
  информации о графе. Предположим, узнать смежны ли вершины i и j с помощью 
  матрицы смежности потребует времени O(1), а с помощью списка ребер- O(M)...
 
 Q:> И как можно задавать граф?
 A:> Я пока знаю три основных способа:
 
  * 3.1. _Матрица смежности_ *
 
    _1. (для  задания  невзвешенного графа)._  Используется  _матрица связности_
  _(смежности)_ A размера N*N, при этом элемент 
         A[i, j] = { 1, если существует ребро из i-ой в j-ую вершины и 
                   { 0, если такого ребра нет. 
     Очевидно, матрица S - симметрична,  если граф неориентированный, и может 
  быть не симметричной в противном случае. 
 
    _2. ( для  задания  взвешенного  графа)._  Используется  _матрица  весов_  W
  размера N*N. При этом элемент 
         W[i, j] = { весу ребра, соединяющего i-ую и j-ую вершины. 
                   { бесконечности, если такого ребра нет.
     (на практике макс. возможное число на данном языке программирования).
     Далее будем считать, что веса имеют некоторый числовой тип TVes, а 
  константа MaxVes = бесконечности.
 
   * 3.2. _Список ребер._ *
 
     Тут, наверно, все понятно...  Заводим список - либо  просто массив, либо
  односвязный,  двусвязный список -  как вам удобно.  Каждый элемент содержит
  следующие параметры - [ _номер ребра в списке_ ],  инцидентные ему вершины,
  [ _вес ребра_ ] и т.п., где в скобку [ ] заключены необязательные элементы.
 
   * 3.3. _Перечислители_. *
 
     Для каждой вершины  i  определяем  список вершин,  смежных вершине i. Он 
  может задаваться как: 
        1) функция f(i, j), где j - номер возвращаемой вершине в списке
         [+] возможно будет занимать меньше памяти.
        2) собственно как список.
         [+] возможно будет работать быстрее (если ф-я сложная).
             Применяется также, если ф-я заранее не известна, но если N 
           достаточно мало, чтобы хранить N^2 элементов.
 
 * 4. Поиск в графе *
 
     Рассмотрим алгоритмы _обхода графа (поиска, просмотра)_.
 
 Q:> _Задача:_ необходимо "просмотреть" все вершины графа, в которые можно
 
  попасть из определенной вершины. 
 
 A:> Следующие алгоритмы также используются в  более  сложных  алгоритмах, 
 
  например, в волновом алгоритме (алгоритме Дейкстры).
     _Замечание:_ Предложенные методы обходят все вершины, содержащиеся в одной 
  компонете  связности с  начальной вершиной, поэтому если надо обойти ВСЕ  
  вершины графа, то нужно вызывать процедуры для каждой еще не просмотренной 
  вершниы:   
 
     For v := 1 To N Do     { цикл по всем вершинам v }
        If not Mark[v] Then { вершина v еще не просмотрена  }
           Proc(v); { вызвать процедуру обхода с начальной вершиной v }
 
   * 4.1 _Поиск "в глубину"_ *
 
     _Идея  метода:_ Просмотр начинается  с  некоторой  вершины v. Выбирается 
  вершина u, смежная с v, и процесс повторяется с ней.
     Если на очередном шаге мы работаем с вершиной q и нет вершин, смежных с 
  q и не просмотренных ранее, то возвращаемся в предыдущий шаг. Если попадаем 
  в первый шаг, то просмотр завершен.
     _Сложность  :_ O(n) (каждую вершину просмотрим максимум один раз.) * 
                    O(n) (сложность проверки смежности). Итого - O(n^2).
      Можно O(m) - если использовать перечислители. (быстрее работает, если 
  граф разреженный)
     _Реализация :_ рекурсивная процедура. Если стандартное ограничение на стек
  мало, можно попытаться увеличить его(с помощью директив компилятора). Если
  это  не  помогает,   то  нужно написать нерекурсивную  реализацию  метода, 
  работающую со стеком.
      Procedure D_f_s (v : integer);
      Var i : integer;
      Begin
        { ...Здесь должна быть обработка вершины v... }
        Mark[v] := True;
        For i := 1 To n Do 
          If (A[v, i]<>0)              { вершины смежны }
              And (Not Mark[i]) Then   { и в i еще не были }
            D_f_s(i);
      End; 
 
 Q:> Я сделал свою рекурсивную реализацию, но она все равно "вылетает", 
 
  хотя вершин мало.
 
 A:> Hе нужно передавать в процедуру большие по размеру параметры. Если 
 
  параметр занимает больше 2 байт, то лучше передать указатель  на  него 
  (ключевые слова *var* , *const* в Turbo Pascal)
   
   * 4.2. _Поиск "в ширину"_ *
    
     _Идея метода:_ Hеобходимо рассмотреть _все_ вершины, смежные с  текущей.
  Выбор следующей "текущей" - выбирается та, что была раньше "рассмотрена".
     _Сложность  :_ тоже O(n)
     _Реализация :_ работать с "очередью": берем вершину из начала очереди и
  добавляем в очередь все непросмотренные смежные с ней вершины.
     Procedure B_f_s(v : integer);
     Var i : integer;
     Begin
       < Добавить в очередь вершину v >
       While < очередь не исчерпана > Do Begin
         { ...Здесь должна быть обработка вершины v... }
         < Взять из очереди очередную вершину k > 
         For i := 1 To n Do 
           If (A[k, i]<>0) And (Not Mark[i]) Then Begin    
             Mark[i] := True;
             < Добавить в очередь вершину i >
           End;
       End;
     End; 
 
 --- WP/95 Rel 1.78E (215.0) Reg.
  * Origin: Программиcт без Кнута - не настоящий программист! (2:5015/185.5)
 
 

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