\A vd**ad Mj IŁ
Egzamin % matematyki dyskretnej (D)
UWAGA' W trakcie rtsawarywama zadań należy krótko objaśniać postępowanie powołując się na twierdzenia lub zagadnienia «.c^bflatarycz3r>e, z których się korzysta.
Wyrafci obJtćzen sianowńąoe rozwiązania zadań należy wyróżniać poprzedzając je skrótem „Odp.:”.
v4 TTłooz one zawerać symboli potęgi ubywającej i przyrastającej, silni oraz współczynnika dwumianowego i wielomianowego; rroga j&yć orzed^awione w postaci wyrażeń arytmetycznych zawierających symbole operacji dodawania, odejmowania, mnożenia i toeienia oraz zwyMego potęgowania.
należy wyznaczać rekurencyjnie.
£U4 W,
- |
— |
1 | |||||
oj | |||||||
■ ; |
5 |
* — _1_ |
' 1 | ||||
* |
6 | ||||||
1 |
i
Pecr^ebrie wartości liczbowe • ’• k I i
|a, ; zAisrue |
I Maks. pkt. |
Uzysk. |
I. Ile iest akujenwych i ca&owitych rozwiązań nierów ności x\ + + x$ + xA + x$ + <12, 1S które spełniają warunki: s {2.5.4} i Xj + Ay + xA + xt = 6 . |
5 |
0 |
2. Be różnvch dąsów- symboli zawierających 6 liter i 5 niepowtarzających się cyfr można utworzyć K wybierając litery ze zbioru {a. b. o. d. e, f. g. h, i. R} oraz cyfry ze zbioru {1,2, 3. 4. 5, 6, 7}? |
5 |
3 |
5. Na iłe sposobów można rozdzielić 13 jednakowy ch procesów pomiędzy 5 jednakowych procesorów t&L abv na jednym z nich zostały wy konane dokładnie 3 procesy? Rozdzielić trzeba wszystkie procesy, żaden z procesorów nie może pozostać bezczynny i każdy proces mus: b\ć w całości wykoniny na jednym procesorze. |
5 |
1 |
4 &fany do dvspoz\c'i S osób. wśród który ch są dw ie grupy narodowościowe: dwoje Estończyków : czworo Gruzinów. Na ile sposobów można ustawić te 8 osób w szereg tak, żeby osoby żadnej z tych dwóch narodowości nie stały w komplecie obok siebie? |
5 |
| |
ss r*a podanej kracie ulic najkrótszych dróg z A do B. przechodzą przyna jmniej przez jedno z zaznaczonych
2.
3
rwrnm grafie o 16 wierzchołkach maksymalna moc wewnętrznie stabilnego zbioru wierzchołków ?si 9. Ile wyndsi minimalna moc pokrycia w ierzchołkowego w tym grafie? iC *\? - ^ rsoże w nim istnieć skojarzenie o mocy 8? Odpow iedzi dokładnie uzasadniaj.
óżzuk odwiedził pewien daleki kraj i zapisał w swojej relacji z podróży: „W tym pięknym kraju } duży ch miast. Wiele z nich połączonych jest ze sobą utwardzonymi traktami, które nigdzie poza $ami się nie krzy żują. W każdym mieście początek traktu wskazuje specjalna brama z nazwą miało którego on prowadzi. Stolica ma 7 takich bram. Pięć większych miast ma po 5 takich bram a w hm z pozostały ch są 4 takie bramy.” Zweryfikuj w oparciu o teorię grafów wiarygodność tej
łr
nej sieci (przy lukach podano wartości przepływów iasach ich przepustowości) wyznacz: brakujące wartości przepływów przez łuki (ozn. ?) tak. że zoranie zdefiniowany przepływ przez tę sieć; wanosc maksymalnego przepływ u z s do t za pomocą kolejnych ścieżek powiększających przepływ; minimalny przekrój pomiędzy S i t oraz jego
rzepu
stowość (zilustruj tw. Forda i Fulkersona)
y*arvsuj wszy stkie nieizomorficzne ze sobą grafy o 5 wierzchołkach i 4 krawędziach.
KOZSua
zwiedz
przejść
\&v$u
ygmj z uzasadnieniem w oparciu o teonę gratów, czy można ić piętro budynku o podanym obok planie tak, aby wejść ni A. wy jść drzwiami B i przez każde z zaznaczonych drzwi dokładnie raz.
i graf reprezentujący zadanie i opisz rozwiązywane renie w jeżyku teorii grafów.