Matematyka dyskretna 11 PDF

Preview

Summary

grafy...

Description

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

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

Macierz sąsiedztwa macierz

, oznaczany przez

to

grafu prostego

rozmiaru

to zero-jedynkowa

, gdzie

Uwaga Macierz sąsiedztwa grafu nieskierowanego jest symetryczna.

Graf prosty

i graf skierowany

Przykład Na rysunku Graf prosty przedstawiono graf prosty skierowany o wierzchołkach wyglądają następująco:

o wierzchołkach

oraz graf

. Macierze sąsiędztwa grafów

Domknięcie przechodnie grafu skierowanego

, to graf

oraz

taki, że:

, oraz

  wtedy i tylko wtedy, gdy w grafie

istnieje skierowana marszruta z

do

.

Twierdzenie 15.1 Niech marszrut z

do

jest dana elementem

będzie grafem skierowanym. Wtedy liczba skierowanych macierzy:

Dowód Wystarczy pokazać, że

(*) o długości .

jest macierzą, w której

jest liczbą skierowanych marszrut z

do

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

Wartość

,

, oraz

to liczba wszystkich skierowanych marszrut z

do

, to

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.

Graf

(a) oraz jego przechodnie domknięcie

(b)

Przykład Grafy przedstawione na animacji. Macierz sąsiedztwa grafu

Ponadto

i

to

zostały

W macierzy

wartość

marszrut z wierzchołka rzeczywiście i znaleźć w grafie

do ,

o długości co najwyżej

. Dla przykładu i , , są wszystkimi skierowanymi marszrutami jakie można

prowadzące z wierzchołka

do

sąsiedztwa dla przechodniego domknięcia grafu

to

Warto zaobserwować oczywisty fakt, że macierz macierzy przekątnej. Wniosek 15.2 Dla grafu

mówi o liczbie różnych skierowanych

o długości co najwyżej

można równie dobrze uzyskać z

przez zamianę każdej niezerowej wartości na

o wierzchołkach

jedynkowa macierz

, jeśli tylko

grafu rozmiaru

Zorientowana macierz incydencji otrzymana z macierzy incydencji jedynek przez (minus jeden).

, to

to zero, gdzie

grafu prostego to macierz

, rozmiaru

poprzez zastąpienie w każdej kolumnie jednej z dwu

Graf prosty

Przykład

oraz wyzerowanie

i

macierzy

Macierz incydencji

. Z kolei macierz

,

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

Obserwacja 15.3 

Dla macierzy incydencji zachodzi



oraz zorientowanej macierzy incydencji

W zorientowanej macierzy incydencji

Macierz stopni macierz

grafu prostego rozmiaru

mamy:

to diagonalna

, 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 Przykład

jest macierzą transponowaną macierzy

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

 wierzchołek

z

jest równoważne temu, że krawędź . Tak więc

wtedy i tylko wtedy, gdy

. Wtedy

 z

incydentnych do

sąsiaduje z

jest równoważne temu, że krawędź

. Sumując wartości

dla

, czyli stopień

łączy .

jest incydentna

uzyskujemy liczbę krawędzi .

Twierdzenie 15.5 Niech

będzie grafem skierowanym o

rozmiarach incydencji zbioru

wierzchołkach, a macierz

o

, będzie minorem (podmacierzą) zorientowanej macierzy , w którym kolumny odpowiadają krawędziom z pewnego podzbioru . 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 ścieżki od

do

. Ponumerujmy wierzchołki z

i

w grafie to liczność najkrótszej

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 w ścieżkach i indeksem , czyli

. Oczywiście, dla są różne. Tę ostatnią krawędź ścieżki .

Ponieważ w drzewie

jest dokładnie

jest bijekcją między krawędzi

ostanie krawędzie

oznaczmy, tak jak na rysunku,

krawędzi, przypisanie wierzchołkowi a

. W kolumnie

macierzy

krawędzi

, odpowiadającej

, są jedynie dwa niezerowe elementy - jeden leży w wierszu

,

odpowiadającemu wierzchołkowi co wierzchołek , wierzchołek

, a drugi w wierszu . Skoro krawędź ma ten sam numer musi leżeć na ścieżce z do . Tym samym jest

bliżej niż , a zatem przekątną, co kończy dowód.

. Macierz

jest więc macierzą trójkątną górną z niezerową

Załóżmy teraz, że nie jest drzewem. Ponieważ ma jedynie miedzy liczbą wierzchołków, krawędzi i składowych spójnych daje, że Niech wierzchołki

tworzą składową, w której nie występuje

wierszu i -tej kolumnie macierzy

jest niezerowy element

incydentny z krawędzią

. Wierzchołek

oczywiście w tej samej składowej co

, a zatem macierz

w -tym wierszu. Sumując teraz wiersze macierzy wektor zerowy. To oczywiście oznacza, że macierz

Wniosek 15.6

krawędzi, to zależność ma co najmniej składowe. . Jeżeli, w

-tym

, to wierzchołek

jest

będący drugim końcem krawędzi ma liczbę

o indeksach jest osobliwa.

leży

w -tej kolumnie i otrzymujemy

W spójnym grafie prostym

o

wierzchołkach rząd macierzy

Wielomian charakterystyczny grafu sąsiedztwa

wynosi

.

to wielomian charakterystyczny macierzy

.

Permanent grafu

to permanent macierzy

, czyli

gdzie suma

rozciąga się po wszystkich permutacjach

macierzy

.

Wyznacznik grafu

to wyznacznik macierzy

, zaś

oznacza element

, 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 gdy ma niezerowy permanent.

ma skojarzenie doskonałe wtedy i tylko wtedy,

Dowód Niech

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

1. Permanent grafu liczb

jest niezerowy wtedy i tylko wtedy, gdy istnieje permutacja

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 liczb

ma doskonałe skojarzenie taka, że

wtedy i tylko wtedy, gdy istnieje permutacja 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 zsumowaniu skojarzeń odpowidającym wszystkim cyklom permutacji doskonałe w grafie .

. Po otrzymamy skojarzenie

Graf

Skojarzenie doskonałe w grafie

{{przyklad||| Rozważmy graf rysunku Graf G5. Macierz sąsiedztwa

Permanent

przedstawiony na

to

, 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 Obserwacja 15.8

to wartość własna macierzy sąsiedztwa

.

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

 Obserwacja 15.9

na minimalną wartość własną macierzy

, .

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 macierzy założyć, że wektora

oraz

będzie niezerowym wektorem własnym o wartości własnej

. Bez straty ogólności można . Oszacowanie modułu -tej współrzędnej

daje nierówność:

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

Obserwacja 15.10 W grafie prostym składowa grafu

mamy

wtedy i tylko wtedy, gdy któraś spójna

jest grafem regularnym stopnia

.

Obserwacja 15.11 W spójnym grafie prostym tylko wtedy, gdy

liczba

jest wartością własną macierzy

jest regularnym grafem dwudzielnym stopnia

wtedy i

.

Twierdzenie 15.12 [wzór Hoffman'a] W grafie regularnym

gdzie Dowód

zachodzi

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

Niech

gdzie

stopnia

oraz

jest macierzą diagonalną rozmiaru

macierzą rozmiaru

, która na przekątnej ma jedynki, a

jest

w całości wypełnioną jedynkami. Ponadto niech wektor

będzie funkcją charakterystyczną najliczniejszego zbioru niezależnego że

.

takiego,

jest antykliką. Oznacza to, że

Wtedy

To z kolei daje, że

i w konsekwencji

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

, czyli

Uzasadnimy teraz, że

. Dla

Z kolej każdy inny wektor własny do

macierzy

mamy:

o wartości własnej

, który jest prostopadły

spełnia

przy czym oczywiście macierzy są nieujemne. Niech więc własnych macierzy

,a

. Oznacza to, że wszystkie wartości własne będzie ortogonalną bazą złożoną z wektorów będą odpowiadającymi im wartościami własnymi. Niech

ponadto

będzie rozkładem wektora

w tej bazie. Wtedy:

W konsekwencji

Ponieważ nierówności.

a

, to ta ostatnia jest innym zapisem dowodzonej

Wniosek 15.13 W regularnym grafie

zachodzi

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

Jeśli teraz

jest stopniem regularności grafu

indukujące

to Twierdzenie 15.12 daje więc

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

, co...