I've been struggling on how to approach a problem for over two weeks now. I am supposed to generate an undirected graph which represents a map of streets, and I am supposed to divide the map into two sets of non overlapping streets and both paths should be roughly the same distance.
What kind of algorithm should I use to solve it?
I'm just looking for a general direction here on what kind of algorithm should I use to do that.
Edit: (Test Case)
Lets assume that we have a non weighted, 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 an algorithm to find one and I will keep the first one found. How would I do that?
I'm sure that theres a formal way to state this problem, and I will very much appreciate if you tell me how should I do that.