(1) Mějme kostru K = (V, E) ohodnoceného grafu G. Pak je K ohodnocený strom. Ohodnocení hrany G E značíme w(ei). Pokud seřadíme ohodnocení hran tohoto stromu za sebe (sestupně), dostaneme posloupnost, které budeme říkat hodnota kostry. Dokažte, že libovolné dvě minimální kostry grafu mají stejnou hodnotu.
(2) Dokažte, že pokud lze maximální tok v libovolném grafu získat s pomocí Ford-Fulkersonova algoritmu, lze získat s pomocí F-F algoritmu tak, že v žádném kroku nepoužiji zlepšující polocestu, která vede přes protisměrné hrany (tj. aplikuji F-F algoritmus a nikdy nebudu protlačovat proti směru).
Je to možné i v případě, když použiji navíc Edmondsonův algoritmus (beru vždy nejkratší zlepšující polocestu)?
(3) Buď dán ohodnocený graf G = (V, E, c), kde c(e) je funkce ohodnocení, ve kterém hledám minimální tok /(e). Při hledání užívám F-F algoritmus. Po několika (n) krocích algoritmu se náhodně zastavím (aniž bych nutně nalezl řešení) a sestavím graf G2 = (V, E, c — fn), tj. bude vypadat stejně až na to, že hrana e E E bude ohodnocena rozdílem c(e) — /n(e), kde /n(e) je hodnota toku, která byla zatím vypočtena. Buď (Z, S) minimální řez v grafu G2- Je to minimální řez i v grafu G ?
Rozhodněte a své rozhodnutí zdůvodněte. Zdůvodněním se rozumí buď důkaz, nebo protipříklad.
1