Matematyka dyskretna 1/Ćwiczenia 12: Grafy

From Studia Informatyczne

Grafy I



1. Grafy \displaystyle \mathbf{G}_1 oraz \displaystyle \mathbf{G}_2

Ćwiczenie 1

Niech \displaystyle \mathbf{G}_1 oraz \displaystyle \mathbf{G}_2 będą grafami przedstawionymi na rysunku 1. Przedstaw sumę \displaystyle \mathbf{G}_1\cup\mathbf{G}_2 , przecięcie \displaystyle \mathbf{G}_1\cap\mathbf{G}_2 , oraz różnicę \displaystyle \mathbf{G}_1-\mathbf{G}_2 .

Wskazówka

Skorzystaj z definicji sumy, przecięcia, oraz różnicy.

Rozwiązanie

<flash>file=Cw grafy operation.swf|width=300|height=150</flash>

2. Grafy \displaystyle \mathbf{G}_1\cup\mathbf{G}_2

<flash>file=Cw grafy operation.swf|width=300|height=150</flash>

3. Przecięcie \displaystyle \mathbf{G}_1\cap\mathbf{G}_2 oraz różnica \displaystyle \mathbf{G}_1-\mathbf{G}_2

Suma \displaystyle \mathbf{G}_1\cup\mathbf{G}_2 jest przedstawiona na rysunku 2, zaś przecięcie \displaystyle \mathbf{G}_1\cap\mathbf{G}_2 oraz różnica \displaystyle \mathbf{G}_1-\mathbf{G}_2 na rysunku 3.

 


4. Graf \displaystyle \mathbf{G}

Ćwiczenie 2

Graf \displaystyle \mathbf{G}=\left( V,E \right) jest przedstawiony na rysunku 4. Przedstaw graf ilorazowy \displaystyle \mathbf{G}/\!\triangleq dla relacji równoważności \displaystyle \triangleq\ \subseteq V\times V zdefiniowanej przez:

\displaystyle v_i \triangleq v_j\quad w.t.w. \displaystyle  \quad \left\vert i-j \right\vert\ jest wielokrotnością \displaystyle  \ 4.

Wskazówka

Skorzystać z definicji ilorazu podanego na wykładzie.

Rozwiązanie

<flash>file=Cw grafy iloraz odp.swf|width=300|height=200</flash>

5. Graf \displaystyle \mathbf{G}/\!\triangleq

Iloraz \displaystyle V/\triangleq zbioru \displaystyle V=\left\lbrace v_0,v_1,v_2,v_3,v_4,v_5,v_6,v_7,v_8,v_9 \right\rbrace to \displaystyle \left\lbrace \left\lbrace v_0,v_4,v_8 \right\rbrace,\left\lbrace v_1,v_5,v_9 \right\rbrace,\left\lbrace v_2,v_6 \right\rbrace,\left\lbrace v_3,v_7 \right\rbrace \right\rbrace . Z faktu, że \displaystyle v_0 v_2 \in E wynika, że wierzchołki \displaystyle \left\lbrace v_0,v_4,v_8 \right\rbrace oraz \displaystyle \left\lbrace v_2,v_6 \right\rbrace są sąsiednie w grafie \displaystyle \mathbf{G}/\!\triangleq . Z kolei krawędzie \displaystyle v_1 v_4, v_3 v_5 \in E dają krawędzie \displaystyle \left\lbrace \left\lbrace v_0,v_4,v_8 \right\rbrace,\left\lbrace v_1,v_5,v_9 \right\rbrace \right\rbrace oraz \displaystyle \left\lbrace \left\lbrace v_1,v_5,v_9 \right\rbrace,\left\lbrace v_3,v_7 \right\rbrace \right\rbrace w grafie \displaystyle \mathbf{G}/\!\triangleq . Ponadto nie występują tu już żadne inne krawędzie. Graf \displaystyle \mathbf{G}/\!\triangleq został przedstawiony na rysunku 5.

Ćwiczenie 3

Niech \displaystyle \mathbf{G} będzie grafem prostym z co najmniej dwoma wierzchołkami. Wykaż, że \displaystyle \mathbf{G} zawiera dwa wierzchołki tego samego stopnia.

Wskazówka

Skorzystaj z Zasady Szufladkowej Dirichleta.

Rozwiązanie

Niech \displaystyle \mathbf{G} ma \displaystyle n\geq 2 wierzchołków. Wierzchołek \displaystyle v\in{\sf V}\!\left(\mathbf{G}\right) nie może mieć więcej niż \displaystyle \left\vert {\sf V}\!\left(\mathbf{G}\right)-\left\lbrace v \right\rbrace \right\vert=n-1 sąsiadów. Stopień dowolnego wierzchołka z \displaystyle {\sf V}\!\left(\mathbf{G}\right) leży więc w zbiorze \displaystyle \left\lbrace 0,1,2,\ldots,n-1 \right\rbrace . Jeśli jakiś wierzchołek ma stopień \displaystyle 0 , czyli jest izolowany, to każdy inny wierzchołek może mieć co najwyżej \displaystyle n-2 sąsiadów. Z kolei gdyby istniał punkt \displaystyle w o stopniu równym \displaystyle n-1 , to każdy wierzchołek ze zbioru \displaystyle {\sf V}\!\left(\mathbf{G}\right)-\left\lbrace w \right\rbrace byłby sąsiadem \displaystyle w , więc nie mogłby mieć stopnia równego \displaystyle 0 . Zbiór \displaystyle S stopni wierzchołków grafu \displaystyle \mathbf{G} zawiera się więc albo w zbiorze \displaystyle \left\lbrace 0,1,2,\ldots,n-2 \right\rbrace , albo w \displaystyle \left\lbrace 1,2,3,\ldots,n-1 \right\rbrace , więc \displaystyle S jest co najwyżej \displaystyle \left( n-1 \right) -elementowy. Wszystkich wierzchołków jest \displaystyle n , więc z Zasady Szufladkowej Dirichleta otrzymujemy, że istnieją dwa wierzchołki o tym samym stopniu.

Ćwiczenie 4

Wykaż, że w grupie sześciu osób zawsze znajdą się trzy, które albo znają się nawzajem, albo żadna z nich nie zna dwóch pozostałych.

Wskazówka

Wybierz dowolną osobę i rozważ zbiór jego znajomych oraz osobno zbiór nieznajomych, zwracając uwagę na większy z tych dwu zbiorów.

Rozwiązanie

Wybierzmy dowolną osobę z rozważanej szóstki i oznaczmy ją za pomocą inicjału A. Załóżmy, że A w zbiorze pięciu pozostałych osób ma więcej znajomych niż nieznajomych. A ma więc \displaystyle 3 , \displaystyle 4 , lub \displaystyle 5 znajomych. Jeżeli istnieje chociaż jedna para w tym gronie, która się zna, to wraz z A tworzy poszukiwaną trójkę. Jeśli znajomi A nie znają się nawzajem, to trójka z nich tworzyłaby z kolei zbiór osób nieznających siebie. W przypadku, gdy A ma mniej znajomych niż nieznajomych rozumowanie jest symetryczne.

Ćwiczenie 5

Dopełnienie grafu \displaystyle \mathbf{G}=\left( V,E \right) to graf \displaystyle \overline{\mathbf{G}}=\left( V,\mathscr{P}_{2}\!\left( V \right)- E \right) . Przedstaw dopełnienie grafu pełnego \displaystyle \mathcal{K}_{n} oraz dwudzielnego grafu pełnego \displaystyle \mathcal{K}_{m,n} . Przedstaw graf, którego dopełnienie jest z nim izomorficzne.

Wskazówka

Przejrzyj definicje kliki, antykliki oraz pełnego grafu dwudzielnego.

Rozwiązanie

Dopełnieniem grafu pełnego jest graf pusty, tzn. \displaystyle \overline{\mathcal{K}_{n}}=\mathcal{A}_{n} . Na odwrót dopełnienie grafu pustego jest grafem pełnym: \displaystyle \overline{\mathcal{A}_{n}}=\mathcal{K}_{n} . Z kolei dopełnienie pełnego grafu dwudzielnego \displaystyle \mathcal{K}_{n,n} jest rozłączną sumą dwóch klik \displaystyle \mathcal{K}_{m}\cup\mathcal{K}_{n} .

Cykl piecioelementowy oraz ścieżka czteroelementowa są przykładami

grafów izomorficznych ze swoimi dopełnieniami.

Ćwiczenie 6

Niech \displaystyle \mathbf{G} będzie grafem prostym, w którym każdy wierzchołek ma co najmniej \displaystyle r\geq 2 sąsiadów. Wykaż, że \displaystyle \mathbf{G} zawiera cykl o długości co najmniej \displaystyle r+1 .

Wskazówka

Spróbuj budować indukcyjnie możliwie długą ścieżkę. Pokaż, że musi mieć co najmniej \displaystyle r elementów. Aby znaleźć cykl, rozważ sąsiadów ostatniego wierzchołka na tej ścieżce.

Rozwiązanie

Wskażemy odpowiednią ścieżkę definiując ją indukcyjnie. Załóżmy, że istnieje ścieżka o długości \displaystyle k< r tzn. \displaystyle v_1\to v_2\to\ldots\to v_k . Wierzchołek \displaystyle v_k ma co najmniej \displaystyle r sąsiadów, musi więc mieć sąsiada \displaystyle v_{k+1} poza \displaystyle k -elementowym zbiorem \displaystyle \left\lbrace v_1,v_2,\ldots,v_k \right\rbrace . Skonstruowaliśmy więc ścieżkę \displaystyle v_1\to v_2\to\ldots\to v_k\to v_{k+1} odwiedzającą \displaystyle k+1 wierzchołków. Powtarzając tę czynność tak długo jak \displaystyle k< r , otrzymujemy \displaystyle r -elementową ścieżkę:


\displaystyle v_1\to v_2\to\ldots\to v_r.


Wiemy więc, że ścieżka o możliwie największej długości ma \displaystyle k\geq r wierzchołków. Niech \displaystyle w_1\to w_2\to\ldots\to w_k będzie taką ścieżką. Z jej maksymalności wiemy, że wszyscy sąsiedzi \displaystyle w_k są już na tej ścieżce, bo inaczej można by ją było przedłużyć. Niech więc \displaystyle w_i będzie sąsiadem \displaystyle w_k o najmniejszym indeksie. Ścieżka \displaystyle w_i\to w_{i+1}\to\ldots\to w_k odwiedza \displaystyle r sąsiadów wierzchołka \displaystyle w_k , więc jest długości co najmniej równej \displaystyle r . Wraz z wierzchołkiem \displaystyle w_k tworzy więc cykl:


\displaystyle w_i\to w_{i+1}\to\ldots\to w_k\to w_i


o długości co najmniej \displaystyle r+1 .

Ćwiczenie 7

Niech \displaystyle \mathbf{G} będzie grafem prostym o \displaystyle 2k wierzchołkach, niezawierającym trójkątów. Wykaż, że \displaystyle \mathbf{G} ma co najwyżej \displaystyle k^2 krawędzi i podaj przykład grafu, w którym to górne oszacowanie jest osiągnięte.

Wskazówka

Zastosuj indukcję względem \displaystyle k usuwając z grafu jedną krawędź, jej końce, a także krawędzie incydentne z tymi końcami.

Rozwiązanie

Dowód zostanie przeprowadzony indukcyjnie ze względu na \displaystyle k . Dla \displaystyle k=1 mamy po prostu graf bez krawędzi. Załóżmy więc, że ograniczenie liczby krawędzi zachodzi dla wszystkich grafów o \displaystyle 2k\geq 2 wierzchołkach. Niech teraz graf \displaystyle \mathbf{G} posiada \displaystyle 2k+2 wierzchołków. Jeśli \displaystyle \mathbf{G} nie posiada krawędzi, to nie ma czego dowodzić. Załóżmy więc, że \displaystyle vw\in{\sf E}\!\left(\mathbf{G}\right) . Na mocy założenia indukcyjnego podgraf \displaystyle \mathbf{G}|_{{\sf V}\!\left(\mathbf{G}\right)-\left\lbrace v,w \right\rbrace} posiada co najwyżej \displaystyle k^2 krawędzi. Ponadto, gdyby istniał \displaystyle u\in{\sf V}\!\left(\mathbf{G}\right) sąsiadujący zarazem z \displaystyle v jak i \displaystyle w , to \displaystyle \left\lbrace v,w,u \right\rbrace byłby trójkątem. Tak więc zbiór sąsiadów \displaystyle v jest rozłączny ze zbiorem sąsiadów \displaystyle w . Zbiór krawędzi łączących wierzchołki \displaystyle v oraz \displaystyle w z wierzchołkami \displaystyle {\sf V}\!\left(\mathbf{G}\right)-\left\lbrace v,w \right\rbrace jest więc nie większy niż rozmiar \displaystyle {\sf V}\!\left(\mathbf{G}\right)-\left\lbrace v,w \right\rbrace , czyli ograniczony przez \displaystyle 2k . Zbiór wszystkich krawędzi w \displaystyle \mathbf{G} składa się z:

  • krawędzi grafu \displaystyle \mathbf{G}-\left\lbrace v,w \right\rbrace ,
  • krawędzi łączących wierzchołki \displaystyle v oraz \displaystyle w z wierzchołkami \displaystyle {\sf V}\!\left(\mathbf{G}\right)-\left\lbrace v,w \right\rbrace ,
  • krawędzi \displaystyle vw .

W sumie więc rozmiar zbioru krawędzi grafu \displaystyle \mathbf{G} jest ograniczony przez


\displaystyle \left\vert {\sf E}\!\left(\mathbf{G}\right) \right\vert\leq k^2+2k+1=\left( k+1 \right)^2.




6. Graf Petersena

Ćwiczenie 8

Wskaż jakieś drzewo rozpinające w grafie Petersena z rysunku 6.

Wskazówka

Skorzystaj z definicji drzewa rozpinającego.

Rozwiązanie

<flash>file="Cw grafy petersen tree.swf"|width=250|height=150</flash>

7. Drzewo rozpinające w grafie Petersena

Prykładowe drzewo rozpinające w grafie Petersena zostało przedstawione na rysunku 7.

 

Ćwiczenie 9

Pokaż, że w dowolnym drzewie o co najmniej dwu wierzchołkach, istnieją co najmniej dwa wierzchołki o stopniu równym jeden.

Wskazówka

Policz sumę stopni wszystkich wierzchołków, połącz te sumę z liczba krawędzi i porównaj z zależnością między liczbą krawędzi i wierzchołków w drzewie.

Rozwiązanie

Niech \displaystyle n będzie liczbą wierzchołków drzewa. Drzewo jest grafem spójnym, więc każdy wierzchołek ma stopień co najmniej jeden. Załóżmy, że co najwyżej jeden wierzchołek ma stopień jeden, czyli jest co najmniej \displaystyle n-1 wierzchołków o stopniu równym \displaystyle 2 lub więcej. Sumując teraz stopnie tych wierzchołków i pamiętając, że suma taka to podwojona liczba krawędzi, dostajemy, że liczba krawędzi jest równa co najmniej


\displaystyle \frac{2\left( n-1 \right)+1}{2}=n-\frac{1}{2}.


Przeczy to faktowi, że drzewo o \displaystyle n wierzchołkach ma \displaystyle n-1 krawędzi.

Ćwiczenie 10

Centrum spójnego grafu \displaystyle \mathbf{G} to taki wierzchołek \displaystyle v , dla którego maksymalna odległość pomiędzy \displaystyle v i dowolnym innym wierzchołkiem grafu \displaystyle \mathbf{G} jest możliwie najmniejsza. Udowodnij, że każde drzewo ma albo dokładnie jedno centrum, albo dwa sąsiednie centra.

Wskazówka

Dowód można przeprowadzić przez sukcesywne usuwanie liści, czyli wierzchołków posiadających jedynie jednego sąsiada.

Rozwiązanie

Zauważmy najpierw, że :

  • W drzewie o co najmniej trzech wierzchołkach żaden liść nie może być centrum.

Niech \displaystyle v będzie liściem, oraz \displaystyle w jedynym jego sąsiadem. Ścieżka pomiędzy liściem \displaystyle v , a dowolnym innym wierzchołkiem musi przechodzić przez wierzchołek \displaystyle w . Jeśli tylko w drzewie istnieje jeszcze jakiś wierzchołek \displaystyle u poza \displaystyle v,w , to \displaystyle w leży bliżej \displaystyle u niż \displaystyle v .

  • Gdy \displaystyle x jest wierzchołkiem drzewa, to wierzchołek najbardziej oddalony od \displaystyle x jest liściem.

Rozważmy dowolny wierzchołek \displaystyle y realizujący największą odległość od \displaystyle x i załóżmy, że nie jest on liściem w drzewie \displaystyle \mathbf{T} . Usunięcie \displaystyle y rozspaja drzewo \displaystyle \mathbf{T} na dwa niepuste drzewa \displaystyle \mathbf{T}_1 oraz \displaystyle \mathbf{T}_2 . Bez straty ogólności załóżmy, że \displaystyle x\in \mathbf{T}_1 . Ścieżka w \displaystyle \mathbf{T} z \displaystyle x do dowolnego wierzchołka z \displaystyle \mathbf{T}_2 odwiedza \displaystyle y , tak więc jest dłuższa niż ścieżka pomiędzy \displaystyle x i \displaystyle y . A zatem \displaystyle y nie może być najdalej oddalonym wierzchołkiem od \displaystyle x .

  • Usunięcie liści nie zmienia zbioru centrów w drzewie.

Usunięcie liścia nie zmienia odległości pomiędzy pozostałymi wierzchołkami. Ustalmy wierzchołek \displaystyle v i przez \displaystyle k oznaczmy odległość \displaystyle v od wierzchołków najbardziej oddalonych od \displaystyle v . Usuwając wszystkie liście, usuwamy między innymi najbardziej oddalone wierzchołki od wierzchołka \displaystyle v . W tym zmniejszonym drzewie, parametr \displaystyle k zmienia się więc na \displaystyle k-1 . A zatem, usunięcie wszystkich liści, zmniejsza każdemu wierzchołkowi parametr decydujący o tym, czy jest on centrum drzewa, o jeden . Tym samym centra w drzewie z obciętymi liśćmi to centra w oryginalnym drzewie.

  • Drzewo o co najmniej trzech wierzchołkach posiada wierzchołek nie będący liściem.

Wynika to z faktu, że drzewo, jak każdy inny graf, posiada centrum, które nie może być liściem.

Wyposażeni w te obserwacje, z drzewa \displaystyle \mathbf{T}^0:=\mathbf{T} konstruujemy

sukcesywnie drzewa \displaystyle \mathbf{T}^j usuwając wszystkie liście drzewa \displaystyle \mathbf{T}^{j-1} tak długo, jak długo otrzymane drzewa są niepuste. A zatem ostatnie ma jeden lub dwa (ale wtedy połączone) wierzchołki, które są wobec tego centrami wyjściowego drzewa \displaystyle \mathbf{T}^0=\mathbf{T} .