Matematyka dyskretna 1/Ćwiczenia 12: Grafy

Grafy I

1. Grafy ${\mathbf{𝐆}}_1$ oraz ${\mathbf{𝐆}}_2$

Ćwiczenie 1

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

Wskazówka

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

Rozwiązanie

2. Grafy ${\mathbf{𝐆}}_1\cup {\mathbf{𝐆}}_2$

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

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

4. Graf $\mathbf{𝐆}$

Ćwiczenie 2

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

$v_i\triangleq v_j$ w.t.w. $|i-j|$ jest wielokrotnością $4.$

Wskazówka

Skorzystać z definicji ilorazu podanego na wykładzie.

Rozwiązanie

5. Graf $\mathbf{𝐆}/\triangleq$

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

Ćwiczenie 3

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

Wskazówka

Skorzystaj z Zasady Szufladkowej Dirichleta.

Rozwiązanie

Niech $\mathbf{𝐆}$ ma $n\ge 2$ wierzchołków. Wierzchołek $v\in \mathsf{V}\left(\mathbf{𝐆}\right)$ nie może mieć więcej niż $|\mathsf{V}\left(\mathbf{𝐆}\right)-\left\{v\right\}|=n-1$ sąsiadów. Stopień dowolnego wierzchołka z $\mathsf{V}\left(\mathbf{𝐆}\right)$ leży więc w zbiorze $\{0,1,2,\dots ,n-1\}$ . Jeśli jakiś wierzchołek ma stopień $0$ , czyli jest izolowany, to każdy inny wierzchołek może mieć co najwyżej $n-2$ sąsiadów. Z kolei gdyby istniał punkt $w$ o stopniu równym $n-1$ , to każdy wierzchołek ze zbioru $\mathsf{V}\left(\mathbf{𝐆}\right)-\left\{w\right\}$ byłby sąsiadem $w$ , więc nie mogłby mieć stopnia równego $0$ . Zbiór $S$ stopni wierzchołków grafu $\mathbf{𝐆}$ zawiera się więc albo w zbiorze $\{0,1,2,\dots ,n-2\}$ , albo w $\{1,2,3,\dots ,n-1\}$ , więc $S$ jest co najwyżej $(n-1)$ -elementowy. Wszystkich wierzchołków jest $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 $3$ , $4$ , lub $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 $\mathbf{𝐆}=(V,E)$ to graf $\overline{\mathbf{𝐆}}=(V,{{𝒫}}_2\left(V\right)-E)$ . Przedstaw dopełnienie grafu pełnego ${{𝒦}}_n$ oraz dwudzielnego grafu pełnego ${{𝒦}}_{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. $\overline{{{𝒦}}_n}={{𝒜}}_n$ . Na odwrót dopełnienie grafu pustego jest grafem pełnym: $\overline{{{𝒜}}_n}={{𝒦}}_n$ . Z kolei dopełnienie pełnego grafu dwudzielnego ${{𝒦}}_{n,n}$ jest rozłączną sumą dwóch klik ${{𝒦}}_m\cup {{𝒦}}_n$ .

Cykl piecioelementowy oraz ścieżka czteroelementowa są przykładami grafów izomorficznych ze swoimi dopełnieniami.

Ćwiczenie 6

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

Wskazówka

Spróbuj budować indukcyjnie możliwie długą ścieżkę. Pokaż, że musi mieć co najmniej $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 $k<r$ tzn. $v_1\to v_2\to \dots \to v_k$ . Wierzchołek $v_k$ ma co najmniej $r$ sąsiadów, musi więc mieć sąsiada $v_{k+1}$ poza $k$ -elementowym zbiorem $\{v_1,v_2,\dots ,v_k\}$ . Skonstruowaliśmy więc ścieżkę $v_1\to v_2\to \dots \to v_k\to v_{k+1}$ odwiedzającą $k+1$ wierzchołków. Powtarzając tę czynność tak długo jak $k<r$ , otrzymujemy $r$ -elementową ścieżkę:

$v_1\to v_2\to \dots \to v_r.$

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

$w_i\to w_{i+1}\to \dots \to w_k\to w_i$

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

Ćwiczenie 7

Niech $\mathbf{𝐆}$ będzie grafem prostym o $2k$ wierzchołkach, niezawierającym trójkątów. Wykaż, że $\mathbf{𝐆}$ ma co najwyżej $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 $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 $k$ . Dla $k=1$ mamy po prostu graf bez krawędzi. Załóżmy więc, że ograniczenie liczby krawędzi zachodzi dla wszystkich grafów o $2k\ge 2$ wierzchołkach. Niech teraz graf $\mathbf{𝐆}$ posiada $2k+2$ wierzchołków. Jeśli $\mathbf{𝐆}$ nie posiada krawędzi, to nie ma czego dowodzić. Załóżmy więc, że $vw\in \mathsf{E}\left(\mathbf{𝐆}\right)$ . Na mocy założenia indukcyjnego podgraf $\mathbf{𝐆}{|}_{\mathsf{V}\left(\mathbf{𝐆}\right)-\{v,w\}}$ posiada co najwyżej $k^2$ krawędzi. Ponadto, gdyby istniał $u\in \mathsf{V}\left(\mathbf{𝐆}\right)$ sąsiadujący zarazem z $v$ jak i $w$ , to $\{v,w,u\}$ byłby trójkątem. Tak więc zbiór sąsiadów $v$ jest rozłączny ze zbiorem sąsiadów $w$ . Zbiór krawędzi łączących wierzchołki $v$ oraz $w$ z wierzchołkami $\mathsf{V}\left(\mathbf{𝐆}\right)-\{v,w\}$ jest więc nie większy niż rozmiar $\mathsf{V}\left(\mathbf{𝐆}\right)-\{v,w\}$ , czyli ograniczony przez $2k$ . Zbiór wszystkich krawędzi w $\mathbf{𝐆}$ składa się z:

• krawędzi grafu $\mathbf{𝐆}-\{v,w\}$ ,
• krawędzi łączących wierzchołki $v$ oraz $w$ z wierzchołkami $\mathsf{V}\left(\mathbf{𝐆}\right)-\{v,w\}$ ,
• krawędzi $vw$ .

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

$\left|\mathsf{E}\left(\mathbf{𝐆}\right)\right|\le k^2+2k+1={(k+1)}^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>

<div.thumbcaption>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 $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 $n-1$ wierzchołków o stopniu równym $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

$\frac{2(n-1)+1}{2}=n-\frac{1}{2}.$

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

Ćwiczenie 10

Centrum spójnego grafu $\mathbf{𝐆}$ to taki wierzchołek $v$ , dla którego maksymalna odległość pomiędzy $v$ i dowolnym innym wierzchołkiem grafu $\mathbf{𝐆}$ 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 $v$ będzie liściem, oraz $w$ jedynym jego sąsiadem. Ścieżka pomiędzy liściem $v$ , a dowolnym innym wierzchołkiem musi przechodzić przez wierzchołek $w$ . Jeśli tylko w drzewie istnieje jeszcze jakiś wierzchołek $u$ poza $v,w$ , to $w$ leży bliżej $u$ niż $v$ .

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

Rozważmy dowolny wierzchołek $y$ realizujący największą odległość od $x$ i załóżmy, że nie jest on liściem w drzewie $\mathbf{𝐓}$ . Usunięcie $y$ rozspaja drzewo $\mathbf{𝐓}$ na dwa niepuste drzewa ${\mathbf{𝐓}}_1$ oraz ${\mathbf{𝐓}}_2$ . Bez straty ogólności załóżmy, że $x\in {\mathbf{𝐓}}_1$ . Ścieżka w $\mathbf{𝐓}$ z $x$ do dowolnego wierzchołka z ${\mathbf{𝐓}}_2$ odwiedza $y$ , tak więc jest dłuższa niż ścieżka pomiędzy $x$ i $y$ . A zatem $y$ nie może być najdalej oddalonym wierzchołkiem od $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 $v$ i przez $k$ oznaczmy odległość $v$ od wierzchołków najbardziej oddalonych od $v$ . Usuwając wszystkie liście, usuwamy między innymi najbardziej oddalone wierzchołki od wierzchołka $v$ . W tym zmniejszonym drzewie, parametr $k$ zmienia się więc na $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 ${\mathbf{𝐓}}^0:=\mathbf{𝐓}$ konstruujemy sukcesywnie drzewa ${\mathbf{𝐓}}^j$ usuwając wszystkie liście drzewa ${\mathbf{𝐓}}^{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 ${\mathbf{𝐓}}^0=\mathbf{𝐓}$ .