wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Finding minimum number of pen lifts required
        
(Message started by: singhar on Jul 21^st, 2011, 11:08am)

Title: Finding minimum number of pen lifts required
Post by singhar on Jul 21^st, 2011, 11:08am

We have to draw a diagram that consists of several line segments. We are given the start and end coordinates of these line segements. Now we need to find what is the minimum number of times one needs to lift his pen to draw the entire diagram. If needed one is allowed to split a give line segment into two collinear pieces.

Title: Re: Finding minimum number of pen lifts required
Post by towr on Jul 21^st, 2011, 1:11pm

[hide]Split the graph in connected components
For each component count the number of nodes where there's an odd number of ingoing/outgoing connections.
And I think if you divide that by two, and add one for each connected component without nodes with odd parity you're done.[/hide]

Title: Re: Finding minimum number of pen lifts required
Post by singhar on Jul 21^st, 2011, 2:35pm

This one is going to be an undirected unweighted graph. Could you elaborate your approach a bit more.

I was thinking of the following:

Find the largest eulerian subgraph Gsub and then drop all the edges of Gsub from the original graph G and repeat the process. Each eulerian sub graph will give a path between pen lifts.

Title: Re: Finding minimum number of pen lifts required
Post by towr on Jul 21^st, 2011, 10:09pm

It's basically the same approach, but without explicitly finding the eulerian subgraphs. You know there's a eulerian trail in a connected component if there are at most two vertices with an odd number of edges. My reasoning is that for every additional pair of vertices with an odd number of edges you can split the connected component in two (by splitting specific nodes in two), such that one component has only two vertices with an odd number of edges (and thus a Eulerian trail).