Please see this node diagram. I want a closed loop that hits each of the 16 nodes exactly once, and travels an odd number of red paths (and thus also an odd number of blue paths). For instance, ABCDEFIPOLHKJNMGA is a loop that travels six red nodes.
Given how easy it is to find loops with even red node counts (I’ve found loops with two, four, and six), I suspect what I want is impossible. However, it’s not clear to me why. If anyone knows how to demonstrate that it’s impossible, I’d be interested in that as well.
You do understand that Travelling Salesperson is an important problem in Computer Science and that Computer Science is most definitely not Math, Pure or otherwise? Hardly any Mathematicians care in the least about NP complete problems.
As to the OP: I don’t answer questions that sound a lot like homework questions.
I cannot answer the question but by observation I can state the number of red line segments must be 9 or less.
There are four points, A,D,N and O that have only blue lines and the four are independent–no two are directly connected. That’s eight of the 17 line segments.
Oh crap I left out a line! H is connected to G and I via blue paths. I have corrected it in the diagram. I don’t think this changes what you said, aahala. I don’t see why you think there are 17 segments; there should only be 16. And when you erase all blue paths not connected to A, D, N, or O you get a disconnected graph.
I haven’t found a loop with eight red paths. I wonder if it’s possible. Zero is clearly impossible, because both F and B would have to be connected to both A and K.
Yes I know. However, this is not the Travelling Salesperson problem and it may have an application in computer science but that’s not why I’m doing it.
Are you saying I should use some sort of computer program to solve it? It’s been two years since I took Artificial Intelligence, and while I did notice that this problem resembled some of the problems we did in there, I don’t want to have to download a LISP interpreter and start from scratch.
As for my OP sounding a lot like a homework problem, what do you suggest I change to make it sound less like a homework problem?
Okay, I added the following two pairs of paths. GJ and IL, blue, and ME and CP, also blue. I’ve checked it two ways now. This has to be right. There may be an obvious solution with these new paths - they were new to me too - but I haven’t found it yet.
I’ll post my notes in your format in just a second, ultrafilter.
I notice that B and F have exactly two blue segments, both going to A and K. Therefore there must be at least one red segment, otherwise the segment ABKFA is enclosed.
Well, this is close. Before the hyphen is blue, and after the hyphen is red. If you’d prefer, I can rewrite it exactly like you have, but this was a little more compact.
The first number is the blue-degree of the vertex, and the second is the red-degree. The number in parentheses is the total degree.
There are only two vertices of odd degree, so there is an Euler path (FWIW). There are 6 vertices of odd blue-degree, and 6 vertices of odd red-degree. There are only four vertices with both odd red-degree and odd blue-degree.
These facts may be relevant to the solution of the problem.
If it makes a difference in your analysis, the red edge connecting H and K should be doubled, and both G and I should each have a red edge that connects to itself. (ie, there is a red edge going from G to G.) However, since neither of these made a difference in the problem I posed, I didn’t include them.
Out of curiosity, does this problem arise in some context outside of graph theory? I notice that it’s called “knightnode.gif.” If it’s a knight’s tour problem, I think there’s a fair amount of literature out there about it…
Yes, it’s a knight’s tour problem. If I find a loop then I can construct a rotationally symmetric, re-entrant 8 by 8 knight’s tour. It’s likely that someone has thought of this as a method of doing it before, but if it doesn’t yield a solution, what are the chances that it’s published?
Anyway, if you have any links that you think would apply, I’d love to see them. All I know I read from MathWorld, and that’s not very extensive.
…and, it hits me like a bolt of lightning, such a thing clearly cannot exist. Because after 16 moves, you have to wind up on the same color, and the corresponding square in the next quadrant is the other color.
If anyone wants to know what I’m jabbering about, I’ll explain, but suffice it to say that I know now there is no loop on that graph crossing an odd number of red edges. Sorry to waste your time, but your help was most appreciated.
