Author |
Topic: Finding minimum number of pen lifts required (Read 2063 times) |
|
singhar
Newbie
Posts: 22
|
 |
Finding minimum number of pen lifts required
« on: Jul 21st, 2011, 11:08am » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Finding minimum number of pen lifts required
« Reply #1 on: Jul 21st, 2011, 1:11pm » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
singhar
Newbie
Posts: 22
|
|
Re: Finding minimum number of pen lifts required
« Reply #2 on: Jul 21st, 2011, 2:35pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Finding minimum number of pen lifts required
« Reply #3 on: Jul 21st, 2011, 10:09pm » |
Quote Modify
|
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).
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print