# S.O.S. Mathematics CyberBoard

Your Resource for mathematics help on the web!
 It is currently Sat, 3 Dec 2016 12:41:12 UTC

 All times are UTC [ DST ]

 Page 1 of 1 [ 6 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Graph DecompositionPosted: Thu, 20 May 2010 16:06:18 UTC
 Senior Member

Joined: Tue, 7 Aug 2007 11:37:58 UTC
Posts: 141
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,

Top

 Post subject: Re: Graph DecompositionPosted: Fri, 21 May 2010 08:11:57 UTC
 S.O.S. Oldtimer

Joined: Sun, 4 Nov 2007 12:08:30 UTC
Posts: 246
Location: Bratislava, Slovakia
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,

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

 Post subject: Posted: Sun, 23 May 2010 11:37:46 UTC
 Senior Member

Joined: Tue, 7 Aug 2007 11:37:58 UTC
Posts: 141
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

 Post subject: Posted: Sun, 23 May 2010 12:07:48 UTC
 S.O.S. Oldtimer

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

I mean dividing G into more than 2 subgraphs.

More than 2 or at least 2?

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

 Post subject: Posted: Sun, 23 May 2010 12:18:29 UTC
 S.O.S. Oldtimer

Joined: Sun, 4 Nov 2007 12:08:30 UTC
Posts: 246
Location: Bratislava, Slovakia
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

 Post subject: Posted: Mon, 24 May 2010 11:15:11 UTC
 Senior Member

Joined: Tue, 7 Aug 2007 11:37:58 UTC
Posts: 141
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

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 6 posts ]

 All times are UTC [ DST ]

#### Who is online

Users browsing this forum: No registered users

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

Search for:
 Jump to:  Select a forum ------------------ High School and College Mathematics    Algebra    Geometry and Trigonometry    Calculus    Matrix and Linear Algebra    Differential Equations    Probability and Statistics    Proposed Problems Applications    Physics, Chemistry, Engineering, etc.    Computer Science    Math for Business and Economics Advanced Mathematics    Foundations    Algebra and Number Theory    Analysis and Topology    Applied Mathematics    Other Topics in Advanced Mathematics Other Topics    Administrator Announcements    Comments and Suggestions for S.O.S. Math    Posting Math Formulas with LaTeX    Miscellaneous