I have a weighted undirected graph $G_0$, from which I want to derive weighted undirected graphs $G_1$ and $G_2$.
- All nodes in $G_0$ have a degree of at least one.
- $G_1$ and $G_2$ can contain the same node but not the same edge.
- All nodes in both $G_1$ and $G_2$ should have a degree of at least one.
- All edges from $G_0$ should be contained in either $G_1$ or $G_2$
- Both $G_1$ and $G_2$ are subgraphs of $G_0$ and cannot contain additional nodes.
- Edit (Added constraint): $G_1$ and $G_2$ are both traversable trails
Let's assume that the sum of all the edges in $G_0$ is $x$.
I need to find the pair of $G_1$ and $G_2$ for which the sum of all edges in $G_1$ 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 to 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.