3545336450

9 Cykle Hamiltona/obchody Eulera

Zadanie 9.1. Udowodnij, że jeśli graf G ma ścieżkę Hamiltona, to dla dowolnego niepustego podzbioru S C V(G) mamy

w(G - 5) < |5| + 1

Zadanie 9.2. Pokaż, że graf Petersena nie ma cyklu Hamiltona.

Zadanie 9.3. W spójnym grafie G wierzchołek v ma trzech sąsiadów stopnia 2. Czy graf ten może mieć cykl Hamiltona.

Zadanie 9.4. Czy każdy graf, który posiada obchód Eulera ma parzystą liczbę krawędzi? Jeśli tak, to podaj uzasadnienie. Jeśli nie, to podaj kontrprzykład.

Zadanie 9.5. Udowodnij, że każdy spójny graf zawiera obchód (domknięty spacer), który przechodzi przez każdą krawędź dokładnie dwa razy. Podaj potrzebne definicje i twierdzenia. Wskazówka: Popatrz na przejście przez krawędź dokładnie dwa razy jak na jej sklonowanie (zdublowanie).

10 Algorytmy grafowe

Zadanie 10.1. Do grafu na poniższym rysunku zastosuj algorytmy przeszukiwania wszerz (BFS) i w głąb (DFS) zaczynając od wierzchołka a i rozpatrując wierzchołki w kolejności alfabetycznej. Narysuj uzyskane drzewa i podaj w jakiej kolejności rozpatrujesz wierzchołki.

Zadanie 10.2. Pomóż literce X wydostać się z labiryntu. W tym celu wykorzystaj reprezentację grafową dla tego problemu i zastosuj jeden z poznanych algorytmów.

Zadanie 10.3. Opisz prosty algorytm (bazujący na BFS lub DFS), który określa, czy podana krawędź w grafie G (podanym macierzą przyległości) jest krawędzią cięcia. Dla grafu podanego macierzą przyłegłości poniżej sprawdź, czy krawędź viv& jest krawędzią cięcia.

0 1 1 1 0 0 0 1 1 0 1 1 0 0 0 0 1 1 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 1 1 0 0 0 0 1 1 0 1 1 0 0 0 1 1 1 0

Zadanie 10.4. Po zastosowaniu algorytmu Dijkstry dla pewnego grafu o zbiorze wierzchołków {a, 6,..., i} poszukującego najkrótszych ścieżek z wierzchołka a do pozostałych wierzchołków otrzymano na końcu następujące wektory etykiet:

wektor długości ścieżek (etykiety lewe): l = (0,17,15,3,5,5,7,16,2), wektor poprzedników (etykiety prawe): p =    i, i, a,a, c, a).

Na tej postawie wyznacz najkrótsze ścieżki z a do b oraz z a do i Znajdź wagi każdej z krawędzi na tych ścieżkach.

Zadanie 10.5. Odkoduj ciąg (3, 3, 1, 2, 4, 2, 5), otrzymany za pomocą kodowania Priifera. Sprawdź wynik kodując otrzymane drzewo.