0
UGCNET-dec2008-ii-3
source link: https://gateoverflow.in/155027/Ugcnet-dec2008-ii-3
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
3 Answers
3 votes
Best answer
Ans : A.
According to cayley’s formula for counting spanning trees, for a complete graph Kn, T(Kn)= n pow (n-2) where n is the number of vertices. T(k5)=5^(5-2)=5^3= 5 * 5 * 5=125
ref: http://ugcnetsolved-computerscience.blogspot.in/2011/08/ugc-net-solved-computer-science-paper.html
Sep 27, 2017
1 vote
We can use Prüfer sequences (of length n−2n−2) to find the labeled spanning trees for KnKn, using the following decoding algorithm, by Cayley’s theorem the number of spanning trees are nn−2nn−2.
For n=5n=5, there are 53=12553=125 such spanning trees on 55 labeled vertices, as can be computed using the above algorithm
and seen from the following animation:
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK