# Analyze undirected weight graph and generate two sub graphs

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.

• Just edited trying to make it clearer, I am trying to find the pair of G1 and G2 with the most similar weight. Thanks for your help I just want to know what to read in order to solve something like this using AI. Sorry about the lack of clarity – LeedMx Feb 24 '20 at 1:47
• When you say the weights of G1, do you mean the sum of the weights of the edges in G1? When you say "approximate to zero", how close to zero do they need to be? – D.W. Feb 24 '20 at 1:58
• What I mean is that I want the best pair of G1 and G2, the criteria to define the best pair is : the pair for which the sum of edges in G1 is the closest to the sum of the edges in G2... – LeedMx Feb 24 '20 at 2:04
• Should we edit out all references to AI? It seems to me that the question is more about just graph theory & formulating a problem. – Juho Mar 9 '20 at 19:59
• You are correct! no harm in removing them. – LeedMx Mar 10 '20 at 18:58