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

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

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe

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

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

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

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

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

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