Matematické Fórum
Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
#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