Serwis Edukacyjny w I-LO w Tarnowie Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej Autor artykułu: mgr Jerzy Wałaszek |
©2024 mgr Jerzy Wałaszek |
ProblemNależy zbadać, czy dany graf nieskierowany i spójny jest grafem dwudzielnym. |
Graf dwudzielny (ang. bipartite graph lub bigraph) jest grafem, którego wierzchołki możemy podzielić na dwa rozłączne zbiory U i V. Wierzchołki należące do zbioru U mogą się łączyć krawędziami tylko z wierzchołkami ze zbioru V i na odwrót
Innymi słowy, każda krawędź grafu dwudzielnego łączy wierzchołki z różnych zbiorów.
Wierzchołki należące do zbioru U możemy traktować jako pokolorowane np. na niebiesko, a wierzchołki należące do zbioru V jako pokolorowane np. na czerwono. Graf będzie grafem dwudzielnym, jeśli uda nam się pokolorować wszystkie jego wierzchołki, tak aby żaden z sąsiadów danego wierzchołka nie był tego samego koloru co sam wierzchołek.
Do kolorowania grafu możemy wykorzystać algorytm przejścia wszerz BFS lub algorytm przejścia w głąb DFS. Zasada jest następująca:
Początkowo wszystkie wierzchołki grafu powinny posiadać kolor neutralny. Wybieramy dowolny wierzchołek w grafie i kolorujemy go np. na czerwono. Następnie przechodzimy algorytmem DFS lub BFS przez graf począwszy od wybranego wierzchołka kolorując po drodze wszystkich nie odwiedzonych sąsiadów na kolor przeciwny (czerwony → niebieski, niebieski → czerwony) do koloru odwiedzanego wierzchołka. Jeśli któryś z odwiedzonych wierzchołków sąsiadujących posiada taki sam kolor jak wierzchołek odwiedzany, to graf nie jest grafem dwudzielnym - dana krawędź łączy wierzchołki tej samej klasy.
Prześledźmy te operacje na przykładowym grafie:
Mamy przykładowy graf, dla którego chcemy sprawdzić dwudzielność (ang. bipartiteness). Początkowo wszystkie wierzchołki posiadają kolor neutralny – tutaj szary. | |
W grafie wybieramy dowolny wierzchołek (u nas
niech to dla prostoty będzie wierzchołek 0) i kolorujemy go
np. na czerwono. Wybrany wierzchołek posłuży jako punkt startowy dla przejścia BFS (lub alternatywnie DFS). |
|
Sprawdzamy, czy każdy sąsiad posiada inny kolor od wierzchołka startowego (jeśli nie, to graf nie jest dwudzielny i operację sprawdzania dwudzielności możemy natychmiast zakończyć z wynikiem negatywnym), a następnie kolorujemy go na kolor przeciwny do koloru wierzchołka startowego – tutaj na niebiesko. | |
Operację sprawdzania i kolorowania powtarzamy dla każdego sąsiada zgodnie z wybranym algorytmem przejścia grafu – tutaj BFS. | |
I dalej… | |
I dalej… | |
Koniec, graf jest dwudzielny. |
n | : | liczba wierzchołków w grafie, n ∈ C. |
graf | : | zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje. |
Q | : | kolejka. |
i, v, u | : | wierzchołki, i, v, u ∈ C. |
C | : | n elementowa tablica zawierająca kolory
wierzchołków, w przypadku grafu dwudzielnego: 0 - kolor szary, 1 - kolor czerwony, -1 - kolor niebieski. |
K01: | Utwórz n elementową tablicę C | |
K02: | Ustaw wszystkie elementy tablicy C na 0 | 0 oznacza kolor szary |
K03: | Utwórz pustą kolejkę Q | |
K04: | Dla i = 0, 1, …,
n - 1, wykonuj kroki K05…K15 |
przechodzimy przez kolejne wierzchołki grafu |
K05: | Jeśli C
[i] ≠ 0, to następny obieg pętli K04 |
szukamy wierzchołka szarego, który będzie wierzchołkiem startowym |
K06: | C [i ] ← 1 | wierzchołek startowy kolorujemy na czerwono |
K07: | Q.push (i) | numer wierzchołka umieszczamy w kolejce |
K08: | Dopóki Q.empty() = false, wykonuj kroki K09…K15 |
rozpoczynamy przejście BFS |
K09: | v ← Q.front() | pobieramy element z początku kolejki |
K10: | Q.pop() | pobrany element usuwamy z kolejki |
K11: | Dla każdego sąsiada
u wierzchołka v : wykonuj kroki K12…K15 |
przetwarzamy sąsiadów wierzchołka v |
K12: | Jeśli C [u] = C [v
], to zakończ z wynikiem false |
sąsiad ma ten sam kolor, więc graf nie może być dwudzielny |
K13: |
Jeśli C [u] ≠ 0, to następny obieg pętli K11 |
szukamy wierzchołka niepokolorowanego, czyli jeszcze nieodwiedzonego |
K14: | C [u] = -C [v] | kolorujemy sąsiada na kolor przeciwny |
K15: | Q.push (u) | sąsiada umieszczamy w kolejce |
K16: | Zakończ z wynikiem true |
Algorytm z przejściem DFS jest identyczny z powyższym. Jedyna zmiana polega na zastąpieniu kolejki Q stosem S.
Algorytm po niewielkiej przeróbce pozwala również wyznaczyć oba zbiory U i V. Odpowiednia informacja zawarta jest w tablicy color.
Z postaci przedstawionego powyżej algorytmu wynika, że najlepszym sposobem reprezentowania grafu jest tablica list sąsiedztwa.
Uwaga:
Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich. |
Program odczytuje definicję grafu nieskierowanego, tworzy tablicę list sąsiedztwa, a następnie sprawdza, czy graf jest dwudzielny. Jeśli tak, to wypisuje 'BIPARTITE GRAPH'. W przeciwnym razie wypisuje 'NOT A BIPARTITE GRAPH'. Za wierzchołek startowy przyjmowany jest wierzchołek nr 0. |
Dane przykładowe (przekopiuj do schowka i
wklej do okna konsoli):
Graf dwudzielny:
|
Graf niedwudzielny:
|
Pascal// Testowanie dwudzielności grafu // Data: 24.11.2013 // (C)2013 mgr Jerzy Wałaszek //--------------------------- program test_bigraph; // Typy dla dynamicznej tablicy list sąsiedztwa i kolejki type PslistEl = ^slistEl; slistEl = record next : PslistEl; v : integer; end; TList = array of PslistEl; // Definicja typu obiektowego queue //--------------------------------- queue = object private head : PslistEl; tail : PslistEl; public constructor init; destructor destroy; function empty : boolean; function front : integer; procedure push (v : integer); procedure pop; end; //--------------------- // Metody obiektu queue //--------------------- // Konstruktor - tworzy pustą listę //--------------------------------- constructor queue.init; begin head := nil; tail := nil; end; // Destruktor - usuwa listę z pamięci //----------------------------------- destructor queue.destroy; begin while not empty do pop; end; // Sprawdza, czy kolejka jest pusta //--------------------------------- function queue.empty : boolean; begin if head = nil then empty := true else empty := false; end; // Zwraca początek kolejki. // Wartość specjalna to -MAXINT //----------------------------- function queue.front : integer; begin if head = nil then front := -MAXINT else front := head^.v; end; // Zapisuje do kolejki //-------------------- procedure queue.push (v : integer); var p : PslistEl; begin new (p); p^.next := nil; p^.v := v; if tail = nil then head := p else tail^.next := p; tail := p; end; // Usuwa z kolejki //---------------- procedure queue.pop; var p : PslistEl; begin if head <> nil then begin p := head; head := head^.next; if head = nil then tail := nil; dispose (p); end; end; // Funkcja testuje dwudzielność grafu // n - liczba wierzchołków grafu // A - tablica list sąsiedztwa //----------------------------------- function isBipartite (n : integer; var A : TList) : boolean; var Q : queue; C : array of integer; v, u, i : integer; p : PslistEl; begin SetLength (C, n); // Tworzymy tablicę kolorów for i := 0 to n - 1 do C [i] := 0; Q.init; // Tworzymy pustą kolejkę for i := 0 to n - 1 do // Przechodzimy przez kolejne wierzchołki if C [i] = 0 then // Szukamy wierzchołka szarego begin C [i] := 1; // Wierzchołek startowy kolorujemy na czerwono Q.push (i); // i umieszczamy w kolejce while Q.empty = false do // Przejście BFS begin v := Q.front; // Pobieramy wierzchołek z kolejki Q.pop; // Pobrany wierzchołek usuwamy z kolejki p := A [v]; // Przeglądamy sąsiadów wierzchołka v while p <> nil do begin u := p^.v; // pobieramy z listy sąsiedztwa numer sąsiada if C [u] = C [v] then begin SetLength (C, 0); Q.destroy; Exit (false); // Sąsiad ma ten sam kolor end; if C [u] = 0 then // Jeśli wierzchołek nie jest odwiedzony, begin C [u] := -C [v]; // kolorujemy go na kolor przeciwny Q.push (u); // i umieszczamy w kolejce end; p := p^.next; // Następny sąsiad end; end; end; SetLength (C, 0); isBipartite := true; end; // ********************** // *** PROGRAM GŁÓWNY *** // ********************** var n, m, i, v1, v2 : integer; p, r : PslistEl; A : TList; begin read (n, m); // Czytamy liczbę wierzchołków i krawędzi SetLength (A, n); // Tworzymy tablicę list sąsiedztwa // Tablice wypełniamy pustymi listami for i := 0 to n - 1 do A [i] := nil; // Odczytujemy kolejne definicje krawędzi for i := 0 to m - 1 do begin read (v1, v2); // Wierzchołek startowy i końcowy krawędzi new (p); // Tworzymy nowy element p^.v := v2; // Numerujemy go jako v2 p^.next := A [v1]; // Dodajemy go na początek listy A [v1] A [v1] := p; new (p); // Krawędź w drugą stronę, bo graf jest nieskierowany p^.v := v1; p^.next := A [v2]; A [v2] := p; end; if isBipartite (n, A) then writeln('BIPARTITE GRAPH') else writeln('NOT A BIPARTITE GRAPH'); // Usuwamy tablicę list sąsiedztwa for i := 0 to n - 1 do begin p := A [i]; while p <> nil do begin r := p; p := p^.next; dispose (r); end; end; SetLength (A, 0); end. |
// Testowanie dwudzielności grafu // Data: 24.11.2013 // (C)2013 mgr Jerzy Wałaszek //--------------------------- #include <iostream> using namespace std; const int MAXINT = -2147483647; // Typy dla dynamicznej tablicy list sąsiedztwa i kolejki struct slistEl { slistEl * next; int v; }; // Definicja typu obiektowego queue //--------------------------------- class queue { private: slistEl * head; slistEl * tail; public: queue(); // konstruktor ~queue(); // destruktor bool empty (void); int front (void); void push (int v); void pop (void); }; //--------------------- // Metody obiektu queue //--------------------- // Konstruktor - tworzy pustą listę //--------------------------------- queue::queue() { head = tail = NULL; } // Destruktor - usuwa listę z pamięci //----------------------------------- queue::~queue() { while(head) pop(); } // Sprawdza, czy kolejka jest pusta //--------------------------------- bool queue::empty (void) { return !head; } // Zwraca początek kolejki. // Wartość specjalna to -MAXINT //----------------------------- int queue::front (void) { if(head) return head->v; else return -MAXINT; } // Zapisuje do kolejki //-------------------- void queue::push (int v) { slistEl * p = new slistEl; p->next = NULL; p->v = v; if(tail) tail->next = p; else head = p; tail = p; } // Usuwa z kolejki //---------------- void queue::pop (void) { if(head) { slistEl * p = head; head = head->next; if(!head) tail = NULL; delete p; } } // Funkcja testuje dwudzielność grafu // n - liczba wierzchołków grafu // A - tablica list sąsiedztwa //----------------------------------- bool isBipartite (int n, slistEl ** A) { queue Q; int * C; int v, u, i; slistEl * p; C = new int [n]; // Tworzymy tablicę kolorów for(i = 0; i < n; i++) C [i] = 0; for(i = 0; i < n; i++) // Przechodzimy przez kolejne wierzchołki if(!C [i]) // Szukamy wierzchołka szarego { C [i] = 1; // Wierzchołek startowy kolorujemy na czerwono Q.push (i); // i umieszczamy w kolejce while(!Q.empty()) // Przejście BFS { v = Q.front(); // Pobieramy wierzchołek z kolejki Q.pop(); // Pobrany wierzchołek usuwamy z kolejki for(p = A [v]; p; p = p->next) // Przeglądamy sąsiadów wierzchołka v { u = p->v; // pobieramy z listy sąsiedztwa numer sąsiada if(C [u] == C [v]) { delete [] C; return false; // Sąsiad ma ten sam kolor } if(!C [u]) // Jeśli wierzchołek nie jest odwiedzony, { C [u] = -C [v]; // kolorujemy go na kolor przeciwny Q.push (u); // i umieszczamy w kolejce } } } } delete [] C; return true; } // ********************** // *** PROGRAM GŁÓWNY *** // ********************** int main() { int n, m, i, v1, v2; slistEl * p, * r, ** A; cin >> n >> m; // Czytamy liczbę wierzchołków i krawędzi A = new slistEl * [n]; // Tworzymy tablicę list sąsiedztwa // Tablice wypełniamy pustymi listami for(i = 0; i < n; i++) A [i] = NULL; // Odczytujemy kolejne definicje krawędzi for(i = 0; i < m; i++) { cin >> v1 >> v2; // Wierzchołek startowy i końcowy krawędzi p = new slistEl; // Tworzymy nowy element p->v = v2; // Numerujemy go jako v2 p->next = A [v1]; // Dodajemy go na początek listy A [v1] A [v1] = p; p = new slistEl; // Krawędź w drugą stronę, bo graf jest nieskierowany p->v = v1; p->next = A [v2]; A [v2] = p; } if(isBipartite (n, A)) cout << "BIPARTITE GRAPH"; else cout << "NOT A BIPARTITE GRAPH"; cout << endl; // Usuwamy tablicę list sąsiedztwa for(i = 0; i < n; i++) { p = A [i]; while(p) { r = p; p = p->next; delete r; } } delete [] A; return 0;} |
Basic' Testowanie dwudzielności grafu ' Data: 24.11.2013 ' (C)2013 mgr Jerzy Wałaszek '--------------------------- Const MAXINT = 2147483647 ' Typy dla dynamicznej tablicy list sąsiedztwa i kolejki Type slistEl next As slistEl Ptr v As Integer End Type ' Definicja typu obiektowego queue '--------------------------------- Type queue Private: head As slistEl Ptr tail As slistEl Ptr Public: Declare Constructor() Declare Destructor() Declare Function empty() As Integer Declare Function front As Integer Declare Sub push (ByVal v As Integer) Declare Sub pop() End Type '--------------------- ' Metody obiektu queue '--------------------- ' Konstruktor - tworzy pustą listę '--------------------------------- Constructor queue() head = 0 tail = 0 End Constructor ' Destruktor - usuwa listę z pamięci '----------------------------------- Destructor queue() While empty = 0: pop: Wend End Destructor ' Sprawdza, czy kolejka jest pusta '--------------------------------- Function queue.empty() As Integer If head = 0 Then Return 1 Return 0 End Function ' Zwraca początek kolejki. ' Wartość specjalna to -MAXINT '----------------------------- Function queue.front() As Integer If head = 0 then front = -MAXINT Else front = head->v End If End Function ' Zapisuje do kolejki '-------------------- Sub queue.push (ByVal v As Integer) Dim p As slistEl Ptr p = new slistEl p->next = 0 p->v = v If tail = 0 Then head = p Else tail->next = p End If tail = p End Sub ' Usuwa z kolejki '---------------- Sub queue.pop() Dim p As slistEl Ptr If head Then p = head head = head->next If head = 0 Then tail = 0 Delete p End If End Sub ' Funkcja testuje dwudzielność grafu ' n - liczba wierzchołków grafu ' A - tablica list sąsiedztwa '----------------------------------- Function isBipartite (ByVal n As integer, ByVal A As slistEl Ptr Ptr) As Integer Dim As queue Q Dim As Integer Ptr C Dim As Integer v, u, i Dim As slistEl Ptr p C = New Integer [n] ' Tworzymy tablicę kolorów For i = 0 To n - 1 C [i] = 0 Next For i = 0 To n - 1 ' Przechodzimy przez kolejne wierzchołki If C [i] = 0 Then ' Szukamy wierzchołka szarego C [i] = 1 ' Wierzchołek startowy kolorujemy na czerwono Q.push (i) ' i umieszczamy w kolejce While Q.empty() = 0 ' Przejście BFS v = Q.front() ' Pobieramy wierzchołek z kolejki Q.pop() ' Pobrany wierzchołek usuwamy z kolejki p = A [v] While p ' Przeglądamy sąsiadów wierzchołka v u = p->v ' pobieramy z listy sąsiedztwa numer sąsiada If C [u] = C [v] Then Delete [] C Return 0 ' Sąsiad ma ten sam kolor End If If C [u] = 0 Then ' Jeśli wierzchołek nie jest odwiedzony, C [u] = -C [v] ' kolorujemy go na kolor przeciwny Q.push (u) ' i umieszczamy w kolejce End If p = p->Next ' Następny wierzchołek Wend Wend End If Next Delete [] C Return 1 End Function ' ********************** ' *** PROGRAM GŁÓWNY *** ' ********************** Dim As Integer n, m, i, v1, v2 Dim As slistEl Ptr p, r Dim As slistEl Ptr Ptr A Open Cons For Input As #1 Input #1, n, m ' Czytamy liczbę wierzchołków i krawędzi A = new slistEl Ptr [n] ' Tworzymy tablicę list sąsiedztwa ' Tablicę wypełniamy pustymi listami For i = 0 To n - 1 A [i] = 0 Next ' Odczytujemy kolejne definicje krawędzi For i = 0 To m -1 Input #1, v1, v2 ' Wierzchołek startowy i końcowy krawędzi p = new slistEl ' Tworzymy nowy element p->v = v2 ' Numerujemy go jako v2 p->next = A [v1] ' Dodajemy go na początek listy A [v1] A [v1] = p p = new slistEl ' Krawędź w drugą stronę, bo graf jest nieskierowany p->v = v1 p->next = A [v2] A [v2] = p Next Close #1 If isBipartite (n, A) Then Print "BIPARTITE GRAPH" Else Print "NOT A BIPARTITE GRAPH" EndIf ' Usuwamy tablicę list sąsiedztwa For i = 0 To n - 1 p = A [i] While p r = p p = p->Next Delete r Wend Next Delete [] A End |
Wynik: | ||
17 23 0 2 0 3 1 2 1 14 2 6 3 4 3 6 3 13 4 7 4 12 5 6 5 9 5 10 6 7 6 8 6 12 7 13 8 9 10 11 10 14 10 15 11 16 12 16 BIPARTITE GRAPH |
17 24 0 2 0 3 1 2 1 14 2 6 3 4 3 6 3 13 4 7 4 12 5 6 5 9 5 10 6 7 6 8 6 12 7 13 8 9 10 11 10 14 10 15 11 16 12 16 13 16 NOT A BIPARTITE GRAPH |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2024 mgr Jerzy Wałaszek |
Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.