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
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.
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.
- class dane(object):
- def __init__(self, odwiedzony, kolor):
- self.odwiedzony = odwiedzony
- 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.
- def CzyDwudzielny(macierz, start):
- tab = []
- for i in range(0, len(macierz)):
- tab.append(dane(False, -1))
- tab[start].odwiedzony = True
- tab[start].kolor = 0
- q = queue.Queue()
- q.put(start)
- while (not q.empty()):
- u = q.get()
- kolorTeraz = tab[u].kolor
- for i in range(0, len(macierz)):
- if macierz[u][i] == 0:
- continue
- if (tab[i].odwiedzony and tab[i].kolor == kolorTeraz):
- return False
- elif not tab[i].odwiedzony:
- tab[i].odwiedzony = True
- tab[i].kolor = 1 - kolorTeraz
- q.put(i)
- 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:
- n = int(input("Podaj ile węzłów ma graf\n n = "))
- s = int(input("Podaj węzeł startowy\n s = "))
- print("Podaj elementy macierzy:")
- macierz = []
- for i in range(0, n):
- tab = [int(x) for x in input().split()]
- macierz.append(tab)
- wynik = CzyDwudzielny(macierz, s)
- print("Graf " + ("" if wynik else "nie ") + "jest dwudzielny")