Algorithm for dividing graph into edge pairs

0
votes

I've received a task to find an algorithm which divides a graph G(V,E) into pairs of neighboring edges (colors the graph, such that every pair of neighboring edges has the same color).

I've tried to tackle this problem by drawing out some random graphs and came to a few conclusions:

  1. If a vertex is connected to 2(4,6,8...) vertices of degree 1, these make a pair of edges.
  2. If a vertex of degree 1 is directly connected to a cycle, it doesn't matter which edge of the cycle is paired with the lone edge.

However, I couldn't come up with any other conclusions, so I tried a different approach. I thought about using DFS, finding articulation points and dividing graph into subgraphs with an even number of edges, because those should be dividable by this rule as well, and so on until I end up with only subgraphs of |E(G')| = 2.

Another thing I've come up with is to create a graph G', where E(G) = V(G') and V(G) = E(G'). That way I could get a graph, where I could remove pairs of vertices (former edges) either via DFS or always starting with leaf vertices along with their adjacent vertices.

The last technique is most appealing to me, but it seems to be the slowest one. Any feedback or tips on which of these methods would be the best is much appreciated.

EDIT: In other words, imagine the graph as a layout of a town. Vertices being crossroads, edges being the roads. We want to decorate (sweep, color) each road exactly once, but we can only decorate two connected roads at the same time. I hope this helps for clarification.

For example, having graph G with E={ab,bd,cd,ac,ae,be,bf,fd}, one of possible pair combinations is P={{ab,bf},{ac,cd},{ae,eb},{bd,df}}.

1
algorithmgraph-theory
Problem formulation is not clear for me. What to do with edges of A-B-C-D graph? - MBo
My apologies. I edited the post, I hope it helps. - Samuel Novelinka

1 Answers

2
votes

One approach is to construct a new graph G where:

  1. A vertex in G corresponds to an edge in the original graph
  2. An edge in G connects vertices a and b in G where a and b represent edges in the original graph that meet at a vertex in the original graph

Then, if I have understood the original problem correctly, the objective for G is to find the maximum matching, which can be done, for example, with the Blossom algorithm.