22991

Zestaw 2 (tydzień 2)

nie zawiera cykli

(T) Gra: jest dwudzielny wtedy i tylko wtedy, gdy nieparzystych.

(T) Jeśli grrl dwudzielny jest regularny, to jest, zrównoważony.

(T; Jeśli graf dwudzielny jest regularny, to zawiera pełne skojarzenie.

(oc) Znaleźć SRR dla rodziny: {1,2,31, {1.2,4}, {1,3, 4}, {1,2,3,4} {2,3,4}.

Miech G = (.X_:Y: E). (T) Jeśli S_x > Ay, to G ma skojarzenie z A' do V.

G. Znaleźć różne parametry kostki (hiperkosiki)

7.    (T) H_p jest grafem dwudzielnym.

8.    (T) kostka H_v ma skojarzenie pełne.

9.    Kiedy grafy K_VCr maią uelne sko^:arzeuie?

iO. (oo) (Wąskie gardło) Proces wymaga 5 operacji, które można wykonać na 5 maszynach. Czas (w min.) potrzebny do wykonania operacji i na maszynie j podany jesi w tabeli (wiersze odpowiadają maszynom).Czy można tale rozdzielić pracę, aby skończyć proces w cztery minuty? A w trzy?.

4    5 3 6 4

5    6 2 3 5

3    4 5 2 4!

4    8 3 2 7; 26645]

11. (Wersja haremowa t\v. Kalla). Sformułować i udowodnić.