Двудольный граф. Максимальное паросочетание в двудольном графе

Гинзбург Наталья Александровна

ДГ - граф, вершины которого можно разбить на 2 множества (2 доли), так что каждое ребро графа соединяет вершины из разных долей.

Как проверить, двудольный ли граф?
Начать красить в 2 цвета (обходом dfs), и если в какой-то момент две вершины одного цвета будут соединены ребром, то граф не двудольный!

Можно проверить и сразу разбить на две доли (покрасить вершины в два цвета). 

vector<int> g[MaxN];  // g[i] — вектор вершин, смежных с i-й
Используем dfs (depth-first-search), его писать быстрее.

$u_i$:

int dfs(int v, int color)
{
  int ret = 1;
  u[v] = color;
  // Перебираем соседей
  for(int i = 0; i < g[v].size(); i++)
  {
    int v2 = g[v][i];
    if (u[v2] == 0)
      ret &= dfs(v2, 3 - color);
    else if (u[v2] == color)
      return 0;
  }
  return ret;
}
...

//вызов:
ok = 1;
for (i = 0; i < n; i++)
  if (u[i] == 0)
    ok &= dfs (i, 1);

Паросочетание — множество ребёр графа, такое что каждая вершина графа инцидентна не более чем одному ребру этого множества.

Размер паросочетания — мощность множества ребёр этого паросочетания.

Максимальное паросочетание — паросочетание максимального размера.

Как построить максимальное паросочетание? Жадный алгоритм не работает.

Цепь в двудольном графе - простой путь.

Чередующаяся цепь относительно паросочетания $М$ - цепь, в которой чередуются рёбра из $M$ и из $не М$.

Дополняющая цепь - чередующаяся цепь относительно паросочетания $M$, в которой обе крайние вершины не покрыты паросочетанием $M$ (соответственно, оба крайних ребра цепи не принадлежат $M$).

Вдоль дополняющей цепи можно увеличить: выкинуть из паросочетания все ребра дополняющей цепи и добавить из нее же те ребра, которых в паросочетании не было (их больше на 1).

Теорема Бержа

Паросочетание $M$ максимально $<=>$ не сущ. дополняющих цепей относительно $M$.

$=>$ Если $\exists$ дополняющая цепь, то можно увеличить вдоль неё, значит, $M$ не максимальна.

$<=$ Пусть $М$ - паросоч. отн. которой не $\exists$ доп. цепей, $|M'|>|M|$.

$\angle$ $M \bigtriangleup M'$ - симметрическую разность $M$ и $M'$, т. е. множество ребер, которые лежат либо в M, либо в M'. Рассмотрим это множество как граф. Степень каждой вершины в паросочетании не больше 1, значит в $M \bigtriangleup M'$ степень каждой вершины не больше двух. Такой граф разбивается на простые пути и простые циклы, причем и там, и там чередуются ребра из $M$ и $M'$. Тогда каждый цикл содержит одинаковое количество ребер из $M$ и $M'$. Значит, существует путь, в котором больше ребер из $M'$, чем из $M$. Но такой путь - это и есть дополняющая цепь относительно $M$. Получаем противоречие.

Алгоритм Куна

Общий вид:

Поиск дополняющей цепи из вершины v1: 

// Первая доля, Вторая доля - рёбра только из одно доли в другую 
g[1..n1][1..n2] // Граф g[i][j]=1, если есть ребро из i в j
u[1..n1] // Пометки для каждого поиска в глубину (вершина посещена или еще нет) 
to[1..n2] // Храним паросочетание: для каждой вершины второй доли укажем, с какой вершиной из первой доли она связана


// Возвращает 1 если мы нашли дополняющую цепь и 0 - если не нашли
int match(int v1){  // v1 - вершина из первой доли
  int i;
  if(u[v1] == 1)
    return 0;
  u[v1] = 1; // Отмечаем, что в вершине v мы были  
  for(int i2 = 1; i2 <= n2; i2++) //i2 - вершина второй доли
    if (g[v1][i2] && (to[i2] == -1 || match(to[i2]))
    {
      to[i2] = v1;    
      return 1;
    }  
  return 0;    
}

Мы умеем искать из какой-то вершины дополняющую цепь.

Сколько раз надо запустить match? Понятно, что $n_1^2$ раз хватит: $n_1$ раз ищем вершину, с которой можно начать дополняющую цепь, каждый раз перебираем $n_1$ вершин.

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

int res = 0;
for(int i1=1; i1<=n1; i1++){
  memset(u, 0, sizeof(u));
  res += match(i1);
}
// res - размер паросочетания

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

Оценка сложности: $O(n_1*n_1*n_2)$ - поэтому в качестве первой доли лучше выбирать меньшую.

Как улучшить? Можно искать не в глубину, а в ширину. Можно использовать какую-нибудь эвристику для набора первоначального паросочетания, а потом улучшать его.

Примеры задач:

Классическая задача

Одна доля - мальчики. Другая доля девочки. Мальчики и девочки хотят сочетаться узами брака согласно графу их предпочтений (неориентированному, двудольному). Надо поженить как можно больше пар.

Шахматная доска

Дана шахматная доска $m$ на $n$ с некоторыми вырезанными клетками, надо расставить максимальное количество ладей, так чтобы они друг друга не били.

И еще несколько примеров в контесте.

Разбор задач на Pascal

Покраска в два цвета

Дан неориентированный граф из $n$ вершин и $m$ рёбер. Нужно покрасить вершины графа в два цвета таким образом, чтобы все рёбра соединяли вершины разных цветов, или выяснить, что это невозможно.

Входные данные:

В первой строке ввода заданы через пробел два целых числа: число вершин $n$ и число ребёр $m$ ($1 \le n \le 100$, $1 \le m \le 5000$).

Далее следует $m$ строк, каждая из которых содержит по два целых числа в диапазоне от $1$ до $n$ -номера вершин, которые соединяет ребро.

{$APPTYPE CONSOLE}
uses SysUtils;

const MaxN = 100;

var
  n: integer; { Количество вершин }
  g: array [1..MaxN, 1..MaxN] of boolean; { Матрица смежности }
  u: array [1..MaxN] of integer; { Цвет вершины }

{ Depth-First-Search для раскраски графа }
procedure dfs(v, color: integer); { v - вершина, color - цвет, в который её красим }
var i: integer;
begin
  u[v] := color; { Красим вершину v в цвет color }
  { Перебираем соседей вершины v }
  for i := 1 to n do
    if g[v, i] then { Если есть ребро из v в i }
      if u[i] = 0 then { и она ещё не покрашена, то идём в неё.. }
        dfs(i, 3 - color) { 3-2=1, 3-1=2 - меняем цвет }
      else
      begin
        if u[v] = u[i] then { Если соседями оказались вершины одного цвета.. }
        begin
          write(-1); { ..то требуемой покраски не существует, выводим -1.. } 
          halt; { ..и выходим из программы! }
        end;
      end;
end;

var i, x, y, m: integer;
begin
  reset(input, 'paint.in');
  rewrite(output, 'paint.out');

  { Чтение входных данных }
  FillChar(g, sizeof(g), false); { Очищаем матрицу смежности }
  readln(n, m); { Количество вершин, количество рёбер }
  for i := 1 to m do
  begin
    readln(x, y); { Считываем ребро и записываем его в матрицу смежности: }  
    g[x, y] := true; { ребро из x в y }
    g[y, x] := true; { обратное ребро из y в x }
  end;

  { Запускаем DFS для каждой компоненты связности }
  { Каждую компоненту связности мы раскрашиваем независимо от остальных. } 
  { Если компонента связности может быть раскрашена, то есть 2 способа её раскрасить, они
    отличаются заменой цветов. Поэтому цвет одной вершины можно фиксировать (выбрать любым)
    и остальные раскрасятся однозначно. В процессе обхода мы пробуем раскрасить всех соседей в другой цвет.
    Если какой-то сосед оказывается того же цвета, то мы нашли цикл нечётной длины и задачу решить невозможно.
   }
  FillChar(u, sizeof(u), 0); { Очищаем цвета, 0 - не покрашено }
  for i := 1 to n do
    if u[i] = 0 then { Вершина ещё не покрашена => это новая компонента связности... }
      dfs(i, 1); { ..красим её в 1-ый цвет и запускаем от неё DFS }

  { Если мы здесь, значит раскрасить удалось => выводим получившуюся раскраску }
  for i := 1 to n do
    write(u[i], ' ');
end.

Максимальное паросочетание

Граф $(V, \, E)$ называется двудольным, если множество его вершин $V$ можно разбить на два подмножества $A$ и $B$ такие, что любое ребро из $E$ соединяет вершину из $A$ с вершиной из $B$.

Паросочетанием $P$ называется любое подмножество $E$ такое, что никакие два ребра из него не имеют общей вершины.

Максимальное паросочетание - это паросочетание, число рёбер в котором максимально.

Найдите максимальное паросочетание в заданном двудольном графе.  

 

Ссылки: