# #StackBounty: #algorithms #graphs #artificial-intelligence Use AI to analyze undirected weight graph and generate two sub graphs

### Bounty: 50

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.

Get this bounty!!!

This site uses Akismet to reduce spam. Learn how your comment data is processed.