Zadání

https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=counting_spanning_trees

Přečtěte si co je to Kirchoffuv teorem Ze zadání si vytvořím dvě matice - matici stupně vrcholů a matici sousednosti. Od matice stupně vrcholů odečtu matici sousednosti a dostanu Laplacianskou matici Kirchhoffuv teorem říká, že když od této matice odeberu jeden řádek a sloupec (vytvořím její kofaktor), dostanu matici jejíž determinant se rovná počtu stromů daného grafu. Při volbě algoritmu na výpočet determinantu rovnou vynechte ty rekurzivní a zkuste implementovat LU dekompozici, či obyčejnou Gaussovku.

By Milan: Narážím na zarážející problém - když odeberu z LaplacianM první sloupec a první řádek, dostanu 5/10. Odeberu-li poslední sloupec a řádek, dostanu 6/10. Nevíte, kde může být problém? Nesetkal jste se s tím někdo? Dělám to přes Gaussovku.

By Rosion: Ja odeberu posledni radek a posledni sloupec a v poradku a pouzivam LUDecomp.

By Lukesja7: Odebiram prvni radek a prvni sloupec, pouzivam gausovku > 10/10 Mozna spatne zaokrouhleni?

By stuchpet: Opravdu je to nejdrychlejsi a asi nejrychleji naprogramovatelne reseni. Implementace pomocí (float) matice v Jave a Doolittlova algoritmu na LU rozklad projde bezpecne na 10/10. BTW. Determinant lze pocitat uz behem LU faktorizace.

Úloha byla nejspíše myšlena tak, abychom stromy generovali, protože to se zrovna probírá. Já jsem to řešil první způsobem, prosím ať někdo doplní tento.

Návrh řešení

1. Generate graph conditates
   • all spanning trees have |V|-1 egdes, where V is the number of nodes
   • so we have to generate all (|V|-1)-element subsets of the set of edges. Each subset represents then a canditate graph
2. For each generated condidate, test if it is a spanning tree
   • if a condidate graph is connected,
   • contains no cycle
   • and contains all nodes of the original graph
   • then it is a ST

By Petr: hint pro Javu - generoval jsem subsety hran pomoci permutaci binarniho cisla delky |Pocet hran|, ktere obsahovalo |V-1| jednicek. Reprezentace jako retezec charu postacovala jen na 9/10 kvuli casovemu limitu na predposlednim testu. Vyresil jsem to zmenou reprezentace binarky na pole indexu oznacujici primo index, kde je v binarce jednicka. Zrychleni neni zas tak velke, ale na 10/10 uz to stacilo. Nestiha to pouze public test 03.