4736387695

6. W poniższym grafie zapisany jest schemat wybranego fragmentu metra. Wagi krawędzi oznaczają liczbę pasażerów (w tysiącach), którą na danym odcinku mogą przewieźć pociągi w ciągu jednego dnia. Ile maksymalnie osób może dziennie przejechać z punktu A do punktu BI

i___1

7. Udowodnić poprawność metody (omówionej na wykładzie) znajdowania maksymalnego przepływu w sieci z wieloma źródłami oraz ujściami.

11. Skojarzenia w grafach dwudzielnych

1.    Udowodnić, że moc maksymalnego skojarzenia w grafie dwudzielnym G jest równa wartości maksymalnego przepływu / w sieci G' stowarzyszonej z G.

2.    Skojarzeniem całkowitym w grafie dwudzielnym G = (V,E), gdzie V = V\ U V2 oraz |Vj| = \V2\1 nazywamy skojarzenie MCE takie, że dla każdego wierzchołka v G V istnieje krawędź a G M incydentna z v. Udowodnić następujące twierdzenie Halla.

Niech G = (U, E) będzie grafem dwudzielnym takim, że V = V\ U ¥2 oraz |Vi| = |Uj|. WG istnieje skojarzenie całkowite wtedy i tylko wtedy, gdy dla każdego podzbioru A C Vj zachodzi |A| < |</?(A)|_; gdzie

<p(A) = {v € V ; {v,u} C E dla pewnego u G ^4}.

3. Przypuśćmy, że w pewnej firmie pracuje 10 pracowników: Pi,... ,Pio-W pewnym okresie czasu trzeba wykonać zadania: Z\,... ,215. W poniższej tabeli 1 (odp. 0) na miejscu (p*, zf) oznacza, że pracownik p* może (odp. nie może) wykonać zadanie Zj. Stosując odpowiedni algorytm omówiony na wykładzie przydzielić pracownikom zadania w ten sposób aby zostało wykonane możliwie najwięcej zadań.