Matematyka dyskretna 1/Wykład 15: Metody algebraiczne w teorii grafów

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Metody algebraiczne w teorii grafów

Graf regularny stopnia to graf, w którym wszystkie wierzchołki mają stopień .
Graf taki nazywany jest także -regularnym.

Maksymalny stopień wierzchołka w grafie , oznaczany przez to

Macierz sąsiedztwa grafu prostego to zero-jedynkowa macierz rozmiaru , gdzie



Uwaga

Macierz sąsiedztwa grafu nieskierowanego jest symetryczna.

Graf prosty i graf skierowany

Przykład

Na rysunku Graf prosty przedstawiono graf prosty o wierzchołkach oraz graf skierowany o wierzchołkach . Macierze sąsiędztwa grafów oraz wyglądają następująco:



Domknięcie przechodnie grafu skierowanego , to graf taki, że:

  • , oraz

wtedy i tylko wtedy, gdy w grafie istnieje skierowana marszruta z do .

Twierdzenie 15.1

Niech będzie grafem skierowanym. Wtedy liczba skierowanych marszrut z do jest dana elementem macierzy:



Dowód

Wystarczy pokazać, że

(*) jest macierzą, w której jest liczbą skierowanych marszrut z do o długości .

Dowód własności (*) przeprowadzimy indukcją względem . Macierz jest macierzą sąsiedztwa, co natychmiast daje (*) dla . Niech teraz . Oczywiście



Jeśli więc , , oraz , to



Wartość to liczba wszystkich skierowanych marszrut z do o długości . Tak więc iloczyn jest równy liczbie wszystkich skierowanych -elementowych marszrut mających postać , czyli takich skierowanych marszrut z do o elementach, których przedostatni wierzchołek to . Sumując te wartości po wszystkich , czyli dopuszczając dowolny wierzchołek jako przedostatni, otrzymujemy liczbę wszystkich -elementowych skierowanych marszrut z do . To kończy dowód (*), a zatem i całego twierdzenia.

End of proof.gif

Graf (a) oraz jego przechodnie domknięcie (b)

Przykład

Grafy i zostały przedstawione na animacji.

Macierz sąsiedztwa grafu to



Ponadto



W macierzy wartość mówi o liczbie różnych skierowanych marszrut z wierzchołka do o długości co najwyżej . Dla przykładu i rzeczywiście , , , i są wszystkimi skierowanymi marszrutami jakie można znaleźć w grafie prowadzące z wierzchołka do o długości co najwyżej . Z kolei macierz sąsiedztwa dla przechodniego domknięcia grafu to



Warto zaobserwować oczywisty fakt, że macierz można równie dobrze uzyskać z macierzy przez zamianę każdej niezerowej wartości na oraz wyzerowanie przekątnej.

Wniosek 15.2

Dla grafu o wierzchołkach i macierzy , jeśli tylko , to



Macierz incydencji grafu to zero-jedynkowa macierz rozmiaru , gdzie



Zorientowana macierz incydencji grafu prostego to macierz , rozmiaru , otrzymana z macierzy incydencji poprzez zastąpienie w każdej kolumnie jednej z dwu jedynek przez (minus jeden).

Graf prosty

Przykład

Dla grafu przedstawionego na rysunku Graf prosty G4 macierz incydencji oraz zorientowana macierz incydencji, to odpowiednio:



Obserwacja 15.3

  • Dla macierzy incydencji oraz zorientowanej macierzy incydencji zachodzi
  • W zorientowanej macierzy incydencji mamy:

Macierz stopni grafu prostego to diagonalna macierz rozmiaru , gdzie



Przykład

Dla grafu przedstawionego na rysunku Graf prosty G4 odpowiednia macierz stopni to



Twierdzenie 15.4

Jeśli jest grafem prostym, to



gdzie jest macierzą transponowaną macierzy .

Przykład

Policzmy macierze opisane w Twierdzeniu 15.4 dla grafu z rysunku Graf prosty G4. Tak więc



Dowód [Twierdzenia 15.4]

Niech będzie elementem w -tym wierszu oraz w -tej kolumnie macierzy . Z definicji wynika, że



Rozważmy dwa przypadki:

  • . Wtedy jest równoważne temu, że krawędź łączy wierzchołek z . Tak więc wtedy i tylko wtedy, gdy sąsiaduje z .
  • . Wtedy jest równoważne temu, że krawędź jest incydentna z . Sumując wartości dla uzyskujemy liczbę krawędzi incydentnych do , czyli stopień .
End of proof.gif

Twierdzenie 15.5

Niech będzie grafem skierowanym o wierzchołkach, a macierz o rozmiarach , będzie minorem (podmacierzą) zorientowanej macierzy incydencji , w którym kolumny odpowiadają krawędziom z pewnego podzbioru zbioru . Wtedy


jest drzewem wtedy i tylko wtedy, gdy jest nieosobliwa.


Przykładowe drzewo wraz z zaznaczoną ścieżką

Dowód

Niech będzie wierzchołkiem odpowiadającym jedynemu wierszowi pominiętemu w minorze .

Niech będzie drzewem. Dla pokazania, że wtedy macierz jest nieosobliwa, dokonamy takiej permutacji wierszy i kolumn macierzy , by uzyskana w ten sposób macierz była trójkątna i miała wyłącznie niezerowe elementy na przekątnej. Zostanie to uzyskane przez takie ponumerowanie wierzchołków i krawędzi grafu , by w nowej macierzy


wtedy i tylko wtedy, gdy wierzchołek jest incydentny z
.


Przypomnijmy, że odległość pomiędzy dwoma wierzchołkami i w grafie to liczność najkrótszej ścieżki od do . Ponumerujmy wierzchołki z w taki sposób, że jeśli jest bliżej wierzchołka , niż to . Numeracji takich może być wiele, ale dla nas nie ma znaczenia, którą z nich wybierzemy i ustalimy dla dalszej części dowodu. Zauważmy jedynie, że w każdej takiej numeracji wierzchołek znajduje się na początku. Ponieważ graf jest drzewem, to między wierzchołkiem i dowolnym istnieje dokładnie jedna ścieżka. Oznaczmy ją przez . Oczywiście, dla ostanie krawędzie w ścieżkach i są różne. Tę ostatnią krawędź ścieżki oznaczmy, tak jak na rysunku, indeksem , czyli .

Ponieważ w drzewie jest dokładnie krawędzi, przypisanie wierzchołkowi krawędzi jest bijekcją między a . W kolumnie macierzy , odpowiadającej krawędzi , są jedynie dwa niezerowe elementy - jeden leży w wierszu , odpowiadającemu wierzchołkowi , a drugi w wierszu . Skoro krawędź ma ten sam numer co wierzchołek , wierzchołek musi leżeć na ścieżce z do . Tym samym jest bliżej niż , a zatem . Macierz jest więc macierzą trójkątną górną z niezerową przekątną, co kończy dowód.

Załóżmy teraz, że nie jest drzewem. Ponieważ ma jedynie krawędzi, to zależność miedzy liczbą wierzchołków, krawędzi i składowych spójnych daje, że ma co najmniej składowe. Niech wierzchołki tworzą składową, w której nie występuje . Jeżeli, w -tym wierszu i -tej kolumnie macierzy jest niezerowy element , to wierzchołek jest incydentny z krawędzią . Wierzchołek będący drugim końcem krawędzi leży oczywiście w tej samej składowej co , a zatem macierz ma liczbę w -tej kolumnie i w -tym wierszu. Sumując teraz wiersze macierzy o indeksach otrzymujemy wektor zerowy. To oczywiście oznacza, że macierz jest osobliwa.

End of proof.gif

Wniosek 15.6

W spójnym grafie prostym o wierzchołkach rząd macierzy wynosi .

Wielomian charakterystyczny grafu to wielomian charakterystyczny macierzy sąsiedztwa .

Permanent grafu to permanent macierzy , czyli



gdzie suma rozciąga się po wszystkich permutacjach , zaś oznacza element macierzy .

Wyznacznik grafu to wyznacznik macierzy , czyli



Skojarzenie niedoskonałe (a) i doskonałe (b)

Algebraiczne pojęcie permanentu macierzy okazuje się użytecznym przy badaniu skojarzeń w grafie. Rozważaliśmy już skojarzenia w grafach dwudzielnych.

Skojarzenie w grafie to taki podzbiór , że żadne jego dwie krawędzie nie są incydentne z tym samym wierzchołkiem.

Skojarzenie doskonałe to skojarzenie wykorzystujące wszystkie wierzchołki grafu.

Twierdzenie 15.7

Prosty graf dwudzielny ma skojarzenie doskonałe wtedy i tylko wtedy, gdy ma niezerowy permanent.

Dowód

Niech . Dowód ma dwa etapy. Najpierw pokażemy, że:

1. Permanent grafu jest niezerowy wtedy i tylko wtedy, gdy istnieje permutacja liczb taka, że dla .

Istotnie, każdy składnik sumy dającej permanent grafu



jest zawsze nieujemny. A zatem cała suma będzie dodatnia wtedy i tylko wtedy, gdy choć jeden jej składnik będzie niezerowy. To z kolei jest równoważne temu, że dla choć jednej permutacji zachodzi



dla wszystkich .

2. Graf ma doskonałe skojarzenie wtedy i tylko wtedy, gdy istnieje permutacja liczb taka, że dla .

Istotnie, w skojarzeniu doskonałym każdy wierzchołek jest incydentny z dokładnie jedną krawędzią. A zatem skojarzenie wyznacza permutację poprzez



Nadto dla wszystkich .

Z drugiej strony, jeśli jest cyklem permutacji , tzn.



to założona równość mówi, że cyklowi temu odpowiada cykl w grafie . Oczywiście w grafie dwudzielnym cykl taki musi mieć parzystą liczbę wierzchołków, tak więc zbiór krawędzi



tworzy doskonałe skojarzenie zbioru wierzchołków . Po zsumowaniu skojarzeń odpowidającym wszystkim cyklom permutacji otrzymamy skojarzenie doskonałe w grafie .

End of proof.gif

Graf

Skojarzenie doskonałe w grafie

{{przyklad||| Rozważmy graf przedstawiony na rysunku Graf G5.

Macierz sąsiedztwa to



Permanent , tak więc istnieje skojarzenie doskonałe . Jedno z takich skojarzeń, przedstawione na rysunku Skojarzenie doskonałe w grafie G5, odpowiada wyróżnionym elementom macierzy:



Przy badaniu kolorowań grafów przydatne okazuje się inne pojęcie algebraiczne.

Wartość własna grafu to wartość własna macierzy sąsiedztwa .

Obserwacja 15.8

Macierz sąsiedztwa jest rzeczywista i symetryczna, zatem wszystkie jej wartości własne są rzeczywiste i istnieje baza ortogonalna złożona z jej wektorów własnych.

Dla grafu prostego przyjmujemy oznaczenia:

  • na maksymalną wartość własną macierzy ,
  • na minimalną wartość własną macierzy .

Obserwacja 15.9

Wartości własne grafu są, co do wartości bezwzględnej, nie większe niż maksymalny stopień wierzchołków grafu , tzn.



Dowód

Niech oraz będzie niezerowym wektorem własnym macierzy o wartości własnej . Bez straty ogólności można założyć, że . Oszacowanie modułu -tej współrzędnej wektora daje nierówność:


End of proof.gif

Dowód następnych dwu obserwacji pozostawiamy jako ćwicznia 4 i 6.

Obserwacja 15.10

W grafie prostym mamy wtedy i tylko wtedy, gdy któraś spójna składowa grafu jest grafem regularnym stopnia .

Obserwacja 15.11

W spójnym grafie prostym liczba jest wartością własną macierzy wtedy i tylko wtedy, gdy jest regularnym grafem dwudzielnym stopnia .

Twierdzenie 15.12 [wzór Hoffman'a]

W grafie regularnym stopnia zachodzi



gdzie oznacza największy możliwy rozmiar indukowanej antykliki w grafie .

Dowód

Niech oraz



gdzie jest macierzą diagonalną rozmiaru , która na przekątnej ma jedynki, a jest macierzą rozmiaru w całości wypełnioną jedynkami. Ponadto niech wektor będzie funkcją charakterystyczną najliczniejszego zbioru niezależnego takiego, że jest antykliką. Oznacza to, że



Wtedy jest funkcją charakterystyczną zbioru sąsiadów wierzchołków w , czyli



To z kolei daje, że



i w konsekwencji



Uzasadnimy teraz, że . Dla mamy:



Z kolej każdy inny wektor własny macierzy o wartości własnej , który jest prostopadły do spełnia



przy czym oczywiście . Oznacza to, że wszystkie wartości własne macierzy są nieujemne. Niech więc będzie ortogonalną bazą złożoną z wektorów własnych macierzy , a będą odpowiadającymi im wartościami własnymi. Niech ponadto będzie rozkładem wektora w tej bazie. Wtedy:


W konsekwencji



Ponieważ a , to ta ostatnia jest innym zapisem dowodzonej nierówności.

End of proof.gif

Wniosek 15.13

W regularnym grafie zachodzi



Dowód

Ponieważ podział zbioru wierzchołków na rozłączne podzbiory indukujące antykliki, jest równoważny z kolorowaniem grafu przy użyciu kolorów, to



Jeśli teraz jest stopniem regularności grafu to Twierdzenie 15.12 daje więc



Ponieważ graf jest -regularny, to na mocy Obserwacji 15.10 mamy , co pozwala zakończyć dowód.

End of proof.gif