dyskretna z lipca 04

Wydział Informatyki WSISiZ Egzamin z matematyki dyskretnej

Nazwisko i Imię : ................................................................................................................................................ Grupa :

Lp.	Zadanie							Maks. pkt.	Uzysk.
1.	W zbiorze A - (a,b,c,d,e) określono relację £ = {(a, a), (a, d), (b, d), (c, c), (d, d), (e, a), (<?, c)}. Ile jest relacji symetrycznych F <zAxA, które zawierają podaną relację, tzn. spełniają £ ę £ ? Ile spośród tych relacji symetrycznych jest jednocześnie zwrotnych?							4
2.	W wieloprocesorowym systemie przydzielane są ponumerowane procesy do ponumerowanych procesorów. Każdy proces jest w całości wykonywany przez jeden procesor, wszystkie procesy muszą być wykonane i wszystkie procesory obciążone. Na ile sposobów można przydzielić 7 procesów do 4 procesorów, tak aby pierwsze dwa procesy zostały wykonane na tym samym procesorze? Potrzebne wartości wyznaczaj posługując się zależnościami rekurencyjnymi.							6
3.	Dla grafu skierowanego ({1, 2, 3. 4, 5, 6}, {(1, 2), (1,4), (2,5), (3, 2), (3,6), (4, 1), (5, 2), (5,4), (5, 6), (6, 3)}) wyznacz macierz sąsiedztwa i na jej podstawie oblicz stopnie wyjściowe i wejściowe wierzchołków względem zbioru (1, 2, 3}. Uzasadnij postępowanie.							4
4.	Rozważ graf o 9 wierzchołkach, w którym suma stopni wierzchołków wynosi 28. Czyjego dopełnienie może mieć 3 składowe spójne? Odpowiedź dokładnie uzasadnij bez rysowania grafu.							5
5.	Narysuj wszystkie parami nieizomorficzne grafy o 5 wierzchołkach i 4 krawędziach. Przy każdym rysunku wypisz ciąg stopni wierzchołków uporządkowany od najmniejszej wartości do największej.							6
6.	Zbadaj czy graf, którego zbiorem wierzchołków jest zbiór kodów Graya rzędu 3, a krawędzie łączą dwa kody różniące się dokładnie na jednej pozycji, jest grafem dwudzielnym. Odpowiedź dokładnie uzasadnij.							5
7.	Posługując się tw. Kuratowskiego zbadaj czy graf opisany podaną macierzą incydencji jest planarny (pomocniczo można graf narysować). Odpowiedź dokładnie uzasadnij.	1 1100000100 o’ 000110000110 100001100001 010101010000 001010110000 000000001100 000000000011						5
8.	Rozstrzygnij z formalnym uzasadnieniem czy można zwiedzić piętro budynku o podanym planie, tak aby wejść drzwiami A, wyjść drzwiami B i przejść przez każde z zaznaczonych drzwi dokładnie raz. A		\			B		5
			a i
			___-
9.	Wyprowadź i podaj warunek dla stopni wierzchołków w grafie o ponad 3 wierzchołkach, który zapewni, że w dopełnieniu tego grafu będzie spełniony warunek dostateczny istnienia cyklu Hamiltona z tw. Ore.							5
10.	Wyznacz w podanym grafie drzewo rozpinające o kodzie Prilfera (2, 2, 5, 5, 4). Wyznacz zbiór wszystkich cykli fundamentalnych względem tego drzewa. ^ Przedstaw jako różnicę symetryczną cykli fundamentalnych cykl prosty > wyznaczony zbiorem krawędzi {(1, 3}, {3, 6}, {5, 6}, (4, 5}, {4, 7}, {2,7), {1,2}}. Sprawdź wynik za pomocą rachunku zbiorów. \ (				J			6
11.	Czy w grafie o 17 wierzchołkach może istnieć pokrycie krawędziowe o mocy 8? Odpowiedź uzasadnij.							4
12.	W podanej sieci (przy lukach podano przepustowości) --------- wiadomo, że zbiór węzłów {j, v, *} wyznacza jej minimalny przekrój. Wyznacz przepustowość tego f przekroju. Co na podstawie wartości tej przepustowości A 2 ęS \o, 2 t A można powiedzieć o maksymalnej wartości przepływu '"■'C J przez tę sieć? \. \i l/ / Podaj przykład przepływu o takiej wartości. Wszystkie odpowiedzi dokładnie uzasadnij. w							5
Egzan\_03J SUM Al								60