11597  Spanning Subtree
Moderator: Board moderators
11597  Spanning Subtree
I see that the answer is trivially n/2, but why is that true?
Re: 11597  Spanning Subtree
How many edges are possible if vertex_number = 4 ?
as there is no selfloop, u can draw 6 edges
try this using penpaper
similarly, when vertex_number = 6,
highest number of edges = 15
to form a spanning tree with 6 vertices, we must need 5 edges
its very simple, when there are n vertices
we need at least (n  1) edges to form a spanning tree
so, Number of vertices = 6
highest number of edges = 15
minimum 5 edges needed to form a spanning tree
eventually, we can form 3 spanning trees (15 / 5)
as there is no selfloop, u can draw 6 edges
try this using penpaper
similarly, when vertex_number = 6,
highest number of edges = 15
Code: Select all
int edges = 0;
for ( int i = 1; i <= vertex_number; i++ ) {
for ( int j = i + 1; j <= vertex_number; j++ ) {
edges ++;
}
to form a spanning tree with 6 vertices, we must need 5 edges
its very simple, when there are n vertices
we need at least (n  1) edges to form a spanning tree
so, Number of vertices = 6
highest number of edges = 15
minimum 5 edges needed to form a spanning tree
eventually, we can form 3 spanning trees (15 / 5)
I took an IQ test .. and the results were negative !

 Experienced poster
 Posts: 110
 Joined: Tue May 06, 2008 2:18 pm
 Location: CSEDU, Bangladesh
 Contact:
Re: 11597  Spanning Subtree
From combinatorics, it is way too easy to find the required solution. However I am interested if n is odd. Can anyone explain what will happen if n is odd? What I guess is, if n > 3, and n is odd, it is always 2. Is it ok? Find me a path to more of a mathematical proof.
You should not always say what you know, but you should always know what you say.

 Experienced poster
 Posts: 147
 Joined: Mon Jun 07, 2010 11:43 am
 Location: University Of Dhaka,Bangladesh
 Contact:
Re: 11597  Spanning Subtree
Easy problem. in an complete graph you have n*(n1)/2 edges and you need n1 edges to form each spanning tree.
UVa stats: http://felixhalim.net/uva/hunting.php?id=63448
My blog on programming: http://www.shafaetsplanet.com/planetcoding/
My blog on programming: http://www.shafaetsplanet.com/planetcoding/

 New poster
 Posts: 28
 Joined: Fri Mar 30, 2012 12:57 am
Re: 11597  Spanning Subtree
Hi!
Does anybody know how can I reduce my runtime to zero?
Here is my code:
Thanks in advance!
Does anybody know how can I reduce my runtime to zero?
Here is my code:
Code: Select all
#include <stdio.h>
int main()
{
int n;
int caseNo = 1;
scanf( "%d", &n );
while ( n != 0 )
{
printf( "Case %d: %d\n", caseNo++, n >> 1 );
scanf( "%d", &n );
}
return 0;
}