Jim Keenan IST 230.2

Current Affairs Assignment

The Eulerian Cycle and the Konigsberg Bridge Problem

In this web page I plan on explaining some of the basic concepts of the graph theory and its applications. I also provided concise historical facts about Leonard Euler, who discovered these principals. I found a problem for each of the two ideas and I structured it to make it easier to understand for the class. These mathematical concept relate to IST class because they lay the foundation for the design of network topologies. We learned earlier about the importance of minimun spanning trees and the shortest and most reliable route to a desired source.

The Eulerian Cycle

There are well-known conditions for determining whether a graph contains an Eulerian cycle, or path: An undirected graph contains an Eulerian cycle if and only if (1) it is connected and

(2) each vertex is of even degree. An undirected graph contains an Eulerian path if and only if

(1) it is connected and

(2) all but two vertices are of even degree. These two vertices will be the start and end points of the path. A directed graph contains an Eulerian cycle if and only if

(1) it is connected and

(2) each vertex has the same in-degree as out-degree. Finally, a directed graph contains an Eulerian path if and only if

(1) it is connected and

(2) all but two vertices have the same in-degree as out-degree, and these two vertices have their in-degree and out-degree differ by one.

Suppose you are given the map of a city and told to design a route for snow plows. However, every road in the city must be completely plowed at least once in order to ensure that all snow is removed. The basic blueprints of the town look like this.

Input description: A graph G=(V,E).>

Problem description: Find the shortest tour of G visiting each edge at least once.For efficiency, you need to minimize total drive time, and the total distance or number of edges crossed. The correct output is... because as you can see, each "street is plowed by only once and the whole route is covered. This is also an Eulerian Circuit.

The Konisberg Bridge Problem

This problem inspired the great Leonard Euler to create graph theory, which led to the development of topology.

In Konigsberg, Germany, a river ran through the city such that in its center was an island, and after passing the island, the river broke into two parts. Seven bridges were built so that the people of the city could get from one part to another. A crude map of the center of Konigsberg might look like this:

For fun, the people wondered whether or not one could walk around the city in a way that would involve crossing each bridge exactly once. Now you can try to sketch it out on a piece of paper and without removing your pencil tip from the paper, your pathetic attempts might look something like this.

RRRRRight, so now what. Well, Euler found out that the problem was because of the odd number of bridges. Euler realized that all problems of this form could be represented by replacing areas of land by points (he called them vertices), and the bridges to and from them by arcs. For Konigsberg, let's represent land with red dots and bridges with black curves:

In its naked version the Konigsberg Problem looks like this:

Therefore the problem now becomes one of drawing this picture without retracing any line and without picking your pencil up off the paper. All four of the vertices in the above picture have an odd number of arcs connected to them. Take one of these vertices, say one of the ones with three arcs connected to it. Say you're going along, trying to trace the above figure out without picking up your pencil. The first time you get to this vertex, you can leave by another arc. But the next time you arrive, you can't. So you'd better be through drawing the figure when you get there! Alternatively, you could start at that vertex, and then arrive and leave later. But then you can't come back. Thus every vertex with an odd number of arcs attached to it has to be either the beginning or the end of your pencil-path. So you can only have up to two 'odd' vertices! It is impossible to draw the above picture in one pencil stroke without retracing.

Further Resources Definition of Eulerian Cycle The Konigsberg Bridge Problem Applications of Combinatorics Interactive Introduction to Graph Theory