#2 25. 11. 2012 14:17 — Editoval kompik (25. 11. 2012 15:25)
Re: Počet kostier
↑ Speeder:
Ak 
je pocet kostier grafu 
, tak
kde 
je graf, ktory vznikne vynechanim hrany 
a 
je graf, ktory vznikne stotoznenim jej koncovych vrcholov. (Mozu pri tom vzniknut nasobne hrany.) Podmienka je, aby hrana e nebola sluckou.
Takto sa to da previest na ratanie kostier dvoch grafov - jeden ma o hranu menej; druhy o vrchol menej. Casom clovek dospeje k jednoduchym grafom - aj ked pre graf, co si nakreslil sa tato metoda zda byt pracna.
Tu je to vysvetlene aj ukazane na priklade: R. Balakrishnan: A Textbook of Graph Theory, p.76.
Wikipedia spomina aj ine metody, ale tie sa zdaju byt este kompikovaniejsie:
* Counting spanning trees
* Kirchhoff's theorem
Offline
#3 25. 11. 2012 16:57
Re: Počet kostier
nebo to muzes spocitat jako determinant Laplaceovy matice s vynechanym i-tym radkem a sloupcem... (co je to Laplaceova matice najdes zde http://cs.wikipedia.org/wiki/Graf_%28te … f%C5%AF%29 u reprezentace grafu)
Offline