Matematyka dyskretna 1/Ćwiczenia 13: Grafy II

From Studia Informatyczne

Grafy II

Ćwiczenie 1

Kostka \displaystyle k -wymiarowa \displaystyle \mathcal{Q}_{k} jest grafem, którego wierzchołki to ciągi \displaystyle \left( a_1,a_2,\ldots,a_k \right) , gdzie \displaystyle a_i=0,1 , a krawędzie łączą te ciągi, które różnią się tylko na jednej pozycji. Oblicz liczbę wierzchołków, krawędzi oraz rozmiar najdłuższego cyklu.

Wskazówka

Aby znaleźć liczbę wierzchołków policz liczbę \displaystyle k -elementowych ciągów złożonych z \displaystyle 0 i \displaystyle 1 . Przy znalezieniu liczby krawędzi przydatna będzie znajomość stopnia wierzchołków. Najdłuższy cykl, to cykl przechodzący przez wszystkie wierzchołki. Konstrukcję takiego cyklu przeprowadź indukcyjnie ze względu na \displaystyle k .

Rozwiązanie

<flash>file=Cw grafy 4kostka.swf|width=350|height=250</flash>

Cykl \displaystyle 16 -elementowy w kostce \displaystyle \mathcal{Q}_{4}
  • Wierzchołki \displaystyle {\sf V}\!\left(\mathcal{Q}_{k}\right) odpowiadają ciągom \displaystyle \left( a_1,a_2,\ldots,a_k \right) , gdzie \displaystyle a_i=0,1. Liczba \displaystyle k -elementowych ciągów liczb z dwuelementowego zbioru wynosi \displaystyle 2^k .
  • Z kolei krawędzie łączą te ciągi, które różnią się na jednej tylko pozycji. Ciąg ze względu na konkretną pozycję jest sąsiedni z dokładnie jednym ciągiem. Stopień dowolnego wierzchołka równy jest więc \displaystyle k. Ponieważ każda krawędź ma dwa końce, to liczba wszystkich krawędzi jest równa \displaystyle \frac{k\cdot 2^k}{2}=k\cdot 2^{k-1} .
  • Najdłuższy cykl w \displaystyle \mathcal{Q}_{k} jest cyklem przechodzącym przez wszystkie wierzchołki. Wykażemy jego istnienie indukcyjnie ze względu na \displaystyle k , pokazując ścieżkę z wierzchołka \displaystyle \left( 0,0,\ldots,0 \right) do \displaystyle \left( 1,0,\ldots,0 \right) , przechodzącą przez wszystkie wierzchołki.

Kostkę \displaystyle \mathcal{Q}_{k+1} można rozłożyć na dwie kostki w ten sposób, że w pierwszej znajdą się wszystkie wierzchołki odpowiadające ciągom zaczynającym się od \displaystyle 0 , czyli \displaystyle \left( 0,a_2,\ldots,a_{k+1} \right) , a w drugiej wierzchołki odpowiadające ciągom zaczynającym się od \displaystyle 1 , czyli \displaystyle \left( 1,a_2,\ldots,a_{k+1} \right) . Na mocy założenia indukcyjnego otrzymujemy ścieżkę z wierzchołka \displaystyle \left( 0,0,0,\ldots,0 \right) do \displaystyle \left( 0,1,0,\ldots,0 \right) , przechodzącą przez wszystkie wierzchołki pierwszej kostki. Analogicznie otrzymujemy także ścieżkę z wierzchołka \displaystyle \left( 1,0,0,\ldots,0 \right) do \displaystyle \left( 1,1,0,\ldots,0 \right) , przechodzącą przez wszystkie wierzchołki drugiej kostki. Po złożeniu obu ścieżek w ścieżkę postaci


\displaystyle \aligned \left( 0,0,0,\ldots,0 \right)\to\ldots\to\left( 0,1,0,\ldots,0 \right)\to\left( 1,1,0,\ldots,0 \right)\to\ldots&&\\ \ldots\to\left( 1,0,0,\ldots,0 \right)&& \endaligned


otrzymujemy szukaną ścieżkę. W konsekwencji otrzymujemy, że najdłuższa ścieżka \displaystyle \mathcal{Q}_{k} składa się ze wszystkich \displaystyle 2^k wierzchołków.

Ćwiczenie 2

Dla jakich wartości \displaystyle n grafy \displaystyle \mathcal{K}_{n} , \displaystyle \mathcal{K}_{n,m} , \displaystyle \mathcal{Q}_{n} są eulerowskie.

Wskazówka

Skorzystaj z twierdzenia 13.1.

Rozwiązanie

Korzystając z twierdzenia 13.1 otrzymujemy warunek, że każdy graf eulerowski musi posiadać jedynie wierzchołki o stopniu parzystym.

  • W klice \displaystyle \mathcal{K}_{n} , każdy wierzchołek ma stopień równy \displaystyle n-1 , więc eulerowskimi są jedynie kliki \displaystyle \mathcal{K}_{2k+1} o \displaystyle 2k+1 wierzchołkach, gdzie \displaystyle k=0,1,2,\ldots .
  • W pełnym grafie dwudzielnym \displaystyle \mathcal{K}_{n,m} wierzchołki mają stopnie równe \displaystyle n lub \displaystyle m . Wsród pełnych grafów dwudzielnych eulerowskie są jedynie grafy \displaystyle \mathcal{K}_{2k,2l} dla \displaystyle k,l=0,1,2,\ldots .
  • W kostce \displaystyle \mathcal{Q}_{n} każdy wierzchołek ma \displaystyle n sąsiadów, więc eulerowskie są kostki \displaystyle \mathcal{Q}_{2k} dla \displaystyle k=0,1,2,\ldots .

Ćwiczenie 3

Przedstaw cztery pięciowierzchołkowe grafy -- kolejno graf który:

  • nie jest hamiltonowski i nie jest eulerowski
  • nie jest hamiltonowski, ale jest eulerowski
  • jest hamiltonowski i nie jest eulerowski
  • jest hamiltonowski i eulerowski.

Wskazówka

Skorzystaj z definicji grafu eulerowskiego i hamiltonowskiego.

Rozwiązanie

<flash>file=Cw grafy eul ham.swf|width=250|height=200</flash>

Przykłady na: graf niehamiltonowski i nieeulerowski(a),

graf niehamiltonowski ale eulerowskim (b), graf hamiltonowski lecz nieeulerowski (c),

oraz graf eulerowski będący zarazem hamiltonowskim (d)

Rozwiązanie jest przedstawione na rysunku.

Ćwiczenie 4

Dla jakich wartości \displaystyle n grafy \displaystyle \mathcal{K}_{n} , \displaystyle \mathcal{K}_{n,m} , \displaystyle \mathcal{Q}_{n} są hamiltonowskie.

Wskazówka

Wyciągnij wnioski o liczności \displaystyle V_1 oraz \displaystyle V_2 z istnienia cyklu Hamiltona w grafie \displaystyle \mathcal{K}_{n,m}=\left( V_1\cup V_2,E \right) . W odpowiedzi na pytanie, które kostki posiadają cykl Hamiltona, wróć do ćwiczenia 1.

Rozwiązanie

  • Każda klika \displaystyle n\geq 3 elementowa jest hamiltonowska, ponieważ w klice dowolne dwa elementy są połączone krawędzią,

dowolny ciąg wszystkich elementów tworzy więc cykl.

  • W pełnym grafie dwudzielnym \displaystyle \mathbf{G}=\left( V_1\cup V_2,E \right) dowolna ścieżka ma na przemian wierzchołki ze zbiorów \displaystyle V_1 oraz \displaystyle V_2, tzn. ścieżka ma postać


\displaystyle v_1\to v_2\to v_3\to \ldots v_k\to v_1,


gdzie \displaystyle v_1, v_3, v_5,\ldots\in V_1 , zaś \displaystyle v_2, v_4, v_6,\ldots\in V_2 . Jeżeli skojarzymy wierzchołek \displaystyle v_1 z wierzchołkiem \displaystyle v_2 , wierzchołek \displaystyle v_3 z wierzchołkiem \displaystyle v_4 i w ogólności \displaystyle v_{2j+1} z \displaystyle v_{2j+2} , to wykorzystamy wszystkie wierzchołki grafu \displaystyle \mathbf{G} . Skonstruowane zostało skojarzenie wierzchołków z \displaystyle V_1 z wierzchołkami z \displaystyle V_2 wykorzystujące wszystkie wierzchołki, więc \displaystyle \left\vert V_1 \right\vert=\left\vert V_2 \right\vert . Pełny graf dwudzielny \displaystyle \mathcal{K}_{n,m} jest więc hamiltonowski wtedy i tylko wtedy, gdy \displaystyle n=m .

  • Ścieżka o maksymalnej długości znaleziona w ćwiczeniu 1 jest ścieżką Hamiltona. Otrzymujemy więc wniosek, że każda kostka jest grafem hamiltonowskim.



Graf Petersena

Ćwiczenie 5

Czy graf Petersena (patrz rysunek) ma ścieżkę Hamiltona.

Rozwiązanie

<flash>file=Cw grafy petersen ham.swf|width=150|height=150</flash>

Ścieżka Hamiltona w grafie Petersena

Ścieżka Hamiltona w grafie Petersena została przedstawiona na rysunku.

Ćwiczenie 6

Podaj przykład grafu ilustrujący, że warunek \displaystyle \deg{v}\geq n/2 występujący w Twierdzeniu Diraca 13.5 nie może być zastąpiony warunkiem \displaystyle \deg{v}\geq n/2-1 .

Wskazówka

Przeanalizuj dowód twierdzenia Ore'a (patrz tw. 13.4). W którym miejscu załamałby się ten dowód, gdyby istniały wierzchołki \displaystyle v,w takie, że \displaystyle \deg{v}+\deg{w}= n-1 .

Rozwiązanie

<flash>file=Cw grafy kontr dirac.swf|width=250|height=100</flash>

Kontrprzykład do zmodyfikowanego twierdzenia Diraca

Jeżeli w wypowiedzi Twierdzenia Diraca, warunek \displaystyle \deg{v}\geq n/2 zastąpimy warunkiem \displaystyle \deg{v}\geq n/2-1 , to tak zmodyfikowane zdanie ma kontrprzykład przedstawiony na rysunku.

Ćwiczenie 7

Wykaż, że \displaystyle n elementowy \displaystyle \mathbf{G} jest hamiltonowski jeśli tylko ma przynajmniej \displaystyle \left( n-1 \right)\left( n-2 \right)/2+2 krawędzi. Podaj przykład grafu niehamiltonowskiego z \displaystyle n wierzchołkami i \displaystyle \left( n-1 \right)\left( n-2 \right)/2+1 krawędziami.

Wskazówka

Skorzystaj z Twierdzenia Ore'a (patrz tw. 13.4).

Rozwiązanie

<flash>file=Cw grafy kontr moc v.swf|width=250|height=250</flash>

Graf o \displaystyle 5 wierzchołkach i \displaystyle 7 krawędziach, ale bez cyklu Hamiltona

Niech \displaystyle u i \displaystyle v będą niesąsiednimi wierzchołkami grafu \displaystyle \mathbf{G} . Dopełnienie grafu \displaystyle \mathbf{G} posiada co najwyżej

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

krawędzi, więc \displaystyle u i \displaystyle v

mogą być incydentne w sumie z co najwyżej \displaystyle n-3 krawędziami w \displaystyle \overline{\mathbf{G}} . Liczba krawędzi incydentnych z \displaystyle u lub \displaystyle v w grafie pełnym \displaystyle \left( {\sf V}\!\left(\mathbf{G}\right),\mathscr{P}_{2}\!\left( {\sf V}\!\left(\mathbf{G}\right) \right) \right) , jest równa \displaystyle 2n-3 . Dopełnienie grafu \displaystyle \mathbf{G} jest to graf postaci \displaystyle \overline{\mathbf{G}}=\left( {\sf V}\!\left(\mathbf{G}\right),\mathscr{P}_{2}\!\left( {\sf V}\!\left(\mathbf{G}\right) \right)-{\sf E}\!\left(\mathbf{G}\right) \right) , więc liczba krawędzi incydentnych z \displaystyle u lub \displaystyle v to co najmniej

\displaystyle \left( 2n-3 \right)-\left( n-3 \right)=n.

Wierzchołki \displaystyle u i \displaystyle v nie sąsiadują ze sobą,

więc zbiory incydentnych krawędzi są rozłączne, co w konsekwencji daje że

\displaystyle {\sf deg}\ u+{\sf deg}\ v\geq n.

Na mocy więc Twierdzenia Ore'a (patrz tw. 13.4) otrzymujemy, że \displaystyle \mathbf{G} jest hamiltonowski.

Wartość \displaystyle \left( n-1 \right)\left( n-2 \right)/2+2 jest najmniejszą taką liczbą, że każdy graf o \displaystyle n wierzchołkach i co najmniej tylu krawędziach jest hamiltonowski. Graf o \displaystyle n=5 wierzchołkach i \displaystyle \left( n-1 \right)\left( n-2 \right)/2+1=7 krawędziach, który nie jest hamiltonowski jest przedstawiony na rysunku 6.

Ćwiczenie 8

Wykaż, że każde drzewo jest grafem dwudzielnym. Które drzewa są pełnymi grafami dwudzielnymi?

Wskazówka

Dla drzewa \displaystyle T=\left( V,E \right) wybierz dowolny wierzchołek \displaystyle v\in V i zdefiniuj odpowiedni podział \displaystyle V=V_1\cup V_2 korzystając z parzystości odległości od \displaystyle v . Kiedy pełny graf dwudzielny nie ma cykli?

Rozwiązanie

Niech \displaystyle T=\left( V,E \right) będzie drzewem a \displaystyle v\in V dowolnie wybranym jego wierzchołkiem. Podzielimy zbiór \displaystyle V na wierzchołki, które:

  • są oddalone od \displaystyle v o odległość będącą liczbą parzystą - wraz z \displaystyle v będą tworzyć zbiór \displaystyle V_1 ,
  • są oddalone od \displaystyle v o odległość będącą liczbą nieparzystą - te z kolei będą składać się na zbiór \displaystyle V_2 .

W drzewie pomiędzy dowolnymi wierzchołkami istnieje dokładnie jedna ścieżka, tak więc ścieżka świadcząca o odległości wierzchołka \displaystyle w od wierzchołka \displaystyle v jest jedyną ścieżką pomiędzy \displaystyle v a \displaystyle w . Niech \displaystyle ux\in E dla wierzchołków \displaystyle u,x\in V_i. Ścieżka


\displaystyle v\to\ldots\to u\to x,


ma długość innej parzystości niż ścieżka


\displaystyle v\to\ldots\to u,


co przeczy temu, że \displaystyle u oraz \displaystyle v są razem w jednym zbiorze \displaystyle V_i .

Drzewo jest pełnym grafem dwudzielnym wtedy i tylko wtedy gdy jest gwiazdą.

Istotnie, gwiazda o \displaystyle n liściach jest pełnym grafem dwudzielnym \displaystyle \mathcal{K}_{1,n} . Z drugiej strony załóżmy, że drzewo \displaystyle \mathbf{T}=\left( V_1\cup V_2, E \right) jest pełnym grafem dwudzielnym, ale nie jest gwiazdą, czyli zawiera ścieżkę o długości \displaystyle 3 , np.:


\displaystyle u\to v\to w\to x.


Bez straty ogólności załóżmy, że \displaystyle u\in V_1 , tak więc \displaystyle v,x\in V_2 oraz \displaystyle w\in V_1 . W pełnym grafie dwudzielnym istnieje więc krawędź łącząca wierzchołek \displaystyle x\in V_2 z wierzchołkiem \displaystyle u\in V_1 . Mam więc cykl postaci:


\displaystyle u\to v\to w\to x\to u,


co przeczy temu, że \displaystyle \mathbf{T} jest drzewem.

Ćwiczenie 9

Udowodnij wierzchołkową wersję Twierdzenia Mengera.

Wskazówka

Naśladuj dowód Twierdzenia 13.8.

Rozwiązanie

Niech \displaystyle w , \displaystyle u będą dwoma różnymi i niesąsiednimi wierzchołkami spójnego grafu \displaystyle \mathbf{G} = \left( V,E \right) . Przez \displaystyle k oznaczmy najmniejszą możliwą liczność zbioru wierzchołków rozdzielających \displaystyle w , \displaystyle u . Oczywiście każda droga łącząca \displaystyle w z \displaystyle u musi przejść przez każdy zbiór rozdzielający. A zatem dróg wierzchołkowo rozłącznych łączących \displaystyle w z \displaystyle u nie może być więcej niż \displaystyle k . Tak więc wystarczy pokazać, że istnieje \displaystyle k rozłącznych wierzchołkowo dróg z \displaystyle w do \displaystyle u .

Dowód przeprowadzimy indukcyjnie ze względu na liczbę wierzchołków w grafie \displaystyle \mathbf{G} rozważając dwa przypadki.

1. Pewien zbiór rozdzielający \displaystyle X mocy \displaystyle k ma wierzchołek niesąsiedni z \displaystyle w oraz ma wierzchołek (być może inny) niesąsiedni z \displaystyle u .

Graf \displaystyle \mathbf{G} , po usunięciu wszystkich wierzchołków z \displaystyle X , podzieli się na dwie spójne składowe \displaystyle W oraz \displaystyle U , do których należą odpowiednio \displaystyle w i \displaystyle u .

Przez \displaystyle W' oznaczmy graf powstały z grafu \displaystyle \mathbf{G} poprzez ściągnięcie \displaystyle U w jeden wierzchołek \displaystyle u' . Wtedy \displaystyle u' jest połączony z tymi wierzchołkami \displaystyle t\in X , z którymi połączony był jakiś wierzchołek \displaystyle s\in U . Krawędzie łączące wierzchołki wewnątrz \displaystyle W pozostały niezmienione. Graf \displaystyle U' definiujemy analogicznie, poprzez ściągnięcie zbioru \displaystyle W do wierzchołka \displaystyle w' .

W grafie \displaystyle W' minimalny zbiór rozdzielający wierzchołki \displaystyle w, u' posiada \displaystyle k wierzchołków. Ponieważ założyliśmy, ze w \displaystyle X istnieje wierzchołek niesąsiedni z \displaystyle u , to \displaystyle U ma co najmniej dwa wierzchołki, a zatem graf \displaystyle W' ma mniej wierzchołków niż \displaystyle \mathbf{G} . Tak wiec możemy skorzystać z założenia indukcyjnego otrzymując \displaystyle k rozłącznych wierzchołkowo dróg łączących \displaystyle w z \displaystyle u' w \displaystyle W' . Analogicznie w grafie \displaystyle U otrzymujemy \displaystyle k rozłącznych wierzchołkowo dróg łączących \displaystyle w' z \displaystyle u . Sklejając odpowiednio drogi z obu tych rodzin otrzymujemy \displaystyle k rozłącznych ścieżek łączących \displaystyle w z \displaystyle u w grafie \displaystyle \mathbf{G} .

2. W każdym zbiorze rozdzielającym \displaystyle X o mocy \displaystyle k , każdy wierzchołek jest sąsiedni do \displaystyle w lub do \displaystyle u .

Możemy wtedy założyć, że \displaystyle \mathbf{G} poza \displaystyle w,u zawiera jedynie wierzchołki należące do któregoś zbioru rozdzielającego \displaystyle w, u o liczności \displaystyle k . Gdyby tak nie było i istniałby jakiś inny wierzchołek \displaystyle v , to moglibyśmy \displaystyle v usunąć i, na mocy założenia indukcyjnego, otrzymać natychmiast \displaystyle k rozłącznych dróg łączących \displaystyle w, u . Tak wiec pozostały nam jedynie te wierzchołki, które są w minimalnych zbiorach rozdzielających \displaystyle w, u . To zaś, zgodnie z założeniem przypadku 2 oznacza, że każdy wierzchołek jest sąsiedni z \displaystyle w lub z \displaystyle u . W ten sposób drugi przypadek sprowadziliśmy do sytuacji, w której każda ścieżka z \displaystyle w do \displaystyle u ma co najwyżej dwie krawędzie. Wśród takich ścieżek nietrudno jest już wskazać \displaystyle k rozłącznych wierzchołkowo.

Ćwiczenie 10

Korzystając z Twierdzenia Mengera udowodnij Twierdzenie Halla o skojarzeniach w grafach dwudzielnych.

Rozwiązanie

Dla grafu dwudzielnego \displaystyle \mathbf{G}=\left( V_1\cup V_2,E \right) , oraz funkcji \displaystyle \Phi\!\left(A\right) , która zwraca zbiór wierzchołków z \displaystyle V_2 sąsiednich z przynajmniej jednym wierzchołkiem w \displaystyle A\subseteq V_1 twierdzenie Hall'a (patrz tw. 13.7) mówi, że:

Pełne skojarzenie \displaystyle V_1 z \displaystyle V_2 istnieje wtedy i tylko wtedy, gdy \displaystyle \left\vert A \right\vert \leq\left\vert \Phi\!\left(A\right) \right\vert , dla każdego podzbioru \displaystyle A zbioru \displaystyle V_1 .

\displaystyle \Rightarrow Implikacja ta wynika natychmiast z faktu, że jeśli w pełnym skojarzeniu \displaystyle V_1 z \displaystyle V_2 , w \displaystyle \Phi\!\left(A\right) jest \displaystyle \left\vert A \right\vert wierzchołków skojarzonych z wierzchołkami z \displaystyle A , co w szczególności implikuje, że \displaystyle \left\vert A \right\vert \leq\left\vert \Phi\!\left(A\right) \right\vert .

\displaystyle \Leftarrow Do grafu dwudzielnego \displaystyle \mathbf{G}=\left( V_1\cup V_2,E \right)

dołóżmy dwa wierzchołki \displaystyle v_1 oraz \displaystyle v_2 łącząc \displaystyle v_1 ze wszystkimi wierzchołkami z \displaystyle V_1 , a \displaystyle v_2 ze wszystkimi wierzchołkami z \displaystyle V_2 . Rozważmy dowolny zbiór \displaystyle S\subseteq V_1\cup V_2 o \displaystyle \left\vert V_1 \right\vert-1 wierzchołkach. Na mocy założenia otrzymujemy, że zbiór wierzchołków z \displaystyle V_2 sąsiadujących z wierzchołkami \displaystyle V_1- S jest co najmniej tak duży, jak \displaystyle V_1- S , czyli


\displaystyle \left\vert V_1- S \right\vert \leq\left\vert \Phi\!\left(V_1- S\right) \right\vert.


Ponieważ \displaystyle \left\vert S \right\vert<\left\vert V_1 \right\vert , to \displaystyle \left\vert V_2\cap S \right\vert < \left\vert V_1- S \right\vert \leq\left\vert \Phi\!\left(V_1- S\right) \right\vert , a zatem \displaystyle \Phi\!\left(V_1- S\right)- S\neq\emptyset , czyli \displaystyle \Phi\!\left(V_1- S\right)\not\subseteq S . Istnieją więc sąsiednie wierzchołki \displaystyle u_1\in V_1- S oraz \displaystyle u_2\in\Phi\!\left(V_1- S\right)- S . Teraz, ścieżka postaci


\displaystyle v_1\to u_1\to u_2\to v_2


świadczy więc o tym, że \displaystyle S nie był w stanie rozdzielić wierzchołka \displaystyle v_1 od \displaystyle v_2 . Na mocy wierzchołkowej wersji twierdzenia Mangera (patrz ćw. 9), istnieje \displaystyle \left\vert V_1 \right\vert rozłącznych wierzchołkowo ścieżek łączących \displaystyle v_1 z \displaystyle v_2 . Każda taka ścieżka musi być postaci


\displaystyle v_1\to w_1\to w_2\to v_2,


gdzie \displaystyle w_1\in V_1 oraz \displaystyle w_2\in V_2 . Istotnie ścieżek tych jest dokładnie \displaystyle \left\vert V_1 \right\vert , więc każda z nich przechodzi dokładnie raz przez \displaystyle V_1 i dokładnie raz przez \displaystyle V_2 . Usuwając teraz z każdej takiej ścieżki wierzchołki \displaystyle v_1,v_2 , otrzymujemy pełne skojarzenie \displaystyle V_1 z \displaystyle V_2 .