S.O.S. Mathematics CyberBoard

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

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.

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

More than 2 or at least 2?


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.)

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.

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..