Zestaw3

Wydział Informatyki WSISiZ

Nazwisko i Imię:

Grupa:

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	11, 12	13, 14	15,16	17.18	19,20
Ocena	3,0	_Ł5_	_śfi	44	5,0

m.

Lp.	Zadanie - . . , .. . - - _** *<• ^ fe- _			Maks. pkt.	Uzysk.
1. /	A t y Narysuj graf opisany macierzą incydencji I£ ^ S C 9-	‘l 0 0 1 l 0 0 li 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 1 l 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 l 0 0 0 0	-■-WWW- w :Va~: .MS	2 1 1 i i	Sśbss
	Narysuj graf o 5 wierzchołkach, w którym stopnie wierzchołków są kolejnymi liczbajni nieparzystymi, albo uzasadnij, że taki graf nie istnieje. (jUMfiClt f lijtĆłtuLW. dtffuc'			2
3.	Jaka jest minimalna liczba składowych spójnych w grafie o 8 wierzchołkach, w którym suma stopni wierzchołków nie przekracza 12? Narysuj taki graf.			2
4. J	Narvsui zraf skierowany, dla któreeo erafem Dochodnym iest zraf KL. i w którym istnieje cvk! Eulera, albo uzasadnij, że taki graf nie istnieje.			2
5.	Dana jest sieć oparta na grafie w której przepustowości wszystkich łuków równe są 1. Wyznacz w niej przepływ o wartości równej 3, albo uzasadnij, że taki przepływ nie istnieje.			2 ipf
6.	Wyznacz w grafie K5 drzewo rozpinające o kodzie Priifera równym (1, 1,1).			2
7.	Narysuj graf, który jest drzewem o 4 wierzchołkach i wyznacz w nim wszystkie cykle fundamentalne. Ile ich jest?			2
8.	W pewnym grafie o 7 wierzchołkach maksymalna moc wewnętrznie stabilnego zbioru wierzchołków wynosi 4. Ile wynosi minimalna moc pokrycia wierzchołkowego w tym grafie? Czy może w nim istnieć skojarzenie o mocy 4? Odpowiedzi uzasadnij!			2
9.	W grafie wyznacz skojarzenie pełne, albo uzasadnij, że ono nie istnieje.			2	•
10.	Czy graf, który zawiera jako podgraf graf K3 może być 2-barwny? . j t Skonstruuj przykład, lub uzasadnij, że jest to niemożliwe. ^<c 7 kJltisijUMM _			2

SUMA:

20