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|)\).