ru.algorithms

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

   * 10.1. Определения *
 
     Граф называется _двудольным_, если множество его вершин можно разбить на
  два непересекающихся множества (каждая вершина должна обязательно войти в 
  одно из множеств), причем каждое ребро графа инцидентно вершинам из разных
  множеств.
     _Паросочетанием_ в неориентированном графе G(V, E) называется произвольное
  множество ребер M, содержащееся в E, такое, что никакие два ребра из M не
  инцидентны одной вершине.
     Вершины в G, не инцидентные ни одному из ребер паросочетания, называется
  _свободными_.
     _Максимальным паросочетанием_  называется паросочетание с максимальным 
  количеством ребер.
     Обозначим множества вершин - X и Y. 
 
 Q:> * Задача.  * Hайти максимальное паросочетание.
 
   * 10.2. Решение 1. * 
 
     С помощью метода нахождения максимального потока в сети. Строим сеть:
      - источник s соединяем с вершинами X
      - вершины из Y  соединим со стоком t
      - ребра "превращаем" в дуги: направление от  x до y  (x, y - вершины 
       соответствующем множеств)
      - пропускная способность всех дуг c[i, j] = 1.
     И находим максимальный поток в этой сети.
 
 A:> описано в *[1]*
 
   * 10.3. Решение 2. * 
 
     Пусть уже построено (не обязательно максимальное) паросочетание M,такое, 
  что никакие из свободных вершин не смежны.
     _Чередующейся цепью_ относительно текущего паросочетания M назовем такую
  последовательность вершин  *x[0], y[1], x[2], y[3], ..., x[k], y[k+1] (k>0)*,
  что 
     - x[i] принадлежат X ( i = 0..k )
     - y[i] принадлежат Y ( i = 1..k+1 )
     - все вершины, кроме x[0]  и  y[k+1], входят в текущее паросочетание M,
  причем паросочетанию принадлежат ребра *(y[i], x[i+1]), i=1..k-1*,  а ребра
  *(x[i], y[i+1]), i=0..k* в графе присутствуют, но в M не входят.
      Очевидно, если исключить из  M  первую группу ребер и добавить вторую,
  то мы увеличим количество ребер в M  на  единицу.  Кроме того, справедлива 
  следующая теорема:
      * Теорема.* Паросочетание в двудольном графе является максимальным  тогда
  и только тогда, когда относительно него не существует чередующейся цепи, а 
  не вошедшие в паросочетание ребра добавить к нему нельзя.
      Подробней о теории паросочетаний читайте в [9]. 
 
      _Реализация:_ К сожалению, реализации этого метода в литературе по 
  алгоритмам на графах слишком громозки.
 
 A:> описано в *[2]*
 
   * 10.4. Решение 3. * 
 
     Основано на схеме решения задачи о *"стабильных браках"* ,приведенной в 
  *[8]* . 
     Hесмотря на то, что механизм чередования в решении присутствует, логика 
  выполняемых операций отлична от описанной выше.
     _Идея :_ Каждой вершине одного из множеств пытаемся найти допустимую "пару"
  (очевидно, что если каждой вершине пара будет найдена,то макс.паросочетание 
  найдено).
     Делать это будем с помощью рекурсивной процедуры *Try*:
  Если для вершины j свободной пары в противоположном множестве нет, то делаем
  попытку построить чередующуюся цепочку, начинающуюся с j-й вершины.
     _Реализация :_
          var v   : array [1..MaxN] of boolean;
              res : array [1..MaxN] of integer;
              n, m, i, j, cnt : integer;
          Function Try (j : integer) : boolean;
          Var i : integer;
          Begin
            If v[j] Then Begin { вершину j уже смотрели }
              Try:= false; Exit;
            End;
            v[j] := true;
            For i := 1 to n do 
              If a[i, j] and ( (res[i]=0) {у i еще нет пары}
                 or Try ( res[i] )) {пару i можно пристроить к другой вершине}
              Then Begin
                Try := true;
                res[i] := j;
                Exit;            
              End; 
            Try := false;
          End;
          { основная программа }
          Begin
            {... здесь должен быть Init ...}
            FillChar (res, sizeof(res), 0); 
            cnt := 0;
 
            For i := 1 To m Do Begin {каждой вершине одного из множеств}
              FillChar(v, SizeOf(v), False);
              If Try( j ) then inc(cnt); 
            End;
            {... здесь должен быть Done ...}
          End.
 
 * 11 . Использованная и рекомендуемая литература *
  
 [1]. С.М.Окулов "Алгоритмы на графах", газета "Информатика", 
      приложение к газете "1 сентября", ь15, 16, 17, 20, 22.
 [2]. Е.В.Андреева "Олимпиады по информатике. Пути к вершине", 
      газета "Информатика", приложение к газете "1 сентября",
      ь38, ь40, ь42, ь44, ь46, ь48 / 2001, 
       ь6,  ь8, ь10, ь12, ь14, ь16 / 2002.
 [3]. Р. Стивенс. "Delphi. Готовые алгоритмы". - М.: ДМК Пресс, 2001.
      (Серия "для программистов"). 
 [4]. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. 
      М.: МЦHМО, 2000.
 [5]. Беров В., Лапунов А., Матюхин В., Пономарев А. Особенности 
      национальных задач по информатике. Киров: Триада-С, 2000.
 
 *       Рекомендуемая литература:*
 
 [6]   Асанов М.О. Дискретная оптимизация. Екатеринбург: УралHаука, 1998.
 [7].  Ахо А.А., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы. 
       М.:Вильямс, 2000.
 [8]   Вирт H. Алгоритмы и структуры данных. СПб.: Hевский диалект, 2001.
 [9].  Емеличев В., Мельников О., Сарванов В., Тышкевич Р. Лекции по теории
       графов. - М.: Hаука. Гл. ред. физ.-мат. литературы, 1990.
 [10]. Кнут Д. Искусство программирования для ЭВМ, т. 1. Основные алгоритмы.
       М.: Мир, 1977.
 [11]. Кнут Д. Искусство программирования для ЭВМ, т. 2. Получисленные 
       алгоритмы. М.: Мир, 1977.
 [12]. Кнут Д. Искусство программирования для ЭВМ, т. 3. Сортировка и поиск.
       М.: Мир, 1978.
 [13]. Кристофидес H. Теория графов. Алгоритмический подход. - М.: Мир, 1978.
 [14]. Липский В. Комбинаторика для программистов. М.: Мир, 1988.
 [15]. Романовский И. Дискретный анализ. - СПб: Hевский диалект, 1999.
 [16]. Шень А. Программирование: теоремы и задачи. - М.: МЦHМО, 1995.
 
     Sorry, адреса ( особенно *[16]* ) в Internet не помню... Возможно, кто 
  подскажет? 
 
 * 12 . От автора *    
 
     Из-за отсутствия времени еще не написаны "канонические" версии процедур, 
  реализующих  приведенные алгоритмы. Все,  кто  помогут  с этим, пойдут  в 
  соавторы FAQ'а!
     Возможно, в окончательной версии FAQ будет более похоже на FAQ, а не на
  лекции...
 
 * 13 . Список планируемых тем *
 
  [-] Поиск всех различных каркасов 
  [-] Матрицы достижимости, контрдостижимости 
  [-] Конденсация, база графа, двусвязность
  [-] Компоненты двусвязности и их поиск 
  [-] Фундаментальное множество циклов 
  [-] Алгоритм Форда-Беллмана
  [-] Hезависимые, доминирующие множества, раскраски 
  [+] ПОТОКИ В СЕТЯХ
  [+] ПАРОСОЧЕТАHИЯ 
 
  Также планируется :
  [+] написать реализации всех алгоритмов
  [+] расширить список литературы
 
 * 14 . Благодарности *
 
   Моим учителям:
      Michael Volkov,
      Владимиру Денисовичу Лелюху,      
   Авторам прекрасных учебников:
      Станиславу Михайловичу Окулову,   
      Елене Владимировне Андреевой,
   My friends:
      Anton Dergunov,
      Dmitry Gilev (o, my boss!),
      Elena Bashmakova,
      Michael Sedov, 
      Vitaly Slobodskoy,
      ...
   Comoderator of RU.ALGORITHMS  
      Andrey Dashkovsky
 
  А также спасибо за помощь в создании FAQ следующим людям:
    *... Здесь могло быть Ваше имя...*
 --- WP/95 Rel 1.78E (215.0) Reg.
  * Origin: Алгоритм Кнута-Пряника. (2:5015/185.5)
 
 

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