image002 (57)

Wydział Informatyki WIT Egzamin z matematyki dyskretnej (D)

Nazwisko

i Imię :    .......

Grupa

UWAGA! W trakcie rozwiązywania zadań należy krótko objaśniać postępowanie powołując się na twierdzenia lub zagadnienia kombinatoryczne, z których się korzysta-

Wyniki obliczeń stanowiące rozwiązania zadań należy wyróżniać poprzedzając je skrótem „Odp.;".

Nie mogą one zawierać symboli potęgi ubywającej i przyrastającej, silni oraz współczynnika dwumianowego i wielomianowego; mogą być przedstawione w postaci wyrażeń arytmetycznych zawierających symbole operacji dodawania, odejmowania, mnożenia i dzielenia oraz zwykłego potęgowania.

Potrzebne wartości liczbowe P(n. k) s 1ⁿ l należy wyznaczać rekurencyjnie.

Zadanie

Maks. pkt [ Uzysk, i

irodowośctowi

' Mamy do dyspozycji 9 osób. wśród których są dw ie grupy troje Węgrów i czw oro Finów.

1 Na ile sposobów można ustaw ić te 9 osób w szereg tak. żeby osoby żadnej z tych dwóch narodowości nie stały w komplecie obok siebie?

ile jest na podanej kracie ulic najkrótszych dróg z A do B. które przechodzą przynajmniej przez jedno z zaznaczonych skrzy żowań C. D łub E?

Ile jest nieujemny ch i całkowitych rozwiązań nierówności Xj -i I które spełniają warunki: xj.x₆ e {1-2.3} i x₂ + x₃ 4-x₄ +x₅ = t

x₅+x₆<9.

I Ile różnych ciągów symboli zawierających 4 niepowtarzające się litery i 5 cyfr można utworzyć i wybierając litery ze zbioru ja, b, c, d. e. £ g. h. i} oraz cy fry ze zbioru {1,2. 3.4. 5,6.7}?

Na ile sposobów można rozdzielić 13 jednakowych procesów pomiędzy 4 jednakowe procesory' tak. aby' na jednym z nich zostały' wykonane dokładnie 4 procesy?

Rozdzielić trzeba wszy stkie procesy', żaden z procesorów nie może pozostać bezczynny i każdy proces ] musi być w całości wykonany na jednym procesorze.

6. ! Narysuj wszystkie nieizomorficzne ze sobą grafy o 5 wierzchołkach i 5 krawędziach.

j Rozstrzygnij z uzasadnieniem w oparciu o teorię grafów, czy można zwiedzić piętro budynku o podanym obok planie tak. aby wejść drzwiami A, wyjść drzwiami B i przejść przez każde z zaznaczonych drzwi dokładnie raz.

I Narysuj graf reprezentujący zadanie i opisz rozwiązywane zagadnienie w języku teorii grafów.

x

3

-I_

O

8. W podanej sieci (przy łukach podano wartości przepływów i w nawiasach ich przepustowości) wyznacz:

a)    brakujące wartości przepływów przez luki (ozn. ?) tak, że zostanie zdefiniowany przepływ' przez tę sieć;

b)    wartość maksymalnego przepływu z s do t za pomocą kolejnych ścieżek powiększających przepływ;

"—i

SUMA:

c)    minimalny przekrój pomiędzy s i t oraz jego przepustowość (zilustruj tw. Forda i Fulkersona).

Podróżnik odwiedził pewien daleki kraj i zapisał w swojej relacji z podróży: ..W tym pięknym kraju jest 8 duży ch miast. Wiele z nich połączonych jest ze sobą utwardzonymi traktami, które nigdzie poza miastami się nie krzyżują. W każdym mieście początek traktu wskazuje specjalna brama z nazwą j miasta, do którego on prowadzi. Trzy najważniejsze miasta mają po 6 takich bram. W każdym z [pozostałych są 4 takie bramy.” Zweryfikuj w oparciu o teorię grafów wiarygodność tej relacji.

10. W pewnym grafie o 15 wierzchołkach maksymalna moc skojarzenia wynosi 7. Ile wynosi minimalna moc pokrycia krawędziowego w tym grafie?

Czy może w nim istnieć wewnętrznie stabilny zbiór wierzchołków o mocy 9? Odpowiedzi dokładnie uzasadniaj.

£gz_md_ue Aj 4