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. Číslovaný seznam Generate graph conditates

• Nečíslovaný seznam All spanning trees have |V|-1 egdes, where V is the number of nodes
• Nečíslovaný seznam 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:

• Nečíslovaný seznam be connected
• Nečíslovaný seznam contain no cycle
• Nečíslovaný seznam and contain all nodes of the original graph