Graph Theory 1

Graph theory is a subject that should be taught in high school as an alternative to the usual pre-calculus, calculus route. It is a lot more fun because problems take the form of puzzles without a pre-written method of solution for every question in a section. It was by far my favorite subject as an undergraduate and this series of articles will be my way of trying to rekindle that flame, while hopefully showing others the fun side of math.

Graph theory is about graphs, but not the graphs that most people learn about in high school. Those graphs are pictures that represent the behavior of functions of one variable by showing what a y value does as the x value changes. These graphs are much more fun than that.

A graph is a picture consisting of dots and lines connecting dots. To start, we will only allow one line for any two dots, but two dots do not have to have a line between them and a dot can in fact have no lines touching it. A dot can also have a line going out of it to many other dots.
A picture of a crappily drawn graph is below:
\setlength{\unitlength}{7cm}  \begin{picture}(2,5)  \put(1,1){\line(0,1){1}}  \put(1,1){\circle*{1}}  \put(1,2){\circle*{1}}  \put(1,2){\line(1,0){1}}  \put(2,2){\circle*{1}}  \put(2,2){\line(-1,-1){.5}}  \put(1.5,1.5){\circle*{1}}  \put(1,2){\line(1,-1){.5}}  \put(3,1){\circle*{1}}  \put(1.5,1.5){\line(3,1){1.5}}  \put(3,2){\circle*{1}}  \put(2,2){\line(1,-2){.5}}  \put(2.5,1){\circle*{1}}  \end{picture}

Notice that none of the lines are curved, well that is because I lack the ability to draw squiggly lines. Squiggly lines make for squiggly people, so we will accept my crudely drawn straight line graphs and move on.

A graph can have as little as just one dot, or infinitely many dots and lines. We can also attach directions and numbers to lines. Similarly we can assign a value to a dot. Doing these things leads to different questions than with a generic graph without any labels.

One simple question is, when can I reach every possible dot on the graph? In my above one it is obvious that I cannot reach the bottom right dot because it has no lines going to it. But having every dot with at least one line is also not sufficient enough, for example the graph:

\setlength{\unitlength}{7cm}  \begin{picture}(2,5)  \put(1,1){\line(0,1){1}}  \put(1,1){\circle*{1}}  \put(1,2){\circle*{1}}  \put(1,2){\line(1,0){1}}  \put(2,2){\circle*{1}}  \put(2,2){\line(-1,-1){.5}}  \put(1.5,1.5){\circle*{1}}  \put(1,2){\line(1,-1){.5}}  \put(3,1){\circle*{1}}  \put(3,1){\line(0,1){1}}  \put(3,2){\circle*{1}}  \put(2,2){\line(1,-2){.5}}  \put(2.5,1){\circle*{1}}  \end{picture}

Every dot has a line, but you cannot reach every dot on the graph by going along lines from any starting position. This graph is called disconnected. A graph with the property of being able to get from any point to any other point by going along lines is called a connected graph.

With that in mind, we can ask ourselves, when can I go along edges so that I only touch each dot once? Well of course the graph needs to be connected, but we also need other conditions. Another question is when can I touch each line only once? When can I go all the way through every line and dot only once and come back to where I started?

Graphs can be used to represent things in many different subjects. A lot of time research done in different subjects is useful to somebody else, but because of the language barrier it is unknown. Math tries to be the universal translator of different subjects and languages.

I’ll try to answer some of these next time and be a little more formal in naming things, but for now here are examples of other graphs.
\setlength{\unitlength}{7cm}  \begin{picture}(2,5)  \put(0,0){\circle*{1}}  \put(0,0){\line(1,0){1}}  \put(0,0){\line(1,1){1}}  \put(0,0){\line(0,1){1}}  \put(0,1){\circle*{1}}  \put(0,1){\line(1,0){1}}  \put(1,1){\circle*{1}}  \put(1,1){\line(0,-1){1}}  \put(1,0){\circle*{1}}  \put(1,0){\line(-1,1){1}}  \end{picture}

\setlength{\unitlength}{7cm}  \begin{picture}(2,5)  \thicklines  \put(1,1){\circle*{1}}  \put(1,1){\line(1,1){1}}  \put(1,1){\line(1,-1){1}}  \put(2,0){\line(1,1){1}}  \put(2,0){\circle*{1}}  \put(2,2){\line(1,-1){1}}  \put(2,2){\circle*{1}}  \put(3,1){\circle*{1}}  \put(4,1){\circle*{1}}  \put(3,1){\line(1,0){1}}  \put(2,2){\line(2,-1){2}}  \put(2,1){\circle*{1}}  \put(2,0){\line(0,1){1}}  \end{picture}

\setlength{\unitlength}{7cm}  \begin{picture}(2,5)  \thicklines  \put(0,0){\circle*{1}}  \put(1,1){\circle*{1}}  \put(0,1){\circle*{1}}  \put(1,0){\circle*{1}}  \put(2,1){\circle*{1}}  \put(2,0){\circle*{1}}  \put(0,1){\line(1,-1){1}}  \put(0,0){\line(2,1){2}}  \put(0,0){\line(1,1){1}}  \put(0,0){\line(1,0){1}}  \put(0,0){\line(0,1){1}}  \end{picture}

Advertisements
This entry was posted in Graph Theory and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s