Zestaw2

Wydział Informatyki WSISiZ

Nazwisko i Imię :....

Zestaw zadań egzaminacyjnych z teorii grafów

Rozwiązanie każdego z zadań jest punktowane w skali od 0 do 2 punktów. Suma punktów decyduje o uzyskanej ocenie według tabeli:

Liczba punktów	U. 12	13. 14	15.16	17, 18	19. 20
i Ocena	3.0	3ó	4,0	4,5	5,0

! Lo. ] Zadanie

Maks. pkt. | Uzysk.

1.

! Narysuj graf opisany macierzą sąsiedztwa 3 .,

0    1    )    0    0    1

0    0    1    0    I    0

0    0    0    10    0

0 0 10 10 0    10    0    0    1

10    0    0    0    0

Narysuj graf o 6 wierzchołkach i 2 składowych spójnych, w którym stopnie wierzchołków wynoszą: 4. 5, 2,4, 4, 3, albo uzasadnij, ze taki graf nie istnieje.

Zbadaj czy podane dwa graty są izomorficzne,

czy nie.

Odpowiedź dokładnie uzasadnij!

IJztmełnij nodanv gmf minimalna liczbą krawędzi tak, istniał w nim cykl Eulera. Podaj warunek konieczny i dostateczny istnienia cvklu Eulera w grafie.

! 5.

Czy jeśli w podanym grafie, wybierzemy losowo i usuniemy

(o * )

>

W podanym grafie wskaż krawędzie, które tworzą minimalny zbiór rozspąjąjący wierzchołki 1 i 2. Jaka jest maksymalna liczba dróg krawędziowo rozłącznych łączących wierzchołki 1 i 2? Odpowiedź uzasadnij przytaczając odpowiednie twierdzenie!

7

9.

Ile wynosi maksymalna wartość przepływu w podanej sieci (przy łukach podano ich przepustowości)?

Odpowiedź uzasadnij przytaczając odpowiednie twierdzenie!

Dla podanego grafu i jego drzewa rozpinającego {a. b, c. f, h} przedstaw cykl {a, b, c, d, e, f} jako różnice symetryczną cykli fundamentalnych.

Czy w grafie o 8 wierzchołkach może istnieć pokrycie krawędziowe o mocy 3? Odpowiedź uzasadnij!