Santa Claus — modified 2022-01-06 13:54 (364 days ago) — edit — reply
1. Graf rozdělíme podle mostů: Trojúhelníky jsou dva a každý je právě jeden cyklus. [2] Hvězdičky obsahují každá 7 trojúhelníků. [14] Dále od stromu můžeme oddělit kmen, který tvoří jeden cyklus, ale v žádném dalším indukovaném podgrafu nebude. [1] Strom obsahuje křížení, které můžeme rozmotat na dva cykly. [2] Dále dva trojúhelníky a dva pěticykly a dva šesticykly. [6] Dohromady 25. 2. Spustíme hladový algoritmus. Viz obrázek Celkem bude hodnota kostry 182. 3. Ano. Strom obsahuje křížení ve hvězdičkách a uprostřed. Křížení uprostřed vyřešíme překreslením jedné z křívek do vnější stěny. Hvězdičky rozmotáme tak, že přesuneme druhý a čtvrtý vrchol dovnitř trojúhelníku, který tvoří zbylé vrcholy. (číslováno směrem hod. ručiček. od vrcholu s mostem)