Desátá sada domácích úloh k MB103
Příklad 1. Nechť G je úplný graf zobrazený v rovině, jehož hranami jsou úsečky
označené skutečnými euklidovskými vzdálenostmi příslušných vrcholů. Dokažte, že
maximální stupeň vrcholu v minimální kostře G je šest. (Návod: uvědomte si, že
takový vrchol může být středem pravidelného šestiúhelníku, sedm takových hran
se už nepodaří...)
Příklad 2. Sformulujte alespoň dva algoritmy pro maximální kostry (tj. kostry s
maximálním součtem označení hran) a odůvodněte jejich správnost.
Příklad 3. Vrcholy v úplném grafu K6 jsou označeny 1, . . . , 6, hrany mezi i a j
pak čísly (i+j mod 2)+1. Najděte všechny neizomorfní minimální kostry a napište
jejich kódy z nul a jedniček metodou z přednášky.
1