Grafem = para G=(V,E) gdzie V zbiór skończony nie pusty natomiast E⊆{A⊆V, |A|=2}=P2(V) zbiór nieuporządkowanych par.
Reprezentacja macierzowa :
Jeśli graf G , którego wierzchołki są oznakowane liczbami ze zbioru {1,2, ... , n} to macierzą sąsiedztwa A nazywamy jest macierz wymiaru n x n której wyraz o indeksach i,j jest równy liczbie krawędzi łączących wierzchołek i z wierzchołkiem j . Jeśli oznakujemy również krawędzie liczbami ze zbioru {1,2,..., m} to macierzą incydencji M nazwiemy macierz wymiaru n x m której wyraz o indeksach i, j jest równy 1, jeśli wierzchołek i jest incydentny z krawędzią j , i równy 0 w przeciwnym razie.
Podgraf rozpinający zawiera wszystkie wierzchołki wyjściowego grafu.
Podgraf indukowany H=(W,F) taki że F=P2(W)∩ E (zawiera wszystkie krawędzie łączące jego wierzchołki w wyjściowym grafie)
k- kostką Qk to graf którego wierzchołki odpowiadają ciągom (a1,a2, ... , ak) takim że każdy wyraz ai jest równy 0 lub 1 i którego krawędzie łączą ciągi różniące się dokładnie jednym wyrazem. Taki graf ma 2k wierzchołków i 2k - 1 krawędzi , jest k- regularny.
Droga - ciąg wierzchołków (v0,v1, ... vn) taki że
1)dla każdego 0≤i≤n-1 {vi,vi+1}∈E (dwa kolejne wierzchołki połączone krawędzią )
2)dla każdego 0≤i,j≤n-1 i≠j to {vi,vi+1}≠{vj,vj+1} (nie ma krawędzi wielokrotnych)
Jeśli i ≠ j to vi ≠ vj droga prosta (wierzchołki się nie powtarzają)
Długość drogi d=n-1.
Cykl droga (v0,v1, ... ,vn ) taka że v0=vn i n≥3
Cykl prosty jeśli droga prosta.
Lemat : Dla każdego grafu G=(V,E) suma stopni wszystkich wierzchołków =2|E|
Dowód: Każda krawędź ma dwa końce.
Lemat ten jest nazywany lematem o uściskach dłoni , ponieważ stwierdza on ze w trakcie dowolnego powitania ogólna liczba podanych sobie rąk jest równa podwojonej liczbie faktycznie dokonanych powitań. (z Bryanta)
Lemat Jeśli dla każdego wierzchołka w G deg v≥2 to graf zawiera pewien cykl prosty.
Uwaga W każdym grafie liczba wierzchołków stopnia nieparzystego jest parzysta. (Dowód Bryant str50)
Cykl Eulera dowolny cykl przechodzący przez wszystkie wierzchołki grafu i przez każdą krawędź dokładnie jeden raz (czyli krawędzie nie mogą się powtarzać natomiast wierzchołki mogą).
Tw. Eulera :Graf spójny ma cykl Eulera każdy wierzchołek ma stopień parzysty.
Tw. G ma cykl Eulera <=>G jest spójny i każdy wierzchołek ma stopień parzysty i |V(G)|≥3.
Tw. G posiada drogę Eulera <=> G spójny i liczba wierzchołków stopni nieparzystych nie większa niż dwa
G1 ≅ G2 istnieje f:V(G1)→ V(G2) 1-1 i na taka że {x,y}∈E(G1) < = > {f(x), f(y)}∈E(G2)
Graf G1 jest izomorficzny z grafem G2 jeśli istnieje takie, różnowartościowe i na, przyporządkowanie wierzchołków grafu G2 wierzchołkom grafu G1 , że jeśli jakieś dwa wierzchołki są połączone krawędzią w jednym z grafów, to odpowiadające im wierzchołki w drugim grafie również łączy krawędź. Izomorfizm grafów zachowuje właściwie wszystkie własności: liczbę wierzchołków, liczbę krawędzi, stopnie wierzchołków, spójność, planarność. Dlatego grafy izomorficzne zwykle utożsamia się.
Graf spójny <=>dla każdych dwóch wierzchołków u i v istnieje u-v droga (każde dwa wierzchołki połączone drogą)
Składowa spójności grafu każdy maksymalny podgraf spójny grafu.
Drzewo graf spójny i acykliczny.
Graf jest lasem <=>jest acykliczny.
Każdy wierzchołek stopnia pierwszego nazywamy liściem.
Uwaga :Każde nie trywialne drzewo ma co najmniej dwa liście.
Tw. Następujące warunki są równoważne: (dowód Kulikowski str124)
1) G drzewo
2) dla każdej pary wierzchołków u,v∈V istnieje w G dokładnie(tylko) jedna u-v droga
3) G spójny i |V|=|E|+1
4) G acykliczny i |V|=|E|+1
5) G acykliczny i jeśli dodamy krawędź łączącą nie sąsiadujące wierzchołki to w drzewie otrzymamy dokładnie jeden cykl
Własności drzewa:
1.spójne
2.acykliczne
3.kazde dwa wierzchołki łączy tylko jedna droga
4.|V|=|E|+1
5.dodanie krawędzi łączącej nie sąsiadujące wierzchołki sprawia że otrzymujemy dokładnie jeden cykl , natomiast usunięcie dowolnej krawędzi (bez przyległych wierzchołków ) rozspójnia graf
Tw. Każdy spójny graf rozpinający posiada drzewo rozpinające.(Zawiera wszystkie wierzchołki grafu)
(Dowód z ksera w zeszycie)
Graf prosty daną parę wierzchołków łączy tylko jedna krawędź.
δ(G) minimalny stopień wierzchołka w grafie.
Δ(G) maksymalny stopień wierzchołka w grafie.
Graf spójny jeśli nie można go przedstawić w postaci sumy dwóch grafów.
Spójność wierzchołkowa G to najmniejsze k że istnieje k- elementowy zbiór wierzchołków S
taki że G\S niespójny lub trywialny(jednowierzchołkowy)
K(Kn)=n-1 K(T)=1 (bo drzewo nie zawiera cyklu) K(Cn)=2
Gdy usuwamy wierzchołki usuwamy też krawędzie z nimi incydentne.
Spójność krawędziowa G to najmniejsze k że istnieje k- elementowy zbiór krawędzi F
że G\F jest niespójny.
λ(Kn)=n-1 λ(T)=1 λ(Cn)=2
Nierówność Whitneya:
W każdym grafie G zachodzi K(G)≤λ(G)≤δ(G) (Dowód Kulikowski str79)
v∈V wierzchołek rozcinający spójnego grafu G <=>G\v niespójny czyli K(G)=1.
Tw. Wierzchołek v spójnego grafu G jest wierzchołkiem rozcinającym <=>w G istnieje przynajmniej jedna para wierzchołków u i w taka że każda u-w droga przechodzi przez v. (tw. z Kulikowskiego)
Most krawędź po której wyjęciu rozspójnia się graf.
Tw. Krawędź l jest mostem grafu G <=> nie wchodzi w skład żadnego cyklu prostego. (Tw. z Kulikowskiego)
Tw. G graf spójny Następujące warunki są równoważne :
1) wierzchołek v rozcinający
2) istnieją wierzchołki u i w t,że każda u-w droga przechodzi przez v (Dowód 1=> 2 Kulikowski str80)
3) istnieje podział zbioru V-{v} na niepuste podzbiory V1 i V2 t,że dla każdego u∈V1
i dla każdego w∈V2 każda u-w droga przechodzi przez v
G jest dwuspójny <=> K(G)≥2
G jest k- spójny <=>K(G)≥ k
Graf dwuspójny ma co najmniej trzy wierzchołki.
Tw. G dwuspójny <=>każde 2 wierzchołki leżą na pewnym cyklu prostym.
Tw. Aives Graf jest dwuspójny <=>dla każdych trzech wierzchołków x,y,z ∈V istnieje x-y droga przechodząca przez z.
Odległość v od w dist (v ,w) to długość najkrótszej v-w drogi lub +∞ jeśli v i w leżą w różnych składowych.
Def: G=(V,E) Gk=(V,Ek) {x,y}∈Ek <=>distG (x, y) ≤ k
Średnica grafu G diam (G) to max po u ,v ∈V z dist (u ,v)
H jest blokiem grafu G <=>jest maksymalnym podgrafem dwuspójnym lub H=K2 i krawędź grafu H jest mostem grafu G.
B1,B2, ... , Bk wszystkie bloki G
u1,u2, ... , us wszystkie wierzchołki rozcinające grafu G
bc(G)= ({B1,B2, ... , Bk, u1,u2, ... , us}=X)
bc(G) graf bloków i wierzchołków rozcinających grafu G
{a , b}∈X <=>a jest blokiem , b jest wierzchołkiem rozcinającym b∈a
(lub odwrotnie)
Tw. Każde dwa bloki mają co najwyżej jeden wierzchołek wspólny i jest on wierzchołkiem rozcinającym w grafie.
Tw. Każdy wierzchołek rozcinający należy do przynajmniej dwóch bloków.
Tw. Dla każdego grafu spójnego G bc(G) jest drzewem.
Def: u,v ∈(V) {u,v} nie należy do E, S zawiera się w V(G) S jest zbiorem u-v rozdzielającym <=> każda u-v droga w G przechodzi przez S (<=> u i v leżą w różnych składowych grafu G\S)
Tw. Mengera Jeśli dla każdego u-v rozdzielającego zbioru S mamy |S| ≥k to istnieje w G co najmniej k wewnętrznie rozłącznych u-v dróg.
Wniosek : Maksymalna liczba rozłącznych u-v dróg w G jest równa minimalnej liczności zbioru u-v rozdzielającego.
Tw. Mengera Niech G=(V,E) będzie dowolnym grafem i niech X,Y ⊆ V. Wówczas minimalna liczba wierzchołków które oddzielają X od Y jest równa maksymalnej liczbie rozłącznych ścieżek z x do Y. (Tw. z Bryanta + dowód)
Graf właściwy nie zawiera pętli.
Graf k- regularny wszystkie wierzchołki k stopnia.
Graf dwudzielny <=> istnieje podział V=V1+ V2 V1∩ V2 =pusty
P2(V1)∩ E= pusty (wierzchołki w V1 nie połączone)
P2(V2)∩ E= pusty (wierzchołki w V2 nie połączone)
Tw. Graf jest dwudzielny <=>gdy nie zawiera cykli mających nieparzystą ilość krawędzi.(Dowód Bryant)
Tw.W grafie dwudzielnym każdy cykl ma parzystą długość.
Tw. ( o maksymalnym skojarzeniu)
W grafie dwudzielnym maksymalna liczba niezależnych (rozłącznych) krawędzi jest równa minimalnej liczbie wierzchołków pokrywających wszystkie krawędzie.
Wniosek: G=(V,E) |V|>1 G jest k- spójny <=>dla każdej pary wierzchołków istnieje k rozłącznych u-v dróg
prostych w G.
Def: U zawarty w V x∈V\U x-U wachlarz jest to zbiór |U| dróg prostych z x do U takich że wspólnym wierzchołkiem dla każdych dwóch z nich jest x. RYS
Tw. Diraca G jest k- spójny <=>|V|≥k+1 i dla każdego U zawartego w V i dla każdego x∈V |U| =k i x nie należy do U to istnieje x-U wachlarz w G
Wniosek: G jest k- spójny k≥2 to każdy k- elementowy zbiór wierzchołków leży na pewnym cyklu prostym.
Cykl Hamiltona cykl który przechodzi przez każdy wierzchołek w grafie dokładnie i tylko jeden raz.
L(G) graf krawędziowy G
Definicja z ćwiczeń: G=(V,E) L(G)=(E,F) e1,e2∈F wtw gdy |e1∩ e2|=1
Definicja z Kulikowskiego:
L(G) graf taki że :
1)Każdej krawędzi li grafu G będzie odpowiadał jednoznacznie jej wierzchołek bi grafu L(G)
2)Dwa węzły bi i bj w grafie L(G) są połaczone krawędzią λi j <=>odpowiednie krawędzie li i lj w grafie G są do siebie przyległe.
Przykład:Rys 5.7\202 Kulikowski
Θgraf to spójny graf, ma dokładnie dwa wierzchołki stopnia 3 pozostałe stopnia 2
Tw. G dwuspójny i nie zawiera Θpodgrafu to G jest grafem Hamiltona.
Dk(G)={v∈V; deg v ≤k}
Tw Po'se G jest grafem o p wierzchołkach p≥3 . Jeśli dla każdego n 1≤n< (p-1)/2 |Dn(G)|<n oraz dla nieparzystego p |D(p-1)/2(G)|≤(p-1)/2 to G jest grafem Hamiltona.
Lemat: Każdy wierzchołek stopnia ≥(p-1)/2 sąsiaduje z każdym wierzchołkiem stopnia ≥p/2.
Wniosek (Tw Diraca)
G ma p wierzchołków p≥3 i dla każdego v∈V deg v≥p/2 to G ma cykl Hamiltona.
Wniosek (Tw Ore'a) (Dowód Bryant str92)
G ma p wierzchołków p≥3 i dla każdych dwóch wierzchołków u i v takich że {u,v} nie należy do E (nie połączonych krawędzią) deg u + deg v ≥p wówczas G ma cykl Hamiltona.
Def: G=(V,E) v∈V N(v)={ w∈V; {v,w}∈E} Zbiór wszystkich wierzchołków połączonych krawędzią z v.
Tw Halla G=(V,E) dwudzielny z klasami dwudzielności X i Y . Wówczas w G istnieje |X| niezależnych krawędzi rozłącznych <=>dla każdego S zawartego w X |S| ≤ |N(S)|
Zbiór S zawarty w V niezależny w G <=> P2(S) ∩E= pusty (S zbiór wierzchołków nie połączonych ze sobą)
Zbiór S zawarty w V pokrywa E <=> dla każdego e∈E e∩S≠ pustego
Wierzchołek a pokrywa krawędź l jeśli jest on do niej przyległy.
Zbiór F zawarty w E niezależny <=> dla każdych dwóch f1,f2∈F f1∩ f2= pusty (Każde dwie krawędzie z F nie mają wspólnych wierzchołków)
Zbiór F zawarty w E pokrywa V <=> ??
Krawędź pokrywa oba wierzchołki do niej przyległe.
β0(G) największe k takie że istnieje k- elementowy niezależny zbiór wierzchołków
β1(G) największe k takie że istnieje k- elementowy niezależny zbiór krawędzi
α0(G) najmniejsze k takie że istnieje k- elementowy zbiór wierzchołków pokrywający E
α1(G) najmniejsze k takie że istnieje k- elementowy zbiór krawędzi pokrywający V
Przykład
β0(Kn)=1 (jeden wierzchołek sam ze sobą nie jest połączony, a tak w grafie pełnym wszystkie wierzchołki są ze sobą połączone krawędziami)
β1(Kn)=podłogo z n/2
α0(Kn)=n-1
α1(Kn)=sufit z n/2
β0(Cn)=podłoga z n/2
β1(Cn)=podłoga z n/2
α0(Cn)=sufit z n/2
α1(Cn)=sufit z n/2 gdzie Cn cykl o długości n
Uwaga:
1)Jeśli N pokrywa E i |N|= α0 to V\N jest niezależny .
2)Jeśli M niezależny i |M|= β0 to V\M pokrywa E.
Tw Gallai'a:
Dla dowolnego grafu G takiego że δ(G)>0 α0+β0=α1+β1=|V|=n. (Dowód Kulikowski str 102)
Tw. W każdym grafie dwudzielnym G zachodzi β1(G)=α0(G) .
Tw.G ma p wierzchołków , p≥3 i K(G) ≥β0(G) to G ma cykl Hamiltona.
FAKTORYZACJA
k- faktor grafu G to każdy k- regularny podgraf rozpinający grafu G.
1- faktor nazywamy skojarzeniem doskonałym RYS
k- faktoryzacja grafu G to podział zbioru krawędzi na k-faktory postaci E=E1+E2+.....+Es takie że Ei∩Ej= pusty gdzie i≠j oraz dla każdego i (V,Ei) k- regularny
Tw. Kn ma 1- faktoryzacje <=> n jest parzyste.
Tw. Tutte'a G o p wierzchołkach ma 1- faktor <=>
1) p parzyste
2) dla każdego zbioru wierzchołków S zawartego w V liczba nieparzystych składowych w G\S nie przekracza |S|
Tw. Każdy k- regularny graf dwudzielny k≥1 ma 1- faktoryzację (Trzeba pokazać że k- regularny graf dwudzielny ma 1- faktor)
Tw. K2n+1 ma 2- faktoryzację ma cykle Hamiltona. (?)
KOLOROWANIE GRAFÓW
k- pokolorowanie grafu G na klasy {1,2, ... , k} to każda funkcja f: V →{1,2, ...,k} taka że dla każdego i f -1({i}) jest zbiorem niezależnym
Funkcja ta przyporządkowuje każdemu wierzchołkowi jeden z k kolorów tak że dwa sąsiednie są innego koloru.
Liczbą chromatyczną G χ(G) nazywamy najmniejsze k takie że istnieje k- pokolorowanie grafu G czyli k= χ(G)
T drzewo χ(T)=2
χ(Cn)=2 dla n parzystych χ(Cn)=3 dla n nieparzystych
Graf k- krytyczny czyli taki że dla każdego wierzchołka v χ(G)=k i χ(G-v)<k.
Tw. Dla każdego grafu G o p wierzchołkach zachodzi p/β0≤ χ(G) ≤ p- β0+1
Tw. H indukowany podgraf G. k = max po H z δ(H) wówczas χ(G) ≤ k+1.
Wniosek: Dla każdego G zachodzi χ(G) ≤ Δ(G) +1.
Tw. Brooksa Jeśli Δ(G) =n , G spójny to χ(G) ≤ n. (Chyba że n=2 i G jest cyklem nieparzystym lub n>2 i G=Kn+1) (Dowód Kulikowski str 262, Bryant str146)
Wniosek :Jeśli graf G zawiera podgraf Kl to χ(G)≥ l. (z Kulikowskiego)
Lemat: Dla każdego grafu G χ(G) =max χ(H) gdzie H blok grafu G.
Def. W prawidłowo pokolorowanym grafie G gdzie liczba chromatyczna χ(G)=k zbiór wierzchołków ulega rozbiciu na rodzinę parami rozłącznych podzbiorów oznakowanych tą samą barwą czyli podzbiorów monochromatycznych :
Żadne dwa wierzchołki u i v należące do tego samego V χ nie są do siebie wzajemnie przyległe (nie połączone krawędzią) a zatem są to zbiory niezależne czyli | V χ |≤ β0(G). (definicja z Kulikowskiego)
k- pokolorowanie krawędzi to każda funkcja postaci f: E →{1,2, ...,k} taka że dla każdego i f -1({i}) zbiór niezależny. Funkcja taka przyporządkowuje każdej krawędzi jeden z k kolorów tak że dwie sąsiednie są innego koloru.
Indeks chromatyczny χ' (G) to minimalne k takie że istnieje k- pokolorowanie krawędzi.
Tw. Vizinga Dla każdego grafu G mamy Δ(G) ≤ χ' (G) ≤ Δ (G) + 1(Dowód Bryant str 103)
Tw. Königa Niech G=(V1,V2,E) graf dwudzielny i Δ(G)=d. Wówczas χ'(G)=d. (Dowód Bryant str 98)
PLANARNOŚĆ
Graf planarny <=> posiada taką interpretację geometryczną w której łuki reprezentujące krawędzie nie przecinają się.
Rysunek grafu planarnego dzieli płaszczyznę na regiony.
Grafy homeomorficzne to takie że jeden można przeprowadzić w drugi dodając lub usuwając wierzchołki stopnia drugiego.
Tw. Przy dowolnej płaskiej interpretacji grafu planarnego o n wierzchołkach i k krawędziach liczba regionów f spełnia równość f=k-n+1 przy czym G spójny.
Tw. Jeżeli f≥2i n≥3 to k≥3/2 f i k≤3n-6.
Tw. Kuratowskiego G jest planarny <=> nie zawiera podgrafu homeomorficznego z K3,3 lub K5.
Dalej nie z wykładu
Tw. Graf jest planarny gdy nie zawiera jako podgrafu grafu Kuratowskiego. (Szkic dowodu Bryant str 178)
Tw. Niech G rysunek płaski spójnego grafu planarnego o n wierzchołkach, m krawędziach i f regionach
wtedy n - m + f =2 (Dowód Bryant str 173)
Wniosek (z Bryanta +dowód str 176)Niech G=(V,E) graf planarny, w którym liczba krawędzi w najkrótszym cyklu jest równa r (liczba ta jest obwodem grafu G). Wówczas (r-2) |E| ≤ r (|V| -2). (Dowód Bryant str 176)
Wniosek:G spójny planarny graf prosty gdzie n≥3 ilość wierzchołków i k ilość krawędzi to k ≤ 3n - 6.
Jeśli ponadto G nie zawiera trójkątów to k ≤ 2n - 4. (Dowód Bryant str 175)
Wniosek: Niech G graf planarny o k składowych. Wówczas w dowolnej płaskiej reprezentacji grafu G , liczba regionów jest równa |E| - |V| +k +1 (Dowód Bryant str 174)