0
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ 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 $\endgroup$
    – LeedMx
    Feb 24, 2020 at 1:47
  • $\begingroup$ 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? $\endgroup$
    – D.W. ♦
    Feb 24, 2020 at 1:58
  • $\begingroup$ 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... $\endgroup$
    – LeedMx
    Feb 24, 2020 at 2:04
  • $\begingroup$ Should we edit out all references to AI? It seems to me that the question is more about just graph theory & formulating a problem. $\endgroup$
    – Juho
    Mar 9, 2020 at 19:59
  • $\begingroup$ You are correct! no harm in removing them. $\endgroup$
    – LeedMx
    Mar 10, 2020 at 18:58

1 Answer 1

Reset to default
1
$\begingroup$

Sorry about the poor explanation, but after a lot of help here, Stack Overflow and Math 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!

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Your first example can be partitioned into {D-A, D-B, D-E} and {B-A, B-E, B-C, C-E}, which satisfy all your constraints but they are not paths. Could you please clarify this in the question itself instead of posting it as an answer? $\endgroup$
    – xskxzr
    Mar 9, 2020 at 9:53
  • $\begingroup$ I see what you mean, I apologize, initially I was looking for any subgraph, but I ended up accepted this problem definition as it is much easier to solve by finding an eulerian path and spliting it in half. Cannot think of another way to consistently produce solutions, for example, in your solution even tho is valid, is hard to come up with an algorithm that leads to it. I will add the constraint to prevent misunderstandings but thank you for pointing it out. $\endgroup$
    – LeedMx
    Mar 9, 2020 at 14:41
  • $\begingroup$ If there is an Eulerian path, then there are such two trails, but if there are such two trails, there may not be an Eulerian path, so the problem is still not completely solved. $\endgroup$
    – xskxzr
    Mar 9, 2020 at 16:23
  • $\begingroup$ You are correct! but thats something I'm willing to accept, for my particular case I will only provide solutions for graphs with eulerian path or cycle. In fact, for my implementation I will complete the graph with the required edges to be able to have an eulerian path $\endgroup$
    – LeedMx
    Mar 9, 2020 at 17:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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