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 |
©2023 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. |
C++// 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 ©2023 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: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.