====== Zadání ======

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

===== Řešení pomocí Kirchhoffova teoremu =====

Přečtěte si co je to [[http://en.wikipedia.org/wiki/Kirchhoff's_theorem|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 [[http://en.wikipedia.org/wiki/Laplacian_matrix|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 nejrychlejsi 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.
===== Řešení pomocí generování koster =====

Ú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í**

    - **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
    - **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.

~~DISCUSSION~~