Graph Theory

Check up here (click).

Thanks! I do have the book. I wanted to know whether someone else has it as well because there is a problem on Graph Theory which I can't post here but is in the same book I'm stuck on.

Sorry, I have a "Introduction to Graph Theory" but it's by Chartrand and Zhang. Can you give the jist of it?

I have a book with that title, but it's at home and I am at work, so I don't know the author. Perhaps you can post an outline?

I'm at home now, and my book turns out to be J.M. Aldous and R.J. Wilson: Graphs and Applications -- An Introductory Approach; Springer (2000). With any luck, it's just a new edition of your book, with a new title because he changed publishers. So what's the problem you want to discuss?

Thomas, I really appreciate your time and effort. OK, there's a problem, probably in the first chapter on The Hampton Court Maze, where he gives us a sketch of the Hampton Court Maze and tells us to draw a graph from that sketch which shows the various routes one can take to traverse the maze. Please check if your book has this problem. Thanks alot!

Yes, my book has this maze. For Free Duck, this is how it looks like:



My book depicts it upside down however. The graph Wilson constructs from it puts a node in every branching of the graph, and an edge between any two branches that are connected through a corridor.

I'm using "->" to denote "is connected with" now. For example, "b -> c, d" means that b is connected with c and d. In this notation, the graph of the maze has the following structure

a -> b; b -> c, d; d -> e, f; e -> f, g; f -> g; g -> h; h -> i, j; j -> k, l; l -> m.

The question about the graph is: "Use this graph to list all the routes from the centre (A) to the exit (L) that do not involve retracing steps."

Thanks for posting that, Thomas. So, RK4, assuming your book doesn't have the graph constructed from the maze that Thomas mentions, you'll want to construct something like that. If it were me, I would use a node to denote a decision point and probably the end points (dead ends), which I'm guessing is how it was developed in Thomas's edition. So if the red arrow is a, then it has two edges, one to b (the next decision point) and one to c (the dead end). My graph doesn't exactly match the one in Thomas's book. When the graph is finished, it should be easy to see only two solutions where you don't retrace your steps.

Unless I'm missing something, that is.

Yes, the graph in the book starts with 'a' in the center and 'l' at the exit. He always takes a left turn, and whenever he runs into either a dead end or a branching, he calls it a node and labels it with the next letter of the alphabet.

Ah, ok, that makes sense then. I was wondering why there was only one edge out of a, so that makes perfect sense.

Actually, I see three paths that meet the specifications. They differ only in how you you get from 'd' to 'g'. I have d-e-g, d-f-g, and d-e-f-g. The last one is not the shortest, but it doesn't retrace steps, which was the only constraint.

(Patiently waiting for RK4's question.)

Yes Thomas, that's the right problem. So, assuming no back tracking, how many routes are possible from A to L. I could find 3 such routes. Are there more? Can you draw the graph for me? Thanks!

P.S.---> Sorry, I deleted the last topic by mistake.

Yeah, there are three different paths out of this maze. Two of them vary only slightly. Thanks for all the help guys. Really appreciate it.

Here they are:

Route/Path 1: A  B  D  F  E  G  H  J  L

Route/Path 2: A  B  D  E  F  G  H  J  L

Route/Path 3: A  B  D  E G  H  J  L

Note: box indicates arrow.

There's also a b d f g h j l. We both missed one option, so it turns out there are four.

Call me blind, I only saw two. Maybe if I could see the graph in the book it would be more obvious. Ah well.

Oh yeah Thomas! Good work! Indeed there are 4. Hmm, now I wonder if there are any more than 4. Let's hope not! Thanks again for the time and effort. Two minds working together is always better than one!

Thomas, in case you're interested in sharing your thoughts with me on another interesting problem I've posted in this same forum you can click on the one posted under the title "Wheel Rolling." Thanks!