I am having a really hard time explaining a problem to some fellow coders and specially to computer scientists, could you please help me formalizing the following problem:

Lets assume that we have a non weighted, undirected Graph with Vertices A,B,C,D,E

A --- B 
|   / | \
|  /  |  C
| /   | / 
D --- E 

Which means its 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 will accept the first one found.

I'm sure that theres a formal way to state this problem, and I will very much appreciate your help in doing that.

(I apologize in advance, I'm self taught so I have some major knowledge gaps)

  • $\begingroup$ This is not cross posted, Question on CS is aimed at algorithmic solution while the one here clearly states is about the problem formulation, meaning, CS ask what to do, and Math asks how to state the problem, anyway I got it now but was worth claryfing $\endgroup$ Mar 9 '20 at 5:58

You want to find a cut that divides the connected graph into two connected graphs with (nearly) the same number of edges.

Look for algorithms and results on graph cuts. Related is the minimal cut problem.

  • $\begingroup$ Oh dear god, thank you! you're a lifesaver! So, if I understand it correctly, In those examples I found minimum k-cut for k=2? $\endgroup$ Mar 8 '20 at 14:30

After a lot of help here, Stack Overflow and Computer Science Exchange and a lot of reading, I finally understood that what I'm actually trying to do is:

Given a Graph G, obtain two disjointed trails of approximately the same size so that every edge is visited by one of those trails.

Thanks to everyone!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.