For a while now, I've been meaning to start more threads about specific branches of mathematics, to serve as introductions to those areas . I've decided to start with something called 'graph theory', because it's not terribly hard to explain (I'll mostly be letting my diagrams do the talking), and it's quite different from what's usually taught at school.

Now, when I talk about 'graphs', you're probably thinking of something like this:

However, graph theorists aren't interested in those things . While it's true that those things are graphs, the word 'graph' actually has an entirely separate, unrelated definition - and that's the kind of 'graphs' that graph theorists are interested in.

Basically, in graph theory, a 'graph' is a collection of points (also called 'nodes' or 'vertices'), connected by lines (also called 'links' or 'edges'). So, something like this:

These kinds of structures are very useful, because they can represent all kinds of different things. Perhaps the blue vertices represent towns, and the green edges represent roads connecting them. Or, maybe the vertices represent computers, and the edges represent cables connecting them. Or perhaps the vertices represent people, and the edges represent friendships . You can probably think of plenty more examples of uses for these kinds of diagrams.

Notice that the vertex in the top left is attached to one edge; the one in the bottom left is attached to two edges; and the one on the top right is attached to three edges. This number is known as the 'degree' of the vertex (so, the one in the top left has degree 1; the one in the bottom left has degree 2; and the one in the top right has degree 3)

Do note that not all graphs are as nice as that one. Sometimes, you'll get vertices that aren't connected to anything, or you'll get vertices that are connected to each other more than once - or you might even get vertices that are connected to themselves :

On this graph, the vertex in the bottom right has degree 0, because it isn't connected to anything. The one that's connected to itself has degree 5: there's one edge connecting it to the top left; two edges connecting it to the bottom left; and the one that connects it to itself is counted twice (because it's connected to that edge at both ends).

Fortunately, this nonsense about "vertices being connected to themselves" doesn't crop up particularly often in graph theory: most of the important graphs don't have those . Probably the most important graphs are the ones where every vertex is connected to every other vertex exactly once. These are known as 'complete graphs', and you can see three of them here:

First, we have the complete graph of three vertices (also known as K

Anyway, before I finish, I'll quickly introduce a couple of other types of graph. Sometimes, graphs are connected with arrows instead of just plain lines. These are known as directed graphs, and they have their own set of uses. For example, if this is a graph of people, then instead of representing friendships, the one-way arrows might represent "Who fancies whom" :

Or, sometimes, you'll find graphs where the edges have numbers attached to them. These are known as weighted graphs - and, once again, they have their own set of uses. For example, if the vertices represent cities, then the numbers (or 'weights') might represent the shortest distance between those two cities. Here's an example, which is not to scale (but that's actually fine: graph theorists aren't going to do any geometry, so they don't care whether their diagrams are to scale or not !!!):

Those are all the core concepts that I can think of, so I think this would be a good point for me to stop for now. If you have any questions about anything I've posted so far, then let me know and I'll do my best to answer. Or, if you can think of anything that I've missed, then feel free to add it in a reply !

Otherwise, thanks for reading, and I hope you've learned something !

Now, when I talk about 'graphs', you're probably thinking of something like this:

However, graph theorists aren't interested in those things . While it's true that those things are graphs, the word 'graph' actually has an entirely separate, unrelated definition - and that's the kind of 'graphs' that graph theorists are interested in.

Basically, in graph theory, a 'graph' is a collection of points (also called 'nodes' or 'vertices'), connected by lines (also called 'links' or 'edges'). So, something like this:

These kinds of structures are very useful, because they can represent all kinds of different things. Perhaps the blue vertices represent towns, and the green edges represent roads connecting them. Or, maybe the vertices represent computers, and the edges represent cables connecting them. Or perhaps the vertices represent people, and the edges represent friendships . You can probably think of plenty more examples of uses for these kinds of diagrams.

Notice that the vertex in the top left is attached to one edge; the one in the bottom left is attached to two edges; and the one on the top right is attached to three edges. This number is known as the 'degree' of the vertex (so, the one in the top left has degree 1; the one in the bottom left has degree 2; and the one in the top right has degree 3)

Do note that not all graphs are as nice as that one. Sometimes, you'll get vertices that aren't connected to anything, or you'll get vertices that are connected to each other more than once - or you might even get vertices that are connected to themselves :

On this graph, the vertex in the bottom right has degree 0, because it isn't connected to anything. The one that's connected to itself has degree 5: there's one edge connecting it to the top left; two edges connecting it to the bottom left; and the one that connects it to itself is counted twice (because it's connected to that edge at both ends).

Fortunately, this nonsense about "vertices being connected to themselves" doesn't crop up particularly often in graph theory: most of the important graphs don't have those . Probably the most important graphs are the ones where every vertex is connected to every other vertex exactly once. These are known as 'complete graphs', and you can see three of them here:

First, we have the complete graph of three vertices (also known as K

_{3}), which is just three vertices linked in a triangle. Next, we have the complete graph of four vertices (also known as K_{4}), which has four vertices linked up in a square (including the two diagonals). Then, the next member of the family is K_{5}, which resembles a pentagon with a star inside it. (K_{5}is one of the most important graphs of all, for reasons which I'll get to later )Anyway, before I finish, I'll quickly introduce a couple of other types of graph. Sometimes, graphs are connected with arrows instead of just plain lines. These are known as directed graphs, and they have their own set of uses. For example, if this is a graph of people, then instead of representing friendships, the one-way arrows might represent "Who fancies whom" :

Or, sometimes, you'll find graphs where the edges have numbers attached to them. These are known as weighted graphs - and, once again, they have their own set of uses. For example, if the vertices represent cities, then the numbers (or 'weights') might represent the shortest distance between those two cities. Here's an example, which is not to scale (but that's actually fine: graph theorists aren't going to do any geometry, so they don't care whether their diagrams are to scale or not !!!):

Those are all the core concepts that I can think of, so I think this would be a good point for me to stop for now. If you have any questions about anything I've posted so far, then let me know and I'll do my best to answer. Or, if you can think of anything that I've missed, then feel free to add it in a reply !

Otherwise, thanks for reading, and I hope you've learned something !

Board Information and Policies

Affiliation | Coffee Credits | Member Ranks | Awards | Name Changes | Account Deletion

Personal Data Protection | BBCode Reference

Lurker101 Wrote:I wouldn't be surprised if there was a Mega Blok movie planned but the pieces wouldn't fit together.

(Thanks to ObsessedwithBirds for the avatar and sig!)

My Items