Ćwiczenia # 5

1. Narysuj graf G = (X,R), gdzie X = {x,y,z,w} , R={(x,y),(w,x),(w,y),(y,z),(y,z),(w,z)}. Wyznacz macierze incydencji i sąsiedztwa tego grafu. Wyznacz rząd i zerowość grafu.

2. Czy w grafie Hamiltona istnieje obwód Eulera?

3. Wyznacz macierz incydencji grafu zadanego poniższą macierzą sąsiedztwa.

0 1 1

1 0 1

1 0 0

4. Ile jest drzew nieoznakowanych mających 5 wierzchołków?

5. Wyznacz w podanym grafie cykl Eulera i cykl Hamiltona

6. Dla poniższego grafu wyznacz wszystkie dendryty (grafy rozpinające).

7. Podaj przykład grafu skierowanego o wierzchołkach x, y, z, w którym jest cykl z wierzchołkami x i y i inny cykl z wierzchołkami y i z ale nie ma cyklu mającego wierzchołki x i z.

8. Zapisz relację dwuargumentową w zbiorze N określona wzorem: m+n=5 ,

max{m,n} = 2.

9. Czy graf może mieć nieparzystą liczbę wierzchołków nieparzystego stopnia?

10. Czy poniższe grafy są izomorficzne? Odpowiedź uzasadnij.

11. Czy jest możliwe, aby owad poruszający się wzdłuż krawędzi sześcianu przeszedł każdą krawędź dokładnie raz? Odpowiedź uzasadnij.

12. 
    Zastosuj algorytm Fleury'ego aby otrzymać drogę Eulera w poniższym grafie

13. Znajdź wszystkie nieizomorficzne drzewa spinające grafu K₆ (K_3,3). Ile cykli Hamiltona ma ten graf? Ile dróg Hamiltona ma graf K_n,n-1?

14. Zastosuj algorytm Prima, aby znaleźć minimalne drzewo rozpinające w poniższym grafie.

350

240

120 220

320

330

180

270 240

280 90 300

200

280

---