A Network Question

[Aitch]

OK, there is this simple picture that comes up occasionally in puzzle books and so on - see fig. 1. The idea is to draw the figure without taking the pencil off the paper or repeating a line.

http://forums.randi.org/imagehosting/2435549aff5ee5089e.gif (http://forums.randi.org/vbimghost.php?do=displayimg&imgid=15537)

So, I was at a loose end and starting playing with the image. I came up with several ways to draw the image - even excluding reflections and the direction you draw in. A couple of things occurred to me while doing this:

1. It's a bit of a waste of time :)
2. Every successful attempt started off from one of the two bottom corners.
3. And ended on the other one.
4. These corners have an odd number of lines meeting at them.
5. All the others have an even number.
6. Penis[1]

A couple of questions:
1. Have I missed anything?
2. This is just a variation on the Konigsberg Bridge Problem isn't it?
3. What USE is it?

Thank you.

1 Not entirely relevant - just thrown in to keep Yrreg quiet.

[Cuddles]

1. Have I missed anything?

I don't think so.

2. This is just a variation on the Konigsberg Bridge Problem isn't it?

Yes.

3. What USE is it?

Quite a lot actually. Networks, shortest paths, most efficient paths and so on turn up all over the place. Being able to solve this kind of problem (obviuosly this particular example is rather simple, but more complex ones are, well, more complex) can help with all kinds of things from road planning and logisitics to computer networks and the internet to things that seem completely unrelated but can be reduced to similar problems mathematically.

Of course, in the end none of that really matters. It's maths. If someone can think of a question, you'll find plenty of people who will look for an answer just to see if they can. "Useful" is a four letter word to pure mathematicians.

Edit: One thing I should note is that although in this simple example all the points that can't be used to start have an even number of connections, that is not generally the case. Having an odd number of points is a necessary condition, but is not sufficient in itself.

[Dave Rogers]

Edit: One thing I should note is that although in this simple example all the points that can't be used to start have an even number of connections, that is not generally the case. Having an odd number of points is a necessary condition, but is not sufficient in itself.

Huh? Shirley Knott. If there are two points with an odd number of connections, the network can only be traversed starting from either one and finishing on the other. If there are no points with an odd number of connections, the network can be traversed starting from any point and finishing at the same point. If there are more than two points with an odd number of connections, the network cannot be traversed. And if there's only one point with an odd number of connections, your geometry is so impossible it makes Escher look pedestrian.

Dave

[Dave Rogers]

1. Have I missed anything?

7. ?????????
8. PROFIT!

Dave

[drkitten]

A couple of questions:
1. Have I missed anything?

What would happen if I put another triangle at the bottom of the diagram, symmetrically? Would it still be solvable?


2. This is just a variation on the Konigsberg Bridge Problem isn't it?

Yes. The term you want to use if you're googling is "Eulerian" (as in "Eulerian path" or "Eulerian cycle" or "Eulerian graph").


3. What USE is it?

Routing, circuit design, optimization. Lots of applications, actually.

[Cuddles]

Huh? Shirley Knott. If there are two points with an odd number of connections, the network can only be traversed starting from either one and finishing on the other. If there are no points with an odd number of connections, the network can be traversed starting from any point and finishing at the same point. If there are more than two points with an odd number of connections, the network cannot be traversed. And if there's only one point with an odd number of connections, your geometry is so impossible it makes Escher look pedestrian.

Dave

If you have no points with an odd number of connections the solution is trivial, if you have an odd number of points with an odd number of connections then it is impossible and so also trivial. The only interesting case is when an even number of points have an odd number of connections. So yes, my statement isn't correct generally, I was just talking about non-trivial networks. Although now I think about it I'm not completely sure I was right about that either. Will every point with odd connections actually always be possible to use as a starting point?

Of course, there's also the more general case that tries to find the minimum amount of travel required rather than being restricted to travelling each line exactly once. But that just makes my head hurt.

[Aitch]

What would happen if I put another triangle at the bottom of the diagram, symmetrically? Would it still be solvable?.

Yes. I just tried. :cool:

One way is to start at TL, up to peak, down to TR, down to BR, down to bottom 'peak', up to BL, up to TL, across to TR, diagonally to BL, across to BR, diagonally up to TL. If that makes sense? :boggled:

ETA: B = Bottom, T = Top, L = Left and R = Right - referring to corners of central square.

[Aitch]

If you have no points with an odd number of connections the solution is trivial, if you have an odd number of points with an odd number of connections then it is impossible and so also trivial. The only interesting case is when an even number of points have an odd number of connections. So yes, my statement isn't correct generally, I was just talking about non-trivial networks. Although now I think about it I'm not completely sure I was right about that either. Will every point with odd connections actually always be possible to use as a starting point?

Just checked on Wikipedia (http://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg); it appears that:
Euler's argument shows that a walk of the desired form exists if and only if the graph is connected, and there are exactly zero or two nodes of odd degree.

Which, I suppose, explains the original and DrKitten's modification both being soluble.

[Dave Rogers]

The only interesting case is when an even number of points have an odd number of connections. So yes, my statement isn't correct generally, I was just talking about non-trivial networks. Although now I think about it I'm not completely sure I was right about that either. Will every point with odd connections actually always be possible to use as a starting point?

Yes. Assuming two, and only two, points with an odd number of connections, all possible traversals must start on one and finish on the other. Since any traversal must be possible in either direction, the starting point must have an odd number of connections, and any point with an odd number of connections must be a possible starting point.

Dave

[TobiasTheViking]

6. Penis[1]



now you are speaking my language

[Aitch]

OK, thanks for all that. Now a related (I think) question...

If you have a number of points on a surface (ie piece of paper - let's not get non-Euclidian just yet), there is a minimum number of lines you need to join each point to ever other point.

Did some playing about with pencil and paper, and got the following:
Points/Lines
1/0
2/1
3/3
4/6
5/10
6/15
etc

The relationship seems to be expressable in three ways:

1. by an equation: L = (P2 - P)/2
where P is number of points and L is number of lines.

2. a series? Ln = Pn-12 - Ln-1

3. as: P!/2((P-2)!)

Problem with the first is that it's a continuous function whereas the numbers of points and lines must be integer. I assume. Any integer number of points gives an integer number of points, but an integer number of could lead to a non-integer number of points. Which is absurd. It does, however, give a sensible answer for 0 points; but it also gives answers for negative numbers of points.

The second seems to work OK for values of 3 or above. But may be just a reworking of 1. Or possibly very, very loosely related to some sort of Fibonacci series.

The third could probably be written better - it's a long time since I did this sort of maths! - any corrections gratefully received. However it only works for values above 1 - assuming (-x)! is not legal and 0! = 1

Questions:
1. Should 0 points be considered at all?
2. Are my logic and numbers OK?
3. If not where am I going wrong?
4. Which expression is correct, or is there a 4th?
5. What do I need to Google to get information on this area?
6. Is there a cheap/simple (preferably both!) book that covers this sort of thing?

Thanks!

Oh, and yes, I do have too much time on my hands! :cool:

[Aitch]

Oops! Slight error in my previous post. :o

The second expression seems to work for 2 up; possibly for 1 as well, if 0 is considered a valid starting point.