I have a weighted undirected graph G0, from which I want to derive weigthed undirected graphs G1 and G2.
- All nodes in G0 have a degree of at least one.
- G1 and G2 can contain the same node but not the same edge.
- All nodes in both G1 and G2 should have a degree of at least one.
- All edges from G0 should be contained in either G1 or G2
- Both G1 and G2 are subgraphs of G0 and cannot contain additional nodes.
Let’s assume that the sum of all the edges in G0 = x.
I need to find the pair of G1 and G2 for which the sum of all edges in G1 is closest to x/2
How would you go about solving that?
Edit: After much hassle due to my lack of explanatory powers, here is a better explanation of the problem (this is for an unweighted graph, but it will at least point me in the general direction of a suitable algorithm, also it avoids technical terms because is obvious that I struggle understanding them at the moment)
Lets assume that we have an undirected Graph with Vertices A,B,C,D,E
A --- B | / | | / | C | / | / D --- E
Which means an adjacency matrix like this one:
A B C D E A - 1 0 1 0 B 1 - 1 1 1 C 0 1 - 0 1 D 1 1 0 - 1 E 0 1 1 1 -
Assuming all edges are undirected, we have the following edges:
(a,b) (a,d) (b,d) (b,e) (b,c) (e,d) (e,c)
What I want is that through AI, I can take that graph and generate two groups of edges of roughly the same size. (In this particular case, since we have 7 edges, we would get a group of 3 edges and another one of 4 edges.
Group 1: (a,b) (a,d) (b,d) (e,d) A --- B | / | / | / D --- E Group 2: (b,e) (b,c) (e,c) B | | C | / E
Notice that all edges in each group are connected by at least one node, that is a requirement.
Another valid solution could be, for example:
Group 1: (d,a) (a,b) (b,c) (c,e) A --- B | | C | / D E Group 2: (d,b) (b,e) (e,d) B / | / | / | D --- E
And so on, as you see there are many valid solutions but I want to know if there’s an algorithm to find one.