The Postal Owl

U druhé úlohy jsem na prvním cvičení říkal, že jde řešit postupným přidáváním hran, někdo se ptal, proč by nešly odebírat vrcholy a protože už se blížil konec, neměli jsme čas to dořešit. Chtěl bych proto tady zmínit, že úloha jde řešit i přes odebírání vrcholů a je to dokonce výhodnější, protože nám stačí $n + \log n$ dotazů na kouzelnou krabičku. Funguje to díky faktu, který jsme letmo zmínili, tedy že nezávislá množina v nějakém indukovaném podgrafu grafu je nezávislá i v původním grafu.

U čtvrté úlohy si někdo na druhém cvičení všimnul, že postup z přednášky je pro řešení zbytečně složitý, je možné pro každý vrchol $v$ vyrobit formuli která říká že vrchol bude použit právě v jedné hraně.