Grafy Dwudzielne

Definicja

Graf dwudzielny to taki graf, którego wierzchołki można rozbić na dokładnie dwa pozbiory, a wszystkie krawędzi łączą zawsze wierzchołki z dwóch różnych zbiorów. Inna nazwa takiego grafu to bigraf.

Twierdzenie

Graf jest dwudzielny wtedy i tylko wtedy, gdy wszystkie jego cykle są parzyste.

Przykład

Poniżej zostały przedstawione dwa przykłady z których pierwszy jest grafem dwudzielnym, a drugi nie

Graf dwudzielny

Opis grafu dwudzielnego

W powyższym przykładzie istnieje tylko jeden cykl utworzony przez wierzchołki A, B, D, E. Wierzchołki można pogrupować zgodnie z opisem w dwa zbiory: {A, D, C} oraz {E, B}. Każda krawędź grafu łączy wierzchołki pomiędzy dwoma zbiorami, ale nie pomiędzy wierzchołkami tej samej grupy.

Graf niedwudzielny

Opis grafu niedwudzielnego

W tym przykładzie została dodana krawędź łącząca wierzchołek C i D. Ma to ogromne znaczenie dla dwudzielności, ponieważ powstał cykl o nieparzystej długości trzy tworzony przez wierzchołki B, C, D. Teraz nie jest możliwe utworzenie dwóch grup. Dodana krawędź została zaznaczona na schemacie opisu czerwoną linią. Jak widać łąćzy ona dwa wierchołki z tego samego zbioru co jest niedopuszczalne.

Analiza Problemu

Najprostszym sposobem na sprawdzenie czy graf jest dwudzielny polega na pokolorowaniu go dwoma kolorami w taki sposób, żeby żadne dwa sąsiadujące wierzchołki (tj. połączone krawędzią) nie miały tego samego koloru. Kolorowanie można rozpocząć od dowolnego wierzchołka. Jego sąsiadów kolorujemy na kolor inny niż użyty dla początkowego wierzchołka. Kroki te powtarzamy dla każdego kolejnego wierzchołka. Jeśli okaże się, że podczas kolorowania, któryś z sąsiadów ma ten sam kolor to nie jest to graf dwudzielny. Należy pamiętać, że kolorowane są jedynie wierzchołki, które nie zostały dotychczas odwiedzone.

Implementacja

Do zaimplementowania wspomnianego algorytmu kolorowania w celu sprawdzenia dwudzielności można skorzystać z algorytmu BFS.

Struktura danych

Dla każdego wierzchołka trzeba przypisać dwie dodatkowe wartości. Jedna z nich przechowa informację czy wierzchołek został odwiedzony, a druga określone kolor wierzchołka. Początkowo przyjmujemy, że wszystkie wierzchołki prócz startowego mają nieokreślone kolor (-1) oraz są nieodwiedzone.

1. struct dane {
2.   bool odwiedzony;
3.   int kolor;
4. };

Algorytm

Poniższy algorytm wykonuje algorytm BFS do pokolorowania grafu. Do tego celu potrzebuje podania macierzy reprezentującej graf oraz, który wierzchołek przyjąć za startowy (domyślnie będzie to pierwszy wierzchołek jako, że wybór nie ma znaczenia). Uwaga: algorytm wymaga, aby graf był spójny.

1. bool CzyDwudzielny(int** macierz, int n, int start = 0) {
2.   dane* tab = new dane[n];
3.   for (int i = 0; i < n; i++) {
4.     tab[i].odwiedzony = false;
5.     tab[i].kolor = -1;
6.   }
7.   tab[start].odwiedzony = true;
8.   tab[start].kolor = 0;
9.   queue<int> q;
10.   q.push(start);
11.   while (q.size() != 0) {
12.     int u = q.front();
13.     q.pop();
14.     int kolorTeraz = tab[u].kolor;
15.     for (int i = 0; i < n; i++) {
16.       if (macierz[i][u] == 0) {
17.         continue;
18.       }
19.       if (tab[i].odwiedzony && tab[i].kolor == kolorTeraz) {
20.         return false;
21.       } else if (!tab[i].odwiedzony) {
22.         tab[i].odwiedzony = true;
23.         tab[i].kolor = 1 - kolorTeraz;
24.         q.push(i);
25.       }
26.     }
27.   }
28.   return true;
29. }

Podczas przeglądania wierzchołków i sprawdzania sąsiadów jeśli wykryjemy krawędź z tym samym kolorem po obu stronach to przerywamy algorytm. W przeciwnym razie nieodwiedzonych sąsiadów kolorujemy i dodajemy do kolejki przeglądania. Jeśli kolejka będzie pusta to kończymy funkcję zwracając prawdę.

Testowanie funkcji

W celu przetestowania napisanej funkcji można skorzystać z poniższego fragmentu programu:

1. int main() {
2.   int n, s;
3.   cout << "Podaj ile jest wierzcholkow w grafie\n n = ";
4.   cin >> n;
5.   cout << "Podaj wezel poczatkowy\n s = ";
6.   cin >> s;
7.   int** macierz = new int*[n];
8.   for (int i = 0; i < n; i++) {
9.     macierz[i] = new int[n];
10.     for (int j = 0; j < n; j++) {
11.       cin >> macierz[i][j];
12.     }
13.   }
14.   bool wynik = CzyDwudzielny(macierz, n, s);
15.   cout << "Graf " << (wynik ? "" : "nie ") << "jest dwudzielny";
16.   system("pause");
17.   return 0;
18. }

• Kod źródłowy Implementacja