Intro DS: Graphs
Pre-requisite Skill: How to Transpose a Matrix
TED Video on How Graph Theory Started
The Seven Bridges of Konigsberg
The image below shows the city of Konigsberg, Prussia (now Russia) in 1736.
The green, hot-dog-shaped structures are bridges over the river Pregel. The famous mathematician, Leonard Euler was asked if it was possible for a tourist to walk across every bridge exactly once. In his analysis, Euler is said to have discovered that the graph theory to solve this seemingly simple problem had not yet been developed ... so he developed it. Later, in this course, we will go over his solution. For now, we will simply formulate the problem and go over some definitions of graphs.
The first thing that Euler realized in attempting to analyze this problem is that an abstract diagram of the situation would be much more helpful than that of the original map shown, above:
In this diagram, the details of the city have been abstracted away because they are not needed for the analysis of the problem. But we can go further than this once we realize that the size of the land masses are not important either. Here is an even more abstract diagram of the city:
Notice that the land masses have been replaced by green circles (the graph's verticies or nodes) while the bridges are now represented by the yellow line segments (the graph's edges) emanating from each land mass. Notice that each vertex has also been labeled with a number for easy reference. What we have now drawn is an undirected graph. We say it is undirected because each bridge can be traversed in both directions. If they bridges were to be made one-way, we would use arrows to denote their direction. For that case, the graph would be a directed graph (see picture, below). In our picture (above), each land mass, represented by an equally-sized, green circle, represents a vertex of our graph. Each bridge, shown by a yellow line segment, is an edge on our graph.
The use of a graph can facilitate the formulation of many different types of problems in mathematics and business. Often distances (or costs) are assigned to each edge. Shown below is a directed graph with costs depicted on each edge, and the verticies labeled with letters. Verticies are more often labeled with numbers when analyzing graphs in a computer program. For the types of problems we will be doing in this course, we will assume that the costs for traveling from one edge to another will be non-negative.
Some Graph Definitions
DegreeIn a graph, the degree of a vertex is the number of edges connected to that vertex (with loops counting twice). In the graph below, the degree of each vertex is shown by the number in the circle. In this course, you will only be asked to
calculate the degrees for vertices of an undirected graph.
Definition of Simple Graphs
Simple graphs have the following properties:
- They are undirected;
- They have no weights;
- They have no loops;
- None of the verticies have duplicate edges;
One final type of graph we wish to discuss is the concept of a complete graph. In such a graph, each vertex is connected by an edge to every other vertex. The following picture, taken from Wikipedia, shows some complete graphs of varying sizes (different numbers of verticies). Note that completed graphs are always simple graphs.
The concept of a complete graph will be important to us when we describe the "Big-O" efficiency of the Dijkstra Algorithm in our more detailed look at graph theory later in this course.
Programatic Implementations of Graphs
Now watch this video to understand the advantages and disadvantages of the following three programatic implementations of graphs:
- Dual Array
- Adjacency Matrix
- Adjacency List
Multiple Choice Question: