Matematyka dyskretna 1/Ćwiczenia 13: Grafy II

Z Studia Informatyczne
< Matematyka dyskretna 1
Wersja z dnia 15:04, 3 paź 2021 autorstwa Luki (dyskusja | edycje) (Zastępowanie tekstu - "<div class="thumb t(.*)"><div style="width:(.*)px;"> <flash>file=(.*)\.swf\|width=(.*)\|height=(.*)<\/flash> <div\.thumbcaption>(.*)<\/div><\/div> <\/div>" na "$4x$5px|thumb|$1|$6")
(różn.) ← poprzednia wersja | przejdź do aktualnej wersji (różn.) | następna wersja → (różn.)
Przejdź do nawigacjiPrzejdź do wyszukiwania

Grafy II

Ćwiczenie 1

Kostka -wymiarowa jest grafem, którego wierzchołki to ciągi , gdzie , 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
Rozwiązanie

Ćwiczenie 2

Dla jakich wartości grafy , , są eulerowskie.

Wskazówka
Rozwiązanie

Ć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 grafy , , są hamiltonowskie.

Wskazówka
Rozwiązanie
Graf Petersena

Ćwiczenie 5

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

Rozwiązanie

Ćwiczenie 6

Podaj przykład grafu ilustrujący, że warunek występujący w Twierdzeniu Diraca 13.5 nie może być zastąpiony warunkiem .

Wskazówka
Rozwiązanie

Ćwiczenie 7

Wykaż, że elementowy jest hamiltonowski jeśli tylko ma przynajmniej krawędzi. Podaj przykład grafu niehamiltonowskiego z wierzchołkami i krawędziami.

Wskazówka
Rozwiązanie

Ćwiczenie 8

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

Wskazówka
Rozwiązanie

Ćwiczenie 9

Udowodnij wierzchołkową wersję Twierdzenia Mengera.

Wskazówka
Rozwiązanie

Ćwiczenie 10

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

Rozwiązanie