image012 (15)

\A vd**ad Mj IŁ

Egzamin % matematyki dyskretnej (D)

Grupa

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

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$ + x_A + x$ + <12, 1S które spełniają warunki: s {2.5.4} i Xj + Ay + x_A + x_t = 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

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

8- « F*** i i w nav

u a)

ł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.