The Gateway to Computer Science Excellence
+4 votes
345 views

Calculate the number of Spanning trees possible for each of these graphs


in Graph Theory by Active (5.1k points) | 345 views
0

I am getting :

  1. 81
  2. 77
  3. 27
0
In the 2nd Fig,is O a node or just the pt of intersection of AC and BD?
0

Balaji Jegan for 1 i am getting 80.

0
@balaji

How bro?
0
Getting 64,61,24
0

Balaji Jegan in 2nd 5 vertices are there. We need to pick 4 edges from 8. answer will be less than 8c4=70.

How are you getting 77?

0
For 1st, 3c2*3c2*3c2*3c2-8 (length 4 cycle) =73
0
@balaji

question is not correct

u need to give weight to each edges

Otherwise how do we calculate MST?
0
is $(1,2)$ and $(1,3)$ same type of edge ?
+1
@srestha, if we use Kirchoffs algo, why would we require edge weights to determine spanning trees? Qstn didn't ask for min or max spanning tree
0
2nd one 69

3rd one 54
0
@Sayan

then there will be no cycle

right?

So, 1st one will be $\binom{3}{2}\times \binom{3}{2}\times \binom{3}{2}\times \binom{2}{1}=54$
0
2nd one will be

$\binom{4}{3}\times \binom{4}{1}=16$

3rd one will be

$\binom{3}{2}\times \binom{3}{2}\times \binom{2}{1}=18$
0
0
but is spanning tree means , $1$ edge need to be removed from the subgraph?

Spanning tree means , every vertex need to be enclose and also no cycle will be there

right?

So, how can we tell if there is 5 edges, there wouldnot be any cycle?
0

srestha mam

if u r referring to link i added then they take care of that case earlier so atlast only 5 edges cases remaining

0
I need to draw the graph now

otherwise, I havenot got any error in my answer too.

Is there any answer given @Balaji??

or self doubt?
0
self doubt
0
then do I give the picture I got?

because it cannot be even checked :(
0
0

@Sayan Bose O is a vertex

0

@adarsh_1997 

I am getting :

792 - ( 468+32+56+4+4) = 228.

Please help to point out my mistake.

Please log in or register to answer this question.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,380 answers
198,528 comments
105,321 users