Zagadnienia

13.1 Grafy

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.

Optymalizacja I