CODEWITHSUNDEEP
algorithm
197
197

Reputation: 351

Minimum number of total paths in a connected graph

I was looking at the PenLift problem on TopCoder, after reading this editorial I now understand how to do it, however there's one thing I don't understand.

A fairly well known theorem states that to go over all of the edges in a connected graph requires numOfOddVertices/2 total paths.

Which theory is this? Also why is it so? My first thought is to find an Eulerian path by adding edges, to make all the vertices have even degrees except 2, since that would allow an Eulerian path. I'm not sure if this is correct, also if it was, how would I know that would be the best way of doing it, it seems greedy but I don't see any proof. Could someone please link me to the theory or explain how it works? Thanks in advance.

Upvotes: 2

Views: 1367

Answers (3)

MJW
MJW

Reputation: 387

First, the method proposed in the original question is certainly correct: pair all the odd vertices but two, add an edge between each pair, and compute the Eulerian path. The added edges correspond to moves in the final traversal.

If the desire is to minimize the motion of a pen plotter or such, consider the following: The motion for drawing the lines always equals the sum of the edge lengths, so the only way to save motion is to minimize the moves. The added edges represent the moves, so the goal is to pair the odd vertices in a way that minimizes the length of the added edges. That's actually a well-known but rather difficult problem called "minimum-cost perfect matching on a general graph" (note, general graph, not bipartite). There's an algorithm called the Blossom algorithm that can solve it in something like O^3 time, but I've never found a satisfactory description of the full algorithm -- all rather vague and confusing.

Upvotes: 0

Jeewantha
Jeewantha

Reputation: 985

In a graph the number of odd vertices (n) is always zero or an even number. If n = 0 you can traverse the entire graph starting from any point. If n > 0, to traverse the graph, you should always start from one odd vertex and you will end from another odd vertex. Say the number of paths you draw continuously is K.

  • if n = 2 you can still traverse the graph from one go. ie starting from one odd vertex and ending at the other. K = 1
  • if n = 4 after traversing once you will be left with a sub graph which has 2 odd vertices. you can traverse that sub graph with one go. K = 2
  • if n = 6 you will have to traverse the graph 3 times. K = 3 and so on .....

Please read my blog post for more info. http://jeewanthad.blogspot.com/2012/11/eulerian-trail.html

Upvotes: 2

David Eisenstat
David Eisenstat

Reputation: 65427

Which theory is this?

Graph theory.

Also why is it so?

We need to assume at least one pair of odd-degree vertices.

Lower bound: prove inductively that a graph with 2k odd-degree vertices requires at least k paths. Base case k = 1: trivial. Step k > 1: removing a path from a graph with 2k odd-degree vertices leaves at least 2k-2 = 2(k-1) odd-degree vertices.

Upper bound: augment the graph with k edges connecting pairwise disjoint pairs of odd-degree vertices. Now all vertices have even degree, so there exists an Euler circuit. Delete the new edges from this circuit; k paths remain.

Upvotes: 3

Related Questions