Wulital InformatyM Wtl

należy wyznaczać rekurencyjnie

lp.

Aodftnit

Maks, pkL I l/zysk. I

n

Ile jest nicujcmnych i całkow itych rozwiązań nierówności .tj ⁴ *2 '^f *3 ⁴ x4 ⁴ *5 ⁴ xh £'9*

które spełniają warunki

(L

1 .V-. +■ X-

Xa + X,

lic różnych ciągów sy mboli zawierających 4 niepowtarzające się litery i 5 cyfr można utworzyć w ybierając litery ze zbioru (a, b. c, d, e. f. g. h. i i oraz cyfry ze zbioru {J. 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 wszystkie 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.

7.

Narysuj wszystkie nieizomorficznc ze sobą grafy o $ wierzchołkach i 5 krawędziach.

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.

Narysuj Rrtrfreprezentujący zadanie i opisz rozwiązywane łagodnienie w języku teorii grafów.

3

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

brakujące wartości przepływów przez łuki (ozn. ?) tak. że zostanie zdefiniowany przepływ przez tę sieć; wartość maksymalnego przepływu z s do t za pomocą kolejnych ścieżek powiększających przepływ: minimalny przekrój pomiędzy s i t oraz jego przepustowość (zilustruj tw. Forda i Fulkersona).

Podróżnik odwiedzi! pewien daleki kraj 1 zapisał w swojej relacji z podróży: „W tym pięknym kraju jest 8 dużych miast. Wiele z nich połączonych jest ze sobą utwardzonymi traktami, które nigdzie poza miastami się nic krzyżują. W każdym mieście początek traktu wskazuje specjalna brama z nazwą 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.'" /weryfikuj w oparciu o teorię grafów wiarygodność lej relacji.

a)

b) e)

r\

//

/

1 n» lit oe 43 ą.

SUMA:

50

<r>

jf

c.

m