2. Klasówka 2001/02#
Zadanie 1#
Słowa kluczowe: grafy; przepływy
Dla danej sieci \(G=(V, s, t, c)\) i przepływu \(f\) zaproponuj efektywny algorytm znajdowania ścieżki rozszerzającej o największej przepustowości ,,wąskiego gardła»». Uwaga: para \((u, v)\) jest krawędzią w \(G\) wtedy i tylko wtedy, gdy \(c(u, v) > 0\).
Zadanie 2#
Słowa kluczowe: grafy
Pokryciem krawędziowym w grafie \(G\) (bez izolowanych wierzchołków) nazywamy taki podzbiór krawędzi z \(G\), że każdy wierzchołek grafu jest końcem co najmniej jednej z krawędzi tego zbioru. Zaproponuj efektywny algorytm znajdowania najmniej licznego pokrycia krawędziowego w danym grafie dwudzielnym \(G\).
Zadanie 3#
Słowa kluczowe: grafy; dwuspójność
Zaprojektuj efektywny algorytm, który dla danego grafu dwuspójnego \(G = (V, E)\) znajdzie dwuspójny podgraf rozpinający \(H = (V, F)\) taki, że \(|F| = O(|V|)\).