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