11597 - Spanning Subtree

All about problems in Volume 115. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

11597 - Spanning Subtree

Post by yiuyuho » Fri Apr 24, 2009 4:35 pm

I see that the answer is trivially n/2, but why is that true?

User avatar
Tausiq
New poster
Posts: 6
Joined: Fri Mar 06, 2009 4:54 pm
Location: just here
Contact:

Re: 11597 - Spanning Subtree

Post by Tausiq » Wed Jun 16, 2010 9:46 pm

How many edges are possible if vertex_number = 4 ?
as there is no self-loop, u can draw 6 edges
try this using pen-paper

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) :D
I took an IQ test .. and the results were negative ! :(

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:

Re: 11597 - Spanning Subtree

Post by zobayer » Sat Mar 19, 2011 12:58 am

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.

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 11597 - Spanning Subtree

Post by Shafaet_du » Thu Jun 02, 2011 6:40 am

Easy problem. in an complete graph you have n*(n-1)/2 edges and you need n-1 edges to form each spanning tree.

AhmadKhatar
New poster
Posts: 28
Joined: Fri Mar 30, 2012 12:57 am

Re: 11597 - Spanning Subtree

Post by AhmadKhatar » Fri Aug 24, 2012 11:42 pm

Hi!
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;
}
Thanks in advance! :D

Post Reply

Return to “Volume 115 (11500-11599)”