1) Grafem skierowanym nazywamy strukturę , gdzie
jest zbiorem, nazywanym zbiorem wierzchołków,
jest zbiorem, nazywanym zbiorem krawędzi (strzałek) zaś
i
są funkcjami
zwanymi początkiem i końcem krawędzi.
2) nazywamy podgrafem grafu
gdy W' i S' są podzbiorami W i S odpowiednio zaś k' i p' są obcięciami funkcji k i p do S'.
3) Graf nazywamy skończonym gdy jego zbiory wierzchołków
i krawędzi
są skończone.
4) Graf nazywamy ukorzenionym gdy jest wyróżniony jeden z wierzchołków.
Na tym wykładzie będziemy ukorzeniać grafy przez wyprowadzenie z wyróżnionego wierzchołka krawędzi bez końca.
Niech będzie grafem skierowanym.
1) Drogą długości n od wierzchołka A do B nazywamy taki ciąg krawędzi , że istnieje ciąg wierzchołków
spełniający warunki:
,
i
.
2) Drogę nazywamy prostą gdy w ciągu
wierzchołki
są różne.
3) Cyklem nazywamy drogę od A do tego samego wierzchołka A.
Niech będzie grafem skierowanym.
1) Graf G nazywamy spójnym gdy istnieje droga między dowolnymi dwoma wierzchołkami.
2) Graf G nazywamy drzewem gdy jest spójny i nie ma cykli.
3) Podgraf grafu
nazywamy drzewem spinającym,
gdy W' =W i H jest drzewem.
4) Liściem nazywamy wierzchołek drzewa z którego wychodzi jedna krawędź.
Dokładniej jest liściem
gdy
.
Jeżeli istnieje droga między wierzchołkami i
to istnieje droga prosta między tymi wierzchołkami.
Niech będzie drogą pomiędzy wierzchołkami
o minimalnej długości. Jeżeli nie jest ona prosta to istnieją wierzchołki
dla
. Wtedy droga
pomiędzy wierzchołkami
jest krótsza wbrew założeniu.
Skończony spójny graf zawiera poddrzewo spinające.
Niech będzie maksymalnym poddrzewem grafu
. Aby wystarczy pokazać, że każdy wierzchołek
należy do
. Przypuśćmy, że
.
Ze spójności wynika istnienie drogi
pomiędzy wierzchołkami
kończącej się w
. Niech
będzie największym indeksem, dla którego
. Wówczas podgraf
jest większym poddrzewem.
Jeżeli drzewo ma przynajmniej dwa wierzchołki to ma co najmniej dwa liście.
Rozważmy drogę prostą , między wierzchołkami
, o maksymalnej długości. Drzewo nie ma cykli więc
. Ponieważ nie da się tej drogi przedłużyć to jej końce są liściami.
Niech będzie spójnym grafem spójnym zaś
jego liściem. Jeżeli
jest podgrafem
powstałym przez wyrzucenie liścia
i krawędzi
związanej z nim to
jest grafem spójnym.
Niech będzie drogą prostą w grafie
między wierzchołkami
, gdzie
. Jeżeli
jest liściem to
a stąd
więc droga nie jest prosta.
Ponieważ podgraf drzewa nie zawiera cykli więc bezpośrednio otrzymujemy:
Niech będzie drzewem zaś
jego liściem.
Jeżeli jest podgrafem
powstałym przez wyrzucenie liścia
i krawędzi
związanej z nim to
jest drzewem.
Niech będzie grafem skończonym.
Wówczas równoważne są warunki:
a) jest drzewem.
b) i
jest grafem spójnym.
c) i
nie ma cykli.
Drzewo jest grafem spójnym, więc wystarczy pokazać przez indukcję względem ,
że .
Jeżeli
to
bo
nie zawiera pętli.
Niech
i przyjmijmy, że każde mniejsze drzewo ma o jedną krawędź mniej niż wierzchołków. Na mocy lematu * graf posiada liść
. Po usunięciu go wraz ze związaną z nim krawędzią otrzymujemy mniejsze drzewo
. Zatem na mocy założenia indukcyjnego
a stąd
.
Ponieważ jest spójny więc zawiera poddrzewo spinające
, gdzie
. Na mocy poprzedniej implikacji
. Stąd
a zatem
i
jest drzewem i nie ma cykli.
jest sumą spójnych składowych
,
które są drzewami. Na mocy pierwszej implikacji .
Teraz . Stąd
i
jest drzewem.
Niech będzie drzewem skończonym, zaś graf
powstaje z
przez dodanie jednej krawędzi. Wówczas
zawiera dokładnie jeden cykl prosty.
Algorytm szukania cyklu.
Z grafu kolejno wyrzucamy liście wraz ze związanymi z nimi krawędziami. Otrzymany podgraf
jest cyklem.
Rzeczywiście jest spójny, nie ma liści i
ponieważ
. Warunki te implikują, że z każdego wierzchołka wychodzą dokładnie dwie krawędzie. Zatem
jest spójnym zbiorem cykli a więc cyklem.
Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.
strona główna | webmaster | o portalu | pomoc
© Wydział Matematyki, Informatyki i
Mechaniki UW, 2009-2010. Niniejsze materiały są udostępnione bezpłatnie na licencji Creative Commons Uznanie autorstwa-Użycie niekomercyjne-Bez utworów zależnych 3.0 Polska.
Projekt współfinansowany przez Unię Europejską w ramach
Europejskiego Funduszu Społecznego.
Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.