Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm just trying to learn about graph theory and I'm not strong in math to this degree so I'm wondering if this is even possible. If so, I'd appreciate some beginner level resources, if they exist for this topic. If I have two sets of directed graphs with 2 nodes each (to simplify the example) and they are effectively "pointing" at each other can I determine this in any way? Is there an idea of direction that exists outside of the graph itself? I'm thinking of maybe using simple cardinal directions or just left/right/up/down but since an edge that doesn't exist yet has no direction is this even possible?
I hope this makes some sense and please ask for further clarification since I'd like to refine this idea as I learn more. Thanks!

share|improve this question
1  
It's hard to understand what you mean by "pointing". Could you perhaps give a concrete example of the situation you're trying to describe? –  Henning Makholm Dec 11 '11 at 4:53
1  
I'm struggling with an example, but I'm thinking of something like a set of kids train tracks. If I were to lay tracks down in a direction and someone else were laying them down in another direction, is it possible to tell ahead of time that they will connect or if they are just each going off in completely incompatible directions? Maybe "heading" is a better word? –  McArthey Dec 11 '11 at 5:07

1 Answer 1

up vote 7 down vote accepted

Graphs don't really work like that. They're just abstract nodes with edges between them. A directed edge points from one node to another. It does not in any way point beyond that node. If you have two nodes, A and B, in a directed graph then an edge which connects to both A and B must point from A to B or from B to A. If there's another node C, the edge doesn't point "towards" or "away from" C. They're not like vectors. It has no relationship to C at all. As such, directed graphs can't point towards each other. It's not a sensible idea in graph theory.

Direction in a directed graph is usually expressed using the metaphor of one-way roads. Let's talk about a small country called Onewayvia ruled by a king (Humperdink IV) who is an adherent of Unidirectionality, a small religious sect who believes that since there is only one way to God, roads should never go both ways. All roads in the kingdom must be one-way roads. Now, it's a small kingdom made of small towns. And, in fact, the towns are so small, that they don't really have any roads inside them, just roads which run between towns and meet in the center of town. And due to a ruling from the Unidirectionality synod of 1242 (the "wacky synod" as it's called in the history books), they've also decided that roads should never ever, ever meet out in the country and should never connect more than two towns together.

So now we'll talk about a part of Onewayvia where Baron von Alphabet (the inventor of the Alphabet) ruled for several centuries. He renamed the towns in his barony after his children, which in turn, he had named after the letters of the alphabet. So, in his barony, we have the towns of Ai, Bea, Cee, Dee, and Eeee. Now, let's talk about the roads in the area. First, we'll talk about the road from Ai to Bea. Now, this road isn't straight. It winds through the hills and crosses an unnecessary number of bridges over rivers, but if you leave Ai on it, you eventually get to Bea and not to anywhere else. In turn, from Bea, you can take a road to Cee with some lovely waterfalls along the way. And from Cee, there's a tree-lined drive which leads back to Ai. Or if you're in Bea, there's also a lovely road with a lot of tunnels which leads to Dee. And from Dee, there's an expressway which leads to Eeee. And from Eeee you can take the coast road with the pretty scenery and two windmills and the roadside rest-stop whose design is inspired by Finnish architecture to get to Ai. And those are all the roads in the barony (not counting the roads in and out which have, unfortunately, been closed for the last several years since large portions disintegrated in moderate rainfall. It turned out that the cut-rate road contractors used molasses rather than road tar).

Now, let's say given this information, I ask you to make a detailed map. Well, you're going to have a lot of trouble doing that. You don't know what's north or south or east or west of anything else. You don't know latitude or longitude or Cartesian or radial coordinates or distances between the towns or anything else helpful like that. But if I were to ask you a question like "I'm in Ai and I want to get to Dee, how do I get there?" Well, you could answer that question using the information above. You could say "Well, from Ai, you take the road to Bea (the one with all the bridges) and then from Bea, you take the road to Dee (the one with all the tunnels)." So you do actually know how to get around the barony. You can figure out, from that information, how to get from any town to any other.

But to do this, you'd probably want to draw something out because it's tough to keep all that in your head if you haven't driven around the barony (which I don't recommend actually doing). What you'd draw out is a graph-theory style directed graph. On that graph, the towns would be the vertexes (or "vertices" if you want to sound more mathematiciany) and the roads would be the edges. You can draw out a set of dots for the towns and then arrows between them for the roads to show the connections even without knowing the actual positions of the towns or layouts of the roads. That's what we do in graph theory, we map out connections without knowing anything about location or compass direction or anything else like that. The arrangement of the vertexes is completely arbitrary but the connections between them are accurate.

So, let's go back and talk about that road from Ai to Bee. If, in the kingdom, we have an actual map (and not just a graph) and we ask the question "Does the road from Ai to Bee go towards Cee?" well the answer might be "Yes, it goes almost straight towards Cee but then it stops at Bee before it can get to Cee" or it might be "Well, it starts to go towards Cee, but then it winds and it meanders and then it does a loop-de-loop and it eventually winds up at Bee. So, sort of, but not really. I guess?" (Note: the frequent and gratuitous use of loop-de-loops in road design is chief amongst several reasons that I recommend not actually driving the roads of the barony.) But without a real map, we don't know that. When we're just looking at the graph, asking "Does the road from Ai to Bea go towards Cee?" isn't a question that can be answered. It might, it might not, we have no way of knowing. So, in the world of graph theory, we don't worry about that question because we can't answer it using the graph.

But, questions like, "If I drive from Ai to Bea can I get back home to Ai?" or "How many roads will I have to drive on to get from Ai to Eeee?" or "What's the longest drive I could take where I never repeat the same road twice?" are the sort of questions that we can answer with just a graph. And these are the sort of questions which graph theory answers.

And in practice, it turns out that just worrying about connections and not distance or orientation is quite powerful and can model all sorts of useful and practical situations, especially with some small modifications like edge weights or capacities. This is why graph theory is useful to know.

And hopefully now you understand why your initial question wasn't really sensible. As to some of your other statements, I should first assert that you don't need to be especially "strong in math" to understand graph theory. It doesn't really depend on other parts of math. It is, however, the case that most graph theorist like to use the language of set theory to define their terms this is because set theory is very precise and accurate and entirely sufficient to the task. So if you understand a little set theory, you will find the more formal part of writings on graph theory easier to follow, but it's not strictly necessary. In studying graph theory, you will sometimes have to slow down and read things carefully and think about them precisely. If you can do that, you will be fine whether or not you have much other background in math.

There are a number of introductions to graph theory which are available as free pdfs on the web. Some quick searching turned up this one which covers the topic well, but is very dense and quick, and this one which is not quite as quick, but uses a little more set theory language once you reach a certain point, so I'm not sure that it's really more accessible. But I think that really, what you should probably do is search for introductions to graph theory on YouTube. It's a sufficiently visual branch of mathematics that seeing it drawn out and discussed with pointing and motions and whatnot is probably best.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.