12. cvičení z MB154, podzim 2021
Příklad 1. Dokončete příklady z minula, v mém případě 2, 3, 4. Příklad 2.
Odvoďte rekurentní formuli pro počet ak koster grafu Gk
k hran
a určete vytvořující funkci posloupnosti ak. Můžete dopočítat explicitní vzorec pro ak, ale nevyjde extra hezky.
Rozdělte podle přítomných hran mezi třemi nejpravějšími. Pokud některá z nich v kostře není, jedná se v podstatě o kostru Gk-i, pokud jsou přítomny všechny tři, vezměte v pravé části nej delší podgraf tvaru
k — i — 1 hran
který je k levé části - kostře grafu G i - přilepen jednou ze dvou možností, takže vyjde
Ofc = 3afc-i + 2afc-2 H-----h 2a0 + 1
kde poslední 1 odpovídá možnosti k — i — 1 = k, kdy už podgraf tvoří celou kostru. Vytvořující funkci určete z této rekurence, šlo by ji taky algebraicky zjednodušit na
ak = Adk-x - ak-2 + [k = 0] ale to už by měli umět příliš dokonale.
Příklad 3.
Odvoďte rekurentní formuli pro počet ak pokrytí (nerozlíšenými) kostkami domina obdélníku 2k x 3. Můžete také určit vytvořující funkci posloupnosti ak, případně dopočítat.
Rozdělte podle nejmenšího netriviálního obdélníka vpravo pokrytého kostkami. Speciální možnost je 2 x 3 se třemi možnostmi, mimo ni musí pravá část vypadat takto (případně překlopené podle horizontální osy)
i
2
a je tedy počet takovýchto dláždění roven 2 • g^. Dostáváme rekurentní formuli
a-k = 3afc-i + 2afc-2 H-----h 2a0 + [A; = 0].