3
svar
275
visningar
thpthp behöver inte mer hjälp
Hur många uppspännande träd kan man finna i en graf?
Hej,
Jag pluggar inför en tenta och undrar om det finns något smidigt sätt eller en formel för att ta reda på hur många uppspännande träd man kan finna i en graf.
Ett exempel för att göra det enklare:
Vi har en graf som på bilden
Det finns några formler här (lite beroende på vad du egentligen vill räkna). Se om det hjälper dig:
jag försökte kolla men hittar inget som skulle kunna räkna hur många uppspännande träd som finns i grafen. Eftersom det är det jag vill räkna ut. Jag måste hitta hur många uppspännande träd som finns i grafen. Dock behöver jag inte just för den uppgiften jag vill allmänt veta hur man räknar ut det.
Kolla in denna formel https://en.wikipedia.org/wiki/Cayley%27s_formula