Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 63 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 65 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 67 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 69 Notice: Undefined variable: base in /home/misc/mst/public_html/lecture.php on line 36 Optymalizacja I – 13. Grafy – MIM UW

Zagadnienia

13. Grafy

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\rightarrow W zwanymi początkiem i końcem krawędzi.

2) H=\{ W^{{\prime}},S^{{\prime}};k^{{\prime}},p^{{\prime}}\} 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 s_{1},s_{2},...,s_{n}, że istnieje ciąg wierzchołków A=w_{0},w_{1},w_{2},...,w_{n}=B spełniający warunki:

\forall _{{1\leq i\leq n}}\ \{ p(s_{i}),k(s_{i})\}=\{ w_{{i-1}},w_{i}\}, A\in\{ p(s_{1}),k(s_{1})\} i B\in\{ p(s_{n}),k(s_{n})\}.

2) Drogę nazywamy prostą gdy w ciągu A=w_{0},w_{1},w_{2},...,w_{n}=B wierzchołki A=w_{0},w_{1},w_{2},...,w_{{n-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^{{\prime}},S^{{\prime}};k^{{\prime}},p^{{\prime}}\} 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\in W jest liściem G=\{ W,S;k,p\} gdy \exists!_{{s\in S}}\  A\in\{ p(s),k(s)\}.

Lemat 13.1

Jeżeli istnieje droga między wierzchołkami A i B to istnieje droga prosta między tymi wierzchołkami.

Niech s_{1},s_{2},...,s_{n} będzie drogą pomiędzy wierzchołkami A=w_{0},w_{1},w_{2},...,w_{n}=B o minimalnej długości. Jeżeli nie jest ona prosta to istnieją wierzchołki w_{i}=w_{j} dla 0\leq i<j<n. Wtedy droga s_{1},s_{2},...,s_{i},s_{{j+1}},...,s_{n} pomiędzy wierzchołkami

A=w_{0},w_{1},w_{2},...,w_{j},w_{{j+1}},...,w_{n}=B jest krótsza wbrew założeniu.

Twierdzenie 13.1

Skończony spójny graf zawiera poddrzewo spinające.

Niech T=\{ W^{{\prime}},S^{{\prime}};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\in W\setminus W^{{\prime}}.

Ze spójności G wynika istnienie drogi s_{1},s_{2},...,s_{n} pomiędzy wierzchołkami

A=w_{0},w_{1},w_{2},...,w_{n}=B kończącej się w T. Niech j będzie największym indeksem, dla którego w_{j}\not\in W^{{\prime}}. Wówczas podgraf T^{{\prime\prime}}=\{ W^{{\prime}}\cup\{ w_{j}\},S^{{\prime}}\cup\{ s_{{j+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ą s_{1},s_{2},...,s_{n}, między wierzchołkami

A=w_{0},w_{1},w_{2},...,w_{n}=B, o maksymalnej długości. Drzewo nie ma cykli więc A\neq 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\in W jego liściem. Jeżeli G^{{\prime}}=\{ W^{{\prime}},S^{{\prime}};k,p\} jest podgrafem G powstałym przez wyrzucenie liścia w i krawędzi s związanej z nim to G^{{\prime}} jest grafem spójnym.

Niech s_{1},s_{2},...,s_{n} będzie drogą prostą w grafie G między wierzchołkami

A=w_{0},w_{1},w_{2},...,w_{n}=B, gdzie A,B\in W^{{\prime}}. Jeżeli w_{j}=w jest liściem to s_{j}=s=s_{{j+1}} a stąd w_{{j-1}}=w_{{j+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\in W jego liściem.

Jeżeli G^{{\prime}}=\{ W^{{\prime}},S^{{\prime}};k,p\} jest podgrafem T powstałym przez wyrzucenie liścia w i krawędzi s związanej z nim to G^{{\prime}} 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)\Rightarrow b)

Drzewo jest grafem spójnym, więc wystarczy pokazać przez indukcję względem |W|,

że |W|=|S|+1.

1^{0} Jeżeli |W|=1 to S=\emptyset bo G nie zawiera pętli.

2^{0} Niech |W|=n\geq 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^{{\prime}}=\{ W^{{\prime}},S^{{\prime}};k,p\}. Zatem na mocy założenia indukcyjnego |W^{{\prime}}|=|S^{{\prime}}|+1 a stąd |W|=|W^{{\prime}}|+1=|S^{{\prime}}|+2=|S|+1.

b)\Rightarrow c)

Ponieważ G jest spójny więc zawiera poddrzewo spinające G^{{\prime}}=\{ W,S^{{\prime}};k,p\}, gdzie S^{{\prime}}\subset S. Na mocy poprzedniej implikacji |W|=|S^{{\prime}}|+1. Stąd |S|=|S^{{\prime}}| a zatem S=S^{{\prime}} i G=G^{{\prime}} jest drzewem i nie ma cykli.

c)\Rightarrow a)

G jest sumą spójnych składowych

G_{1}=\{ W_{1},S_{1};k,p\},\  G_{1}=\{ W_{2},S_{2};k,p\},...,G_{1}=\{ W_{n},S_{n};k,p\},

które są drzewami. Na mocy pierwszej implikacji \forall _{{1\leq j\leq n}}\ |W_{j}|=|S_{j}|+1.

Teraz |S|+1=|W|=\sum _{{j=1}}^{n}\,|W_{j}|=\sum _{{j=1}}^{n}\,\left(|S_{j}|+1\right)=|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\cup\{ 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^{{\prime}}=\{ W^{{\prime}},S^{{\prime}};k,p\} jest cyklem.

Rzeczywiście G^{{\prime}} jest spójny, nie ma liści i |S^{{\prime}}|=|W^{{\prime}}| ponieważ |S|=|W|. Warunki te implikują, że z każdego wierzchołka wychodzą dokładnie dwie krawędzie. Zatem G^{{\prime}} 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.

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.