Strona główna » Algorytmy » Artykuły » Grafy Dwudzielne
 

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.

C++C#
Python
  1. class dane(object):
  2.   def __init__(self, odwiedzony, kolor):
  3.     self.odwiedzony = odwiedzony
  4.     self.kolor = kolor

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.

C++C#
Python
  1. def CzyDwudzielny(macierz, start):
  2.   tab = []
  3.   for i in range(0, len(macierz)):
  4.     tab.append(dane(False, -1))
  5.   tab[start].odwiedzony = True
  6.   tab[start].kolor = 0
  7.   q = queue.Queue()
  8.   q.put(start)
  9.   while (not q.empty()):
  10.     u = q.get()
  11.     kolorTeraz = tab[u].kolor
  12.     for i in range(0, len(macierz)):
  13.       if macierz[u][i] == 0:
  14.         continue
  15.       if (tab[i].odwiedzony and tab[i].kolor == kolorTeraz):
  16.         return False
  17.       elif not tab[i].odwiedzony:
  18.         tab[i].odwiedzony = True
  19.         tab[i].kolor = 1 - kolorTeraz
  20.         q.put(i)
  21.   return True

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:

C++C#
Python
  1. n = int(input("Podaj ile węzłów ma graf\n n = "))
  2. s = int(input("Podaj węzeł startowy\n s = "))
  3. print("Podaj elementy macierzy:")
  4. macierz = []
  5. for i in range(0, n):
  6.   tab = [int(x) for x in input().split()]
  7.   macierz.append(tab)
  8. wynik = CzyDwudzielny(macierz, s)
  9. print("Graf " + ("" if wynik else "nie ") + "jest dwudzielny")
Zadania
Zadanie 1
Kod źródłowy Zadanie 1Kod źródłowy Zadanie 1Kod źródłowy Zadanie 1