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.

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

Pospup algoritmu

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

1. Číslovaný seznam For each generated condidate, test if it is a spanning tree

To be a spanning tree, the candidate graph must:

• be connected
• contain no cycle
• and contain all nodes of the original graph