#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)
|  C
| / 

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)
    / |
   /  |
  /   | 
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!!!

Leave a Reply

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