Matematyka dyskretna 1/Ćwiczenia 13: Grafy II

Grafy II

Ćwiczenie 1

Kostka $k$ -wymiarowa $𝒬_{k}$ jest grafem, którego wierzchołki to ciągi $(a_{1}, a_{2}, \dots, a_{k})$ , gdzie $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ę $k$ -elementowych ciągów złożonych z $0$ i $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 $k$ .

Rozwiązanie

Wierzchołki $V (𝒬_{k})$ odpowiadają ciągom $(a_{1}, a_{2}, \dots, a_{k})$ , gdzie $a_{i} = 0, 1$ . Liczba $k$ -elementowych ciągów liczb z dwuelementowego zbioru wynosi $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 $k$ . Ponieważ każda krawędź ma dwa końce, to liczba wszystkich krawędzi jest równa $\frac{k \cdot 2^{k}}{2} = k \cdot 2^{k - 1}$ .
Najdłuższy cykl w $𝒬_{k}$ jest cyklem przechodzącym przez wszystkie wierzchołki. Wykażemy jego istnienie indukcyjnie ze względu na $k$ , pokazując ścieżkę z wierzchołka $(0, 0, \dots, 0)$ do $(1, 0, \dots, 0)$ , przechodzącą przez wszystkie wierzchołki.

Kostkę $𝒬_{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 $0$ , czyli $(0, a_{2}, \dots, a_{k + 1})$ , a w drugiej wierzchołki odpowiadające ciągom zaczynającym się od $1$ , czyli $(1, a_{2}, \dots, a_{k + 1})$ . Na mocy założenia indukcyjnego otrzymujemy ścieżkę z wierzchołka $(0, 0, 0, \dots, 0)$ do $(0, 1, 0, \dots, 0)$ , przechodzącą przez wszystkie wierzchołki pierwszej kostki. Analogicznie otrzymujemy także ścieżkę z wierzchołka $(1, 0, 0, \dots, 0)$ do $(1, 1, 0, \dots, 0)$ , przechodzącą przez wszystkie wierzchołki drugiej kostki. Po złożeniu obu ścieżek w ścieżkę postaci

\begin{aligned} (0, 0, 0, \dots, 0) \to \dots \to (0, 1, 0, \dots, 0) \to (1, 1, 0, \dots, 0) \to \dots \\ \dots \to (1, 0, 0, \dots, 0) \end{aligned}

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

Ćwiczenie 2

Dla jakich wartości $n$ grafy $𝒦_{n}$ , $𝒦_{n, m}$ , $𝒬_{n}$ są eulerowskie.

Wskazówka

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 $𝒦_{n}$ , każdy wierzchołek ma stopień równy $n - 1$ , więc eulerowskimi są jedynie kliki $𝒦_{2 k + 1}$ o $2 k + 1$ wierzchołkach, gdzie $k = 0, 1, 2, \dots$ .
W pełnym grafie dwudzielnym $𝒦_{n, m}$ wierzchołki mają stopnie równe $n$ lub $m$ . Wsród pełnych grafów dwudzielnych eulerowskie są jedynie grafy $𝒦_{2 k, 2 l}$ dla $k, l = 0, 1, 2, \dots$ .
W kostce $𝒬_{n}$ każdy wierzchołek ma $n$ sąsiadów, więc eulerowskie są kostki $𝒬_{2 k}$ dla $k = 0, 1, 2, \dots$ .

Ć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

Rozwiązanie

Rozwiązanie jest przedstawione na rysunku.

Ćwiczenie 4

Dla jakich wartości $n$ grafy $𝒦_{n}$ , $𝒦_{n, m}$ , $𝒬_{n}$ są hamiltonowskie.

Wskazówka

Wyciągnij wnioski o liczności $V_{1}$ oraz $V_{2}$ z istnienia cyklu Hamiltona w grafie $𝒦_{n, m} = (V_{1} \cup V_{2}, E)$ . W odpowiedzi na pytanie, które kostki posiadają cykl Hamiltona, wróć do ćwiczenia 1.

Rozwiązanie

Każda klika $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 $𝐆 = (V_{1} \cup V_{2}, E)$ dowolna ścieżka ma na przemian wierzchołki ze zbiorów $V_{1}$ oraz $V_{2}$ , tzn. ścieżka ma postać

v_{1} \to v_{2} \to v_{3} \to \dots v_{k} \to v_{1}

,

gdzie $v_{1}, v_{3}, v_{5}, \dots \in V_{1}$ , zaś $v_{2}, v_{4}, v_{6}, \dots \in V_{2}$ . Jeżeli skojarzymy wierzchołek $v_{1}$ z wierzchołkiem $v_{2}$ , wierzchołek $v_{3}$ z wierzchołkiem $v_{4}$ i w ogólności $v_{2 j + 1}$ z $v_{2 j + 2}$ , to wykorzystamy wszystkie wierzchołki grafu $𝐆$ . Skonstruowane zostało skojarzenie wierzchołków z $V_{1}$ z wierzchołkami z $V_{2}$ wykorzystujące wszystkie wierzchołki, więc $| V_{1} | = | V_{2} |$ . Pełny graf dwudzielny $𝒦_{n, m}$ jest więc hamiltonowski wtedy i tylko wtedy, gdy $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.

Ćwiczenie 5

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

Rozwiązanie

Ćwiczenie 6

Podaj przykład grafu ilustrujący, że warunek $\deg v \geq n / 2$ występujący w Twierdzeniu Diraca 13.5 nie może być zastąpiony warunkiem $\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 $v, w$ takie, że $\deg v + \deg w = n - 1$ .

Rozwiązanie

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

Ćwiczenie 7

Wykaż, że $n$ elementowy $𝐆$ jest hamiltonowski jeśli tylko ma przynajmniej $(n - 1) (n - 2) / 2 + 2$ krawędzi. Podaj przykład grafu niehamiltonowskiego z $n$ wierzchołkami i $(n - 1) (n - 2) / 2 + 1$ krawędziami.

Wskazówka

Rozwiązanie

Niech $u$ i $v$ będą niesąsiednimi wierzchołkami grafu $𝐆$ . Dopełnienie grafu $𝐆$ posiada co najwyżej

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

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

$(2 n - 3) - (n - 3) = n$

Wierzchołki $u$ i $v$ nie sąsiadują ze sobą, więc zbiory incydentnych krawędzi są rozłączne, co w konsekwencji daje że

$d e g u + d e g v \geq n$

Na mocy więc Twierdzenia Ore'a (patrz tw. 13.4) otrzymujemy, że $𝐆$ jest hamiltonowski.

Wartość $(n - 1) (n - 2) / 2 + 2$ jest najmniejszą taką liczbą, że każdy graf o $n$ wierzchołkach i co najmniej tylu krawędziach jest hamiltonowski. Graf o $n = 5$ wierzchołkach i $(n - 1) (n - 2) / 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 $T = (V, E)$ wybierz dowolny wierzchołek $v \in V$ i zdefiniuj odpowiedni podział $V = V_{1} \cup V_{2}$ korzystając z parzystości odległości od $v$ . Kiedy pełny graf dwudzielny nie ma cykli?

Rozwiązanie

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

są oddalone od $v$ o odległość będącą liczbą parzystą - wraz z $v$ będą tworzyć zbiór $V_{1}$ ,
są oddalone od $v$ o odległość będącą liczbą nieparzystą - te z kolei będą składać się na zbiór $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 $w$ od wierzchołka $v$ jest jedyną ścieżką pomiędzy $v$ a $w$ . Niech $u x \in E$ dla wierzchołków $u, x \in V_{i}$ . Ścieżka

v \to \dots \to u \to x

,

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

v \to \dots \to u

,

co przeczy temu, że $u$ oraz $v$ są razem w jednym zbiorze $V_{i}$ .

Drzewo jest pełnym grafem dwudzielnym wtedy i tylko wtedy gdy jest gwiazdą. Istotnie, gwiazda o $n$ liściach jest pełnym grafem dwudzielnym $𝒦_{1, n}$ . Z drugiej strony załóżmy, że drzewo $𝐓 = (V_{1} \cup V_{2}, E)$ jest pełnym grafem dwudzielnym, ale nie jest gwiazdą, czyli zawiera ścieżkę o długości $3$ , np.:

u \to v \to w \to x

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

u \to v \to w \to x \to u

,

co przeczy temu, że $𝐓$ jest drzewem.

Ćwiczenie 9

Udowodnij wierzchołkową wersję Twierdzenia Mengera.

Wskazówka

Rozwiązanie

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

Dowód przeprowadzimy indukcyjnie ze względu na liczbę wierzchołków w grafie $𝐆$ rozważając dwa przypadki.

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

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

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

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

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

Możemy wtedy założyć, że $𝐆$ poza $w, u$ zawiera jedynie wierzchołki należące do któregoś zbioru rozdzielającego $w, u$ o liczności $k$ . Gdyby tak nie było i istniałby jakiś inny wierzchołek $v$ , to moglibyśmy $v$ usunąć i, na mocy założenia indukcyjnego, otrzymać natychmiast $k$ rozłącznych dróg łączących $w, u$ . Tak wiec pozostały nam jedynie te wierzchołki, które są w minimalnych zbiorach rozdzielających $w, u$ . To zaś, zgodnie z założeniem przypadku 2 oznacza, że każdy wierzchołek jest sąsiedni z $w$ lub z $u$ . W ten sposób drugi przypadek sprowadziliśmy do sytuacji, w której każda ścieżka z $w$ do $u$ ma co najwyżej dwie krawędzie. Wśród takich ścieżek nietrudno jest już wskazać $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 $𝐆 = (V_{1} \cup V_{2}, E)$ , oraz funkcji $Φ (A)$ , która zwraca zbiór wierzchołków z $V_{2}$ sąsiednich z przynajmniej jednym wierzchołkiem w $A \subseteq V_{1}$ twierdzenie Hall'a (patrz tw. 13.7) mówi, że:

Pełne skojarzenie $V_{1}$ z $V_{2}$ istnieje wtedy i tylko wtedy, gdy $| A | \leq | Φ (A) |$ , dla każdego podzbioru $A$ zbioru $V_{1}$ .

$\Rightarrow$ Implikacja ta wynika natychmiast z faktu, że jeśli w pełnym skojarzeniu $V_{1}$ z $V_{2}$ , w $Φ (A)$ jest $| A |$ wierzchołków skojarzonych z wierzchołkami z $A$ , co w szczególności implikuje, że $| A | \leq | Φ (A) |$ .

$\Leftarrow$ Do grafu dwudzielnego $𝐆 = (V_{1} \cup V_{2}, E)$ dołóżmy dwa wierzchołki $v_{1}$ oraz $v_{2}$ łącząc $v_{1}$ ze wszystkimi wierzchołkami z $V_{1}$ , a $v_{2}$ ze wszystkimi wierzchołkami z $V_{2}$ . Rozważmy dowolny zbiór $S \subseteq V_{1} \cup V_{2}$ o $| V_{1} | - 1$ wierzchołkach. Na mocy założenia otrzymujemy, że zbiór wierzchołków z $V_{2}$ sąsiadujących z wierzchołkami $V_{1} - S$ jest co najmniej tak duży, jak $V_{1} - S$ , czyli

| V_{1} - S | \leq | Φ (V_{1} - S) |

Ponieważ $| S | < | V_{1} |$ , to $| V_{2} \cap S | < | V_{1} - S | \leq | Φ (V_{1} - S) |$ , a zatem $Φ (V_{1} - S) - S \neq \emptyset$ , czyli $Φ (V_{1} - S) \subseteq̸ S$ . Istnieją więc sąsiednie wierzchołki $u_{1} \in V_{1} - S$ oraz $u_{2} \in Φ (V_{1} - S) - S$ . Teraz, ścieżka postaci

v_{1} \to u_{1} \to u_{2} \to v_{2}

świadczy więc o tym, że $S$ nie był w stanie rozdzielić wierzchołka $v_{1}$ od $v_{2}$ . Na mocy wierzchołkowej wersji twierdzenia Mangera (patrz ćw. 9), istnieje $| V_{1} |$ rozłącznych wierzchołkowo ścieżek łączących $v_{1}$ z $v_{2}$ . Każda taka ścieżka musi być postaci

v_{1} \to w_{1} \to w_{2} \to v_{2}

,

gdzie $w_{1} \in V_{1}$ oraz $w_{2} \in V_{2}$ . Istotnie ścieżek tych jest dokładnie $| V_{1} |$ , więc każda z nich przechodzi dokładnie raz przez $V_{1}$ i dokładnie raz przez $V_{2}$ . Usuwając teraz z każdej takiej ścieżki wierzchołki $v_{1}, v_{2}$ , otrzymujemy pełne skojarzenie $V_{1}$ z $V_{2}$ .

Matematyka dyskretna 1/Ćwiczenia 13: Grafy II

Grafy II

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia