Zastosowanie sieci przepływowych

Maksymalne skojarzenia w grafach dwudzielnych

Wymagane jest zapoznanie się z następującymi podrozdziałami:

    OL008 - Podstawowe informacje o grafach i sposobach ich reprezentacji w pamięci komputera.
    OL017 - Pojęcia podstawowe z teorii grafów
    OL022 - Grafy dwudzielne
    OL023 - Problem kojarzenia małżeństw
    OL028 - Sieci przepływowe - podstawowe definicje i własności
    OL029 - Maksymalny przepływ - algorytm Forda-Fulkersona


Sieci przepływowe służą zwykle do rozwiązywania problemów związanymi z przepływami - komunikacja, transport, ruch w sieciach teleinformatycznych itp. Jednakże po przyjęciu pewnych założeń można je stosować do rozwiązywania zadziwiająco dużej klasy problemów, które na pierwszy rzut oka nie mają wiele wspólnego z przepływami. Jednym z takich problemów jest znajdowanie maksymalnego skojarzenia w grafie dwudzielnym.

Przypomnijmy:

Skojarzeniem nazywamy znalezienie zbioru krawędzi grafu, które w grafie dwudzielnym łączą pary wierzchołków. Przy czym wierzchołki tworzące jedną parę nie mogą już należeć do innych par. Dwudzielność grafu gwarantuje, iż będą to zawsze wierzchołki należące do różnych klas.

Skojarzenie nazywamy maksymalnym, jeśli zawiera maksymalną, możliwą liczbę krawędzi. Powyżej przedstawiamy skojarzenie w grafie dwudzielnym (wierzchołki skojarzone są niebieskimi krawędziami), jednakże nie jest to skojarzenie maksymalne, chociaż w tym układzie nie można już dodać żadnej krawędzi. Skojarzenie maksymalne uzyskamy reorganizując nieco krawędzie niebieskie. Wynik mamy poniżej:

Algorytm znajdowania maksymalnych skojarzeń w grafach dwudzielnych opisaliśmy dokładnie przy okazji problemu kojarzenia małżeństw. Rozwiązanie wykorzystywało metodę BFS do znajdowania naprzemiennych ścieżek rozszerzających. Do tego samego wyniku możemy dojść stosując algorytm Forda-Fulkersona, który znajduje maksymalny przepływ w sieci. W tym celu musimy nieco zmodyfikować graf dwudzielny dodając węzeł źródła oraz węzeł ujścia:

Węzeł źródła s łączymy ze wszystkimi węzłami jednej klasy, a węzły należące do drugiej klasy łączymy z ujściem t. Przepustowość wszystkich krawędzi ustalamy na 1. W efekcie otrzymujemy powyższą sieć przepływową. Wyznaczamy w niej maksymalny przepływ przy pomocy algorytmu Forda-Fulkersona. Ponieważ do węzłów czerwonych (umowne oznaczenie węzłów w pierwszej klasie) dochodzą ze źródła krawędzie o przepustowości 1, to przepływ wypływający z tych węzłów nie może przekroczyć 1. Jeśli przepływ będzie miał wartość 1, to popłynie tylko jedną krawędzią grafu - tą, która kojarzy wierzchołek czerwony z zielonym. W efekcie wyznaczone przepływy w krawędziach grafu wskażą nam skojarzenia wierzchołków. Jeśli w danej krawędzi występuje przepływ o wartości 1, to krawędź ta kojarzy dwa wierzchołki w grafie dwudzielnym. Jeśli przepływ w krawędzi jest zerowy, to krawędź nie jest wykorzystywana do kojarzenia wierzchołków.

Dodatkową korzyścią jest wyznaczenie wierzchołków nieskojarzonych - wystarczy zbadać przepływ zerowy w krawędziach połączonych ze źródłem (wierzchołki nieskojarzone w klasie pierwszej) oraz w krawędziach połączonych z ujściem (wierzchołki nieskojarzone w klasie drugiej). Jeśli skojarzenie jest zupełne (wszystkie wierzchołki klasy pierwszej skojarzone z wierzchołkami klasy drugiej), to oczywiście we wszystkich tych krawędziach będzie przepływ o wartości 1.

Wartość wyznaczonego przez algorytm maksymalnego przepływu w sieci informuje nas o liczbie skojarzonych wierzchołków - pozwala od razu stwierdzić, czy w danym grafie możliwe jest skojarzenie zupełne.

Z rozważań tych wyłania się ogólny algorytm znajdowania maksymalnych skojarzeń w grafach dwudzielnych przy pomocy algorytmu wyznaczania maksymalnego przepływu w sieci przepływowej:

Krok 1: Pokoloruj wierzchołki grafu na czerwono i zielono tak, aby wierzchołki z tej samej klasy posiadały ten sam kolor.
Krok 2: Potraktuj graf jako graf skierowany - wszystkie krawędzie są skierowane od wierzchołka czerwonego do zielonego.
Krok 3: Na podstawie grafu zbuduj macierz przepustowości krawędzi C[n+2] x [n+2] ustawiając przepustowość krawędzi na 1 - macierz powinna zawierać dodatkowo dane dla źródła s i ujścia t. W wierszu C[s][ ] należy ustawić 1 w kolumnach odpowiadających wierzchołkom czerwonym, 0 dla pozostałych wierzchołków. W kolumnie C[ ][t] należy ustawić 1 dla wierszy odpowiadających wierzchołkom zielonym i 0 dla pozostałych wierzchołków.
Krok 4: Zastosuj algorytm Karpa-Edmondsa do wyznaczenia maksymalnego przepływu w sieci
Krok 5: Dla każdego czerwonego wierzchołka grafu wyprowadź tę krawędź, której przepływ jest równy 1
Krok 6: Koniec

 Aby wykorzystać ten algorytm do napisania programu, musimy rozwiązać kilka problemów:

Kolorowanie wierzchołków grafu

Kolorowanie wierzchołków grafu można wykonać wykorzystując metodę BFS - zrobiliśmy to w algorytmie badającym dwudzielność grafu. Jeśli mamy pewność, iż graf jest dwudzielny, to algorytm kolorowania można nieco uprościć:

Dane wejściowe

n - liczba wierzchołków w grafie
L[ ] - n elementowa tablica list sąsiedztwa. Każdy element tablicy jest listą wierzchołków.

Dane wyjściowe

color[ ] - n elementowa tablica zawierająca kolory wierzchołków, w przypadku grafu dwudzielnego:
 0 - kolor biały, wierzchołek nie odwiedzony
 1 - kolor czerwony
-1 - kolor zielony

Dane pomocnicze

q - kolejka służąca do składowania wierzchołków grafu
visited[ ] - tablica logiczna służąca do zaznaczania wierzchołków odwiedzonych

Lista kroków

K01: Wyzeruj tablice visited[ ], color[ ] i kolejkę q  
K02: Dla i = 1, 2, ..., n: wykonuj kroki K03...K13 wybieramy kolejne wierzchołki grafu
K03:     Jeśli visited[i] = true, kontynuuj następny obieg pętli K02 wierzchołki odwiedzone pomijamy
K04:     visited[i] ← true odwiedzamy wierzchołek
K05:     color[i] ← 1 kolorujemy go na czerwono
K06:     Dodaj i na koniec kolejki q zapamiętujemy wierzchołek w kolejce
K07:     Dopóki q zawiera wierzchołki, wykonuj kroki K08...K13 przechodzimy przez graf metodą BFS kolorując wierzchołki na przemian na czerwono i niebiesko
K08:         Pobierz wierzchołek v z początku kolejki  
K09:         Dla każdego wierzchołka w na liście L[v] wykonuj kroki K10...K13 przeglądamy wszystkie sąsiednie wierzchołki
K10:             Jeśli visited[w] = true, wykonaj następny obieg K09 pomijamy wierzchołki odwiedzone
K11:             visited[w] ← true odwiedzamy wierzchołek
K12:             color[w] ← - color[v] kolorujemy go na kolor przeciwny do koloru wierzchołka v
K13:             Umieść w na końcu kolejki q i dodajemy do kolejki
K14 Koniec  

Tworzenie grafu skierowanego

Ten problem można rozwiązać na etapie wprowadzania danych wymagając, aby krawędzie grafu dwudzielnego były zdefiniowane parami wierzchołków (czerwony, zielony) - takie podejście uwalnia nas również od algorytmu kolorowania. Jeśli tak się nie stało i mamy na wejściu graf nieskierowany, to po prostu usuwamy z niego wszystkie krawędzie wychodzące z wierzchołków zielonych, które znaleźliśmy w poprzednim kroku.

Dane wejściowe

n - liczba wierzchołków w grafie
L[ ] - n elementowa tablica list sąsiedztwa. Każdy element tablicy jest listą wierzchołków.
color[ ] - n elementowa tablica zawierająca kolory wierzchołków

Lista kroków

K01: Dla w = 1,2,...,n: wykonuj kroki  K02...K03 Przechodzimy przez kolejne wierzchołki w grafie
K02:     Jeśli color[w] = 1, następny obieg pętli K01 Wierzchołki czerwone pomijamy - zachowają krawędzie
K03:     Wyczyść listę L[w] W wierzchołkach zielonych usuwamy wszystkie krawędzie
K04: Zakończ  

Budowa macierzy przepustowości

Macierz przepustowości C[][] definiuje sieć przepływową. Musimy w niej uwzględnić węzeł źródła S oraz węzeł ujścia T. Dlatego wymiar macierzy jest o 2 większy od n, czyli liczby wierzchołków w grafie. Umawiamy się, iż źródło ma numer n+1, a ujście ma numer n+2. Wierzchołków tych wcale nie musimy dodawać do grafu - wystarczy, iż znajdą się w macierzy przepustowości.

Dane wejściowe

n - liczba wierzchołków w grafie
L[ ] - n elementowa tablica list sąsiedztwa. Każdy element tablicy jest listą wierzchołków.
color[ ] - n elementowa tablica zawierająca kolory wierzchołków

Dane wyjściowe

C[n+2][n+2] - macierz  przepustowości krawędzi sieci przepływowej

Lista kroków

K01: Utwórz i wyzeruj macierz C[n+2] x [n+2]  
K02: Dla w = 1,2,...,n: wykonuj K03...K04 Przechodzimy przez kolejne wierzchołki grafu
K03:     Dla każdego v z L[w] wykonuj
    C[w][v] ← 1
Dla każdej krawędzi w-v ustawiamy jej przepustowość na 1
K04:     Jeśli color[w] = 1, to C[n+1][w] ← 1
    inaczej C[w][n+2] ← 1
Źródło (n+1) łączymy z wierzchołkiem czerwonym,
wierzchołki zielone łączymy z ujściem (n+2)
K05: Zakończ  

Programy

Na podstawie przedstawionego algorytmu napiszemy program w C++ rozwiązujący problem wyznaczenia maksymalnego skojarzenia w grafie dwudzielnym. Program odczytuje ze standardowego wejścia definicję grafu dwudzielnego, która zbudowana jest następująco:

Dwie pierwsze liczby oznaczają kolejno liczbę wierzchołków n oraz liczbę krawędzi m.
Teraz następuje m definicji krawędzi - każda krawędź określona jest przez numery dwóch jej wierzchołków.

16 32
1 2 1 3 1 11 1 15
2 4 2 6 2 9
3 4 3 8 3 9
4 5 4 7 4 11 4 15
5 6 5 10
6 7 6 11 6 13
7 8 7 9 7 10 7 14 7 16
8 12
9 12 9 13
10 11
11 16
12 14
13 14
15 16
 

Dane specjalnie zostały podane w taki sposób, aby było konieczne kolorowanie wierzchołków - nie można liczyć na kolejność (czerwony - zielony) przy definicji krawędzi. Graf wczytamy również jako nieskierowany - krawędzie wychodzące z zielonych wierzchołków zostaną usunięte po kolorowaniu (gdy będzie już wiadomo, które wierzchołki są zielone!).

// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------
// Koło informatyczne 2006/7
//--------------------------
// P030 Maksymalne skojarzenia w grafie dwudzielnym
// Wersja z macierzami sąsiedztwa

#include <iostream>
#include <list>

using namespace std;

main()
{

// Wykonanie programu rozpoczynamy od odczytu definicji grafu.

// Odczytujemy liczbę wierzchołków n oraz liczbę krawędzi m

  int n, m;  cin >> n >> m;
  
// Tworzymy tablicę list sąsiedztwa oraz kolejkę wykorzystywaną przez BFS

  list<int> L[n+1], q;
  
// Odczytujemy m definicji krawędzi i umieszczamy wpisy w L[ ]

  for(int i = 0; i < m; i++)
  {
    int x, y;  cin >> x >> y;
    L[x].push_front(y); L[y].push_front(x);        
  }
  
// Przystępujemy do kolorowania wierzchołków grafu, czyli stworzymy
// tablicę color[], której elementy o indeksie i-tym odpowiadają kolorowi
// i-tego wierzchołka grafu. Do przeglądania grafu wykorzystujemy BFS.

  const int BIALY    =  0;
  const int CZERWONY =  1;
  const int ZIELONY  = -1;
  int  color[n+1];
  bool visited[n+1];
  
  for(int i = 1; i <= n; i++)
  {
    color[i] = BIALY; visited[i] = false;
  }
  q.clear();
  
  for(int i = 1; i <= n; i++)
    if(!visited[i])
    {
      visited[i] = true;
      color[i] = CZERWONY;
      q.push_back(i);
      while(q.size())
      {
        int v = q.front(); q.pop_front();
        for(list<int>::iterator w = L[v].begin(); w != L[v].end(); w++)
          if(!visited[*w])
          {
            visited[*w] = true;
            color[*w] = -color[v];
            q.push_back(*w);
          }
      }
    }

// Gdy mamy pokolorowane wierzchołki, usuwamy z grafu wszystkie krawędzie
// wychodzące z wierzchołków zielonych - w ten sposób otrzymamy graf
// skierowany

  for(int i = 1; i <= n; i++)
    if(color[i] == ZIELONY) L[i].clear();
    
// Na podstawie grafu budujemy macierz przepustowości dla sieci przepływowej.

  int C[n+3][n+3], F[n+3][n+3];
  
  for(int i = 1; i <= n+2; i++)
    for(int j = 1; j <= n+2; j++) F[i][j] = C[i][j] = 0;
  for(int w = 1; w <= n; w++)
  {
    for(list<int>::iterator v = L[w].begin(); v != L[w].end(); v++) C[w][*v] = 1;
    if(color[w] == CZERWONY)
      C[n+1][w] = 1;
    else
      C[w][n+2] = 1;
  }        

// Algorytmem Edmondsa-Karpa znajdujemy przepływy w poszczególnych krawędziach
// sieci przepływowej zdefiniowanej macierzą przepustowości. Dokładny opis tego
// fragmentu programu znajdziesz w poprzednim rozdziale

  int p[n+3], cfp[n+3], cp, s = n+1, t = n+2, x, y, esc;
  const int MAXINT = 2147483647;
  
  do
  {
    for(int i = 1; i <= n+2; i++) p[i] = 0;
    p[s] = -1;
    cfp[s] = MAXINT;
    q.clear(); q.push_back(s);
    esc = 0;
    while(q.size())
    {
      x = q.front(); q.pop_front();
      for(y = 1; y <= n+2; y++)
      {
        cp = C[x][y] - F[x][y];
        if(cp && !p[y])
        {
          p[y] = x;
          cfp[y] = cfp[x] > cp ? cp : cfp[x];
          if(y == t)
          {
             while(y != s)
             {
               x = p[y];
               F[x][y] += cfp[t];
               F[y][x] -= cfp[t];
               y = x;        
             }             
             esc = 1; break;
          }
          q.push_back(y); 
        }
      }
      if(esc) break;              
    }
    if(!esc) break;
  } while(true);

// Zadanie wykonane. Teraz przeglądamy graf i dla każdego czerwonego
// wierzchołka wyprowadzamy krawędź, w której przepływ wynosi 1

  cout << endl;
  for(int i = 1; i <= n; i++)
    if(color[i] == CZERWONY)
    {
      for(list<int>::iterator w = L[i].begin(); w != L[i].end(); w++)
        if(F[i][*w] == 1)
        {
          cout << i << " -> " << (*w) << endl;
          break;
        }
    }
  cout << endl;
  system("pause");
}
16 32
1 2 1 3 1 11 1 15
2 4 2 6 2 9
3 4 3 8 3 9
4 5 4 7 4 11 4 15
5 6 5 10
6 7 6 11 6 13
7 8 7 9 7 10 7 14 7 16
8 12
9 12 9 13
10 11
11 16
12 14
13 14
15 16

1 -> 2
4 -> 3
6 -> 5
8 -> 7
9 -> 12
10 -> 11
14 -> 13
16 -> 15

Następny program wykorzystuje drugą wersję algorytmu Edmondsa-Karpa - z listami sąsiedztwa. Zaletą tego rozwiązania jest mniejsze zapotrzebowanie na pamięć, gdyż przepustowości i przepływy trzymamy bezpośrednio w strukturze grafu.

// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------
// Koło informatyczne 2006/7
//--------------------------
// P030 Maksymalne skojarzenia w grafie dwudzielnym
// Wersja z tablicą list sąsiedztwa

#include <iostream>
#include <list>

using namespace std;

// Definiujemy strukturę wierzchołka umieszczanego na liście sąsiedztwa

struct TNode
{
  int v, c, f;
};

main()
{

  // Wczytujemy definicję grafu ze standardowego wejścia

  int n, m; cin >> n >> m;

  list<TNode> L[n+3];

  for(int i = 0; i < m; i++)
  {
    TNode x, y;
    cin >> x.v >> y.v;
    x.c = x.f = y.c = y.f = 0;
    L[x.v].push_front(y); L[y.v].push_front(x);
  }
  
  // Kolorujemy wierzchołki na czerwone i zielone
 
  const int BIALY    =  0;
  const int CZERWONY =  1;
  const int ZIELONY  = -1;
  int  color[n+1];
  bool visited[n+1];
  list<int> q;
  
  for(int i = 1; i <= n; i++)
  {
    color[i] = BIALY; visited[i] = false;
  }
  q.clear();
  
  for(int i = 1; i <= n; i++)
    if(!visited[i])
    {
      visited[i] = true;
      color[i] = CZERWONY;
      q.push_back(i);
      while(q.size())
      {
        int v = q.front(); q.pop_front();
        for(list<TNode>::iterator w = L[v].begin(); w != L[v].end(); w++)
          if(!visited[w->v])
          {
            visited[w->v] = true;
            color[w->v] = -color[v];
            q.push_back(w->v);
          }
      }
    }
 
  // Tworzymy sieć przepływową. Przepustowości krawędzi o początkowym
  // wierzchołku czerwonym ustawiamy na 1 (przeciwne są ustawione na 0)
  // Wierzchołki czerwone dodajemy na listę sąsiedztwa wierzchołka s.
  // Na listy sąsiedztwa wierzchołków zielonych dodajemy wierzchołek t

  int s = n+1, t = n+2;
  TNode tn = {t,1,0};
  
  for(int i = 1; i <= n; i++)
    if(color[i] == CZERWONY)
    {
      for(list<TNode>::iterator x = L[i].begin(); x != L[i].end(); x++) x->c = 1;
      TNode w = {i,1,0};
      L[s].push_front(w);
    }
    else
      L[i].push_front(tn);  
  
  // Wykonujemy algorytm Edmondsa-Karpa, który wyznaczy przepływy w
  // poszczególnych krawędziach grafu. Ten fragment programu jest
  // szczegółowo opisany w poprzednim rozdziale.
  
  int p[n+3], cfp[n+3];
  const int MAXINT = 2147483647;
  
  do
  {
    for(int i = 1; i <= n+2; i++) p[i] = 0;
    p[s]   = -1;
    cfp[s] = MAXINT;  
    q.clear();
    q.push_back(s);

    bool esc = false;
  
    while(q.size())
    {
      int u = q.front(); q.pop_front();
      for(list<TNode>::iterator x = L[u].begin(); x != L[u].end(); x++)
      {
        int cp = x->c - x->f;
        if(cp && !p[x->v])
        {
          p[x->v] = u;
          cfp[x->v] = (cp < cfp[u]) ? cp : cfp[u];
          if(x->v == t)
          {
            int v = t;

            while(v != s)
            {
              int u = p[v];
              for(list<TNode>::iterator i = L[u].begin(); i != L[u].end(); i++)
                if(i->v == v)
                {
                  i->f += cfp[t]; break;
                }      
              for(list<TNode>::iterator i = L[v].begin(); i != L[v].end(); i++)
                if(i->v == u)
                {
                  i->f -= cfp[t]; break;
                }
              v = u;      
            }            
            esc = true; break;        
          }
          q.push_back(x->v);
        }
      }
      if(esc) break;
    }
    if(!esc) break;
  } while(true);

  // Gotowe. Teraz wyprowadzamy krawędzie, w których przepływ wynosi 1
  
  cout << endl;
  
  for(int i = 1; i <= n; i++)
   if(color[i] == CZERWONY)
      for(list<TNode>::iterator x = L[i].begin(); x != L[i].end(); x++)
        if(x->f == 1)
        {
          cout << i << " -> " << x->v << endl;
          break;
        }
  cout << endl;
  system("pause");
}
16 32
1 2 1 3 1 11 1 15
2 4 2 6 2 9
3 4 3 8 3 9
4 5 4 7 4 11 4 15
5 6 5 10
6 7 6 11 6 13
7 8 7 9 7 10 7 14 7 16
8 12
9 12 9 13
10 11
11 16
12 14
13 14
15 16

1 -> 2
4 -> 3
6 -> 5
8 -> 7
9 -> 12
10 -> 11
14 -> 13
16 -> 15



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.