jc.int 0 Posted December 29, 2011 Hello, I have thought of this math problem I haven't been able to solve, but it must have a simple solution. We have an undefined (either even or odd) number of line segments and we want to connect their end dots except two of them (for all the set -like if a fluid could get in by the unconnected dot, pass through all the segments and connections and them go out by the other unconnected dot).But there is an imposition: the connection cannot connect two segments that are side by side. Here is an uncompleted sketch -How can we know wherever it is better to have an odd number of line segments or an even one as to use the less length of connection? -What is, then, the best disposition of the connections (two by two and then the last one connects with the first one, three by three, etc)? I guess the way to solve this problem is to create a Cartesian model of it, but I don't know what to do then. Merry Christmas Jaime 0 Share this post Link to post Share on other sites

DrRocket 337 Posted December 29, 2011 Hello, I have thought of this math problem I haven't been able to solve, but it must have a simple solution. We have an undefined (either even or odd) number of line segments and we want to connect their end dots except two of them (for all the set -like if a fluid could get in by the unconnected dot, pass through all the segments and connections and them go out by the other unconnected dot).But there is an imposition: the connection cannot connect two segments that are side by side. Here is an uncompleted sketch -How can we know wherever it is better to have an odd number of line segments or an even one as to use the less length of connection? -What is, then, the best disposition of the connections (two by two and then the last one connects with the first one, three by three, etc)? I guess the way to solve this problem is to create a Cartesian model of it, but I don't know what to do then. Merry Christmas Jaime You have not clearly defined your problem, but it appears to be a variation on the Euler circuit in graph theory (Google "Euler circuit" for more information). The minor wrinkle is that all of your vertices (here lines), except 2, are of degree two while the two exceptions are of degree one. This is a well-known variation. The desired circuit always exists under these conditions. Since you have provided no cost function for optimization, there is no meaning to "best". You might want to read a book on graph theory. 0 Share this post Link to post Share on other sites

DrRocket 337 Posted December 29, 2011 Hello, I have thought of this math problem I haven't been able to solve, but it must have a simple solution. We have an undefined (either even or odd) number of line segments and we want to connect their end dots except two of them (for all the set -like if a fluid could get in by the unconnected dot, pass through all the segments and connections and them go out by the other unconnected dot).But there is an imposition: the connection cannot connect two segments that are side by side. Here is an uncompleted sketch -How can we know wherever it is better to have an odd number of line segments or an even one as to use the less length of connection? -What is, then, the best disposition of the connections (two by two and then the last one connects with the first one, three by three, etc)? I guess the way to solve this problem is to create a Cartesian model of it, but I don't know what to do then. Merry Christmas Jaime You have not clearly defined your problem, but it appears to be a variation on the Euler circuit in graph theory (Google "Euler circuit" for more information). The minor wrinkle is that all of your vertices (here lines), except 2, are of degree two while the two exceptions are of degree one. This is a well-known variation. The desired circuit always exists under these conditions. Since you have provided no cost function for optimization, there is no meaning to "best". You might want to read a book on graph theory. 0 Share this post Link to post Share on other sites

jc.int 0 Posted December 31, 2011 Thank you for your answer, I didn't thought that it would be interesting to comparemy problem with the Euler path. Do you know if there is a computer program that could help me find the answer (I've found this but it isn't really what I'm searching for as it passes through all the vectors I draw (http://www.math.okstate.edu/~wrightd/1493/euler/)? By the way the best circuit is the one that uses the least lenght of connection. Happy new year 0 Share this post Link to post Share on other sites

DrRocket 337 Posted January 1, 2012 Thank you for your answer, I didn't thought that it would be interesting to comparemy problem with the Euler path. Do you know if there is a computer program that could help me find the answer (I've found this but it isn't really what I'm searching for as it passes through all the vectors I draw (http://www.math.okst...htd/1493/euler/)? By the way the best circuit is the one that uses the least lenght of connection. Happy new year You have not defined "length of connection". t is not obvious what a natural definition would be for your problem. In general the problem of finding minimal lenght Euler path is called the "traveling salesman problem". It is computationally difficult -- as I recall it is NP-complete. Before you spend a lot of time on your problem you should take the time to learn some graph theory. Graph Theory by Bondy and Murty is one of the classic textbooks. A somewhat unusual,but very nice, treatment oriented towards electrical engineers is Graph Theory with engineering applications by David Johnson and Johnny Johnson. 0 Share this post Link to post Share on other sites