13.1. Grafy
Definicja 13.1
1) Grafem skierowanym nazywamy strukturę G=W,S;k,p, gdzie W jest zbiorem, nazywanym zbiorem wierzchołków, S jest zbiorem, nazywanym zbiorem krawędzi (strzałek) zaś k i p są funkcjami k,p:S→W zwanymi początkiem i końcem krawędzi.
2) H=W′,S′;k′,p′ nazywamy podgrafem grafu G=W,S;k,p 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 G=W,S;k,p nazywamy skończonym gdy jego zbiory wierzchołków W i krawędzi S są skończone.
4) Graf G 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.
Definicja 13.2
Niech G będzie grafem skierowanym.
1) Drogą długości n od wierzchołka A do B nazywamy taki ciąg krawędzi s1,s2,…,sn, że istnieje ciąg wierzchołków A=w0,w1,w2,…,wn=B spełniający warunki:
∀1≤i≤npsi,ksi=wi-1,wi, A∈ps1,ks1 i B∈psn,ksn.
2) Drogę nazywamy prostą gdy w ciągu A=w0,w1,w2,…,wn=B
wierzchołki A=w0,w1,w2,…,wn-1 są różne.
3) Cyklem nazywamy drogę od A do tego samego wierzchołka A.
Definicja 13.3
Niech G 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 H=W′,S′;k′,p′ grafu G=W,S;k,p 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 A∈W jest liściem G=W,S;k,p gdy ∃!s∈SA∈ps,ks.
Lemat 13.1
Jeżeli istnieje droga między wierzchołkami A i B to istnieje droga prosta między tymi wierzchołkami.
Niech s1,s2,…,sn będzie drogą pomiędzy wierzchołkami A=w0,w1,w2,…,wn=B o minimalnej długości. Jeżeli nie jest ona prosta to istnieją wierzchołki wi=wj dla 0≤i<j<n. Wtedy droga s1,s2,…,si,sj+1,…,sn pomiędzy wierzchołkami
A=w0,w1,w2,…,wj,wj+1,…,wn=B jest krótsza wbrew założeniu.
∎
Twierdzenie 13.1
Skończony spójny graf zawiera poddrzewo spinające.
Niech T=W′,S′;k,p będzie maksymalnym poddrzewem grafu G=W,S;k,p. Aby wystarczy pokazać, że każdy wierzchołek G należy do T. Przypuśćmy, że A∈W∖W′.
Ze spójności G wynika istnienie drogi s1,s2,…,sn pomiędzy wierzchołkami
A=w0,w1,w2,…,wn=B kończącej się w T. Niech j będzie największym indeksem, dla którego wj∉W′. Wówczas podgraf T′′=W′∪wj,S′∪sj+1;k,p jest większym poddrzewem.
∎
Lemat 13.2
Jeżeli drzewo G ma przynajmniej dwa wierzchołki to ma co najmniej dwa liście.
Rozważmy drogę prostą s1,s2,…,sn, między wierzchołkami
A=w0,w1,w2,…,wn=B, o maksymalnej długości. Drzewo nie ma cykli więc A≠B. Ponieważ nie da się tej drogi przedłużyć to jej końce są liściami.
∎
Lemat 13.3
Niech G=W,S;k,p będzie spójnym grafem spójnym zaś w∈W jego liściem. Jeżeli G′=W′,S′;k,p jest podgrafem G powstałym przez wyrzucenie liścia w i krawędzi s związanej z nim to G′ jest grafem spójnym.
Niech s1,s2,…,sn będzie drogą prostą w grafie G między wierzchołkami
A=w0,w1,w2,…,wn=B, gdzie A,B∈W′. Jeżeli wj=w jest liściem to sj=s=sj+1 a stąd wj-1=wj+1 więc droga nie jest prosta.
∎
Ponieważ podgraf drzewa nie zawiera cykli więc bezpośrednio otrzymujemy:
Wniosek 13.1
Niech T=W,S;k,p będzie drzewem zaś w∈W jego liściem.
Jeżeli G′=W′,S′;k,p jest podgrafem T powstałym przez wyrzucenie liścia w i krawędzi s związanej z nim to G′ jest drzewem.
Twierdzenie 13.2
Niech G=W,S;k,p będzie grafem skończonym.
Wówczas równoważne są warunki:
a) G jest drzewem.
b) W=S+1 i G jest grafem spójnym.
c) W=S+1 i G nie ma cykli.
a)⇒b)
Drzewo jest grafem spójnym, więc wystarczy pokazać przez indukcję względem W,
że W=S+1.
10 Jeżeli W=1 to S=∅ bo G nie zawiera pętli.
20 Niech W=n≥2 i przyjmijmy, że każde mniejsze drzewo ma o jedną krawędź mniej niż wierzchołków. Na mocy lematu * graf posiada liść w. Po usunięciu go wraz ze związaną z nim krawędzią otrzymujemy mniejsze drzewo G′=W′,S′;k,p. Zatem na mocy założenia indukcyjnego W′=S′+1 a stąd W=W′+1=S′+2=S+1.
b)⇒c)
Ponieważ G jest spójny więc zawiera poddrzewo spinające G′=W,S′;k,p, gdzie S′⊂S. Na mocy poprzedniej implikacji W=S′+1. Stąd S=S′ a zatem S=S′ i G=G′ jest drzewem i nie ma cykli.
c)⇒a)
G jest sumą spójnych składowych
G1=W1,S1;k,p,G1=W2,S2;k,p,…,G1=Wn,Sn;k,p,
które są drzewami. Na mocy pierwszej implikacji ∀1≤j≤nWj=Sj+1.
Teraz S+1=W=∑j=1nWj=∑j=1nSj+1=S+n. Stąd n=1 i G jest drzewem.
∎
Lemat 13.4
Niech T=W,S;k,p będzie drzewem skończonym, zaś graf G=W,S∪s;k,p powstaje z T przez dodanie jednej krawędzi. Wówczas G zawiera dokładnie jeden cykl prosty.
Algorytm szukania cyklu.
Z grafu G kolejno wyrzucamy liście wraz ze związanymi z nimi krawędziami. Otrzymany podgraf G′=W′,S′;k,p jest cyklem.
Rzeczywiście G′ jest spójny, nie ma liści i S′=W′ ponieważ S=W. Warunki te implikują, że z każdego wierzchołka wychodzą dokładnie dwie krawędzie. Zatem G′ jest spójnym zbiorem cykli a więc cyklem.
∎
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.
