V\td/iai Informatyki WIT

Su?*'foko i Imię

BORKOWSKA MNięSzKfl

Grupa:.

IDOMM

Zadanie

Maks. pkt.

Uzysk,

J Mamy do dyspozycji 9 osób, wśród których są dwie grupy narodowościowe:

I woje Węgrów i czworo Finów¹

I Na ile sposobów można ustaw ić te 9 osób w szereg tak, zęby osoby żadnej z tych dwóch narodowości nic stały w komplecie obok siebie?

f tlą jest na podanej kracie ułk najkrótszych dróg i A do B, które przechodzą pr/y najtunici przez jedno a zaznaczonych i \kr*\ żowaó C. D lub E?

IŻI1TEI

lei I 1 ^rtt

+H

Ue jest nieujemnych i Całkow itych rozmazań nierówności .v. + xy ♦ xą + x* + x* £ 9, które fpełmąją smoki, s _ta (k^3j i ♦ x_; e .*-₄ ♦ x* » 5.

Iłe rożnych ciągów symboli ,\mterających 4 aicpowtar/atacc się litery i 5 cyfr można utworzyć wybierając litery ze /tworu {a. b. c, d. c. f, g. h. i} oraz cytry ze zbioru {1,2, 3,4. 5,6,7}?

| Na ile sposobów można mzdżiełar 13 jetaakowych procesów pomiędzy 4 jednakowe procesory tak, j aby na jednym z nich zostały wykonane dokładnie 4 procesy?

! Rożdżkłtć trzeba m/ys&ic procesy. żaden z procesorów nie może pozostać bezczynny i każdy proces \ musi być w całości wykonany na jednym procesom.

r

z

I *

•ł Narysuj wszystkie nietzomorftczne *t sobą grafy o 5 wierzchołkach i 5 krawędziach.

j Rozstrzygnij z umadnicniem w oparciu o teorię grafów, czy można i 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 not

! Afórysaę grafr^/rtumn^cy radnir i optz: rannl^siwir i laęjduwir w/gnd» tocrii grafów

x

\k podanej sieci (przy lukach podano wartości przepływów i w naw usacfa ich przepustowości) wy znacz:

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

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

c)    minimalny przekrój pomiędzy s i t oraz jego przepustowość (zilustruj Iw, Forda i Fułkersona).

»<»

0(2ł

• 0),

O)

(J>

(2)

i 9

łVduy/ruk odwted/d pew ien daleki kraj i zapisał w swojej relacji z podróży: „W tym pięknym kraju I jest Z dużych miast. Wiele z nich połączonych jest ze sobą utwardzonymi traktami, które nigdzie poza ; miastami mc nic krzy żują. W każdym mieście początek traktu w-skazuje specjalna brama z nazwą ; miasta, do Kusego on prowadzi. Trzy najważniejsze miasta maja po 6 takich bram. W każdym z 1 pozostałych są 4 akie bramy." Zweryfikuj w oparciu o teorię grafów wiary godność tej relacji.

j W pewny ni grafie o 15 wierzchołkach maksymalna moc skojarzenia wynosi 7. j ile wy nosi minimalna moc pokrycia krawędziowego w tym grafie? j Czy może w- nim istnieć wewnętrznie stabilny zbiór wierzchołków o mocy 9?

| (Adąowimdtf tbhdśuf acatatŚMę,

51

h

50