S.O.S. Mathematics CyberBoard

Your Resource for mathematics help on the web!
It is currently Tue, 25 Nov 2014 01:18:42 UTC

All times are UTC [ DST ]




Post new topic Reply to topic  [ 6 posts ] 
Author Message
 Post subject: Graph Decomposition
PostPosted: Thu, 20 May 2010 16:06:18 UTC 
Offline
Senior Member

Joined: Tue, 7 Aug 2007 11:37:58 UTC
Posts: 131
Hi everyone,


Given a G graph with n vertics, it is required to divide G into subgraphs; it is not necessary that the sizes of new subgraphs are equal.

The main point is the number of edges among the subgraphs is minimized

How can we solve such problem? or

What methods were used to solve such problem?



Thank you for any help,
full_adder


Top
 Profile  
 
 Post subject: Re: Graph Decomposition
PostPosted: Fri, 21 May 2010 08:11:57 UTC 
Offline
S.O.S. Oldtimer

Joined: Sun, 4 Nov 2007 12:08:30 UTC
Posts: 246
Location: Bratislava, Slovakia
full_adder wrote:
Hi everyone,


Given a G graph with n vertices, it is required to divide G into subgraphs; it is not necessary that the sizes of new subgraphs are equal.

The main point is the number of edges among the subgraphs is minimized

How can we solve such problem? or

What methods were used to solve such problem?



Thank you for any help,
full_adder

If you mean dividing G into 2 subgraphs then it is finding minimal cut, which seems to be well-known. (You might also want to have a look at Menger's theorem.

Using more than 2 subgraphs does not make sense to me - it would increase (or at least not decrease) the number of edges connecting the subgraphs.


Top
 Profile  
 
 Post subject:
PostPosted: Sun, 23 May 2010 11:37:46 UTC 
Offline
Senior Member

Joined: Tue, 7 Aug 2007 11:37:58 UTC
Posts: 131
thank you kompik

I mean dividing G into more than 2 subgraphs.

My goal is to get the min possible number of edges among the sungraphs


Top
 Profile  
 
 Post subject:
PostPosted: Sun, 23 May 2010 12:07:48 UTC 
Offline
S.O.S. Oldtimer

Joined: Sun, 4 Nov 2007 12:08:30 UTC
Posts: 246
Location: Bratislava, Slovakia
full_adder wrote:
thank you kompik

I mean dividing G into more than 2 subgraphs.

More than 2 or at least 2?

full_adder wrote:
My goal is to get the min possible number of edges among the subgraphs

It should be clear that the less subgraphs the better. (Since when you glue two subgraphs together, you do not increase the number of edges.)


Top
 Profile  
 
 Post subject:
PostPosted: Sun, 23 May 2010 12:18:29 UTC 
Offline
S.O.S. Oldtimer

Joined: Sun, 4 Nov 2007 12:08:30 UTC
Posts: 246
Location: Bratislava, Slovakia
full_adder wrote:
thank you kompik

I mean dividing G into more than 2 subgraphs.

My goal is to get the min possible number of edges among the sungraphs

Ok, now that I see the world possible in bold I think that I misunderstood the original question.
Do you want to the following?
Divide n elements into k parts (k can be arbitrary) such that if you add edges between all vertices that are in different parts of the partition, then the number of edges is minimal.


Top
 Profile  
 
 Post subject:
PostPosted: Mon, 24 May 2010 11:15:11 UTC 
Offline
Senior Member

Joined: Tue, 7 Aug 2007 11:37:58 UTC
Posts: 131
Many thanks kompik

I will explain the problem by an example but I cannot insert a figure in this board :(
Suppose G has vertices 1, 2, 3, 4, 5, 6, 7, 8
The edges are between :
1 & 2 , 1 & 3, 2 & 4, 3 & 7, 5 & 7, 4 & 6, 4 & 8

One solution is divide G into two subgraphs, s1 = {1,2,3} and s2={4,5,6,7,8}
# of edges between the subgraphs is 2

However, another solution is to divide G into two subgraphs, s1={1,3,5,7} and s2={2,4,6,8}
# of edges between the subgraphs is 1

We select the second solution since # of edges is 1..

Of course, we can divide G into two subgraohs different from these.. and we can divide it into three subgraphs, four subgraphs,... (i.e., at least two subgraphs) if we can divide G into k (k=2,3,.., or 8 ) subgraps and the # of edges is, for example, is 0, this will be the best solution.

This is an example. However, dividing G into TWO subgraphs is undesirable especially if the size of G is large because the size of a subgraph will still be large relatively; and the ultimate goal of graph decomposition is to reduce the size into small sizes whenever possible..

Hopefully the problem is clear now..


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 6 posts ] 

All times are UTC [ DST ]


Who is online

Users browsing this forum: No registered users


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Search for:
Jump to:  
Contact Us | S.O.S. Mathematics Homepage
Privacy Statement | Search the "old" CyberBoard

users online during the last hour
Powered by phpBB © 2001, 2005-2011 phpBB Group.
Copyright © 1999-2013 MathMedics, LLC. All rights reserved.
Math Medics, LLC. - P.O. Box 12395 - El Paso TX 79913 - USA