As the name implies, Graph Theory is a branch of mathematics which deals with Graph. Then you may ask what is graph ? If you think about the graph that is like charts as you see in Excel spreadsheet, function plot as you see in middle school or high school math text book or those charts showing stock price changes etc, you are completely on a wrong track. The "graph" in Graph Theory is 'a bunch of dots connected each other with a bunch of lines or arrow"

This page builds that idea in four steps. First, we'll see what a graph looks like and what its dots and lines mean. Then we'll turn a real map, the bridges of Konigsberg, into a graph and see the question that started graph theory. After that, we'll write the same graph as a matrix, which is how a computer stores it. Finally, we'll look at where engineers use graphs. The terms used here are collected on the Terminology page.

• What does a graph look like ?
• How does the Konigsberg bridge map become a graph ?
• How is a graph written as a matrix ?
• Where are graphs used in engineering ?
• Video Digest

What does a graph look like ?

The word graph has two meanings in math, and mixing them up is the most common first mistake. The picture below puts the wrong meaning and the right meaning side by side, so you can see the difference before we define anything.

Figure 1. A graph in graph theory is a set of dots joined by lines or arrows. A bar chart, a function plot and a stock chart are not graphs in this sense.

Then the next question you would have would be "what is the meaning of those dots and lines in a graph ?". Simply put, 'Dot' represents an 'object' or 'entity', 'line' or 'arrow' indicates the relationship between the dots (objects).

Look at the graph at the bottom of Figure 1. Some connections are plain lines, and others are arrows. A plain line means the relationship works both ways, like a two way road. An arrow means it works in one direction only, like a one way street or a link from one web page to another. The position of the dots and the length of the lines carry no meaning. Only which dots are connected, and how, matters.

• A graph is about connections, not coordinates : you can move the dots anywhere on the page, and it is still the same graph as long as the same pairs stay connected.
• Lines and arrows are different relationships : a graph with lines is undirected, and a graph with arrows is directed.

How does the Konigsberg bridge map become a graph ?

Graph theory started with a puzzle about a real city. In 1736, Leonhard Euler studied whether a person could walk through Konigsberg and cross each of its seven bridges exactly once. To answer it, he removed everything on the map except the land areas and the bridges. That step is exactly what turns a map into a graph.

The most famous example of a Graph is from Konigsberg brige as illustrated below. A, B, C, D indicates a town (village) in and around a river. The white path (e.g, c-c, d-d, e-e etc) across the river indicate brigdes across the reiver.

Figure 2. The Konigsberg map. Four land areas, A to D, are joined by seven bridges, a to g.

Now let's replace the name of the town (A,B,C,D) with Dots (red dots shown below) and connecting these dots as (1) below. And then let's remove the map in the background in (1) and now you have only dots and connecting lines as shown in (2). If you make the lines a little bit smoother, then you would get a common graph you would see in a textbook. This is how a graph is created.

Figure 3. From map to graph. Each land area becomes a dot and each bridge becomes a line, so the final graph has 4 vertices and 7 edges.

In forrmal Graph theory, we call the dot as a Vertex and call the line as Edge.

The most important thing in any type of Graph analysis is to clearly define (understand) the meaning of the Vertice and Edges in the graph. This meaning differs in every graph, so you would need a lot of practice of interpreting the meaning of dots and lines in various types of graph.

What is the meaning of the Vertex and Edge of the example shown above ? It is as follows :

• Vertex (Dots) : Name of Town (Village)
• Edge (Lines) : Path over a bridge connecting two towns.

Now we can answer Euler's question with the graph alone. Count the edges at each vertex. This count is called the degree. From Figure 2, A has five bridges, a, b, c, d and e. B has three, a, b and f. C has three, c, d and g. D has three, e, f and g. So the degrees are 5, 3, 3 and 3.

Every time a walker arrives at a land area in the middle of the walk, the walker must leave it again by another bridge. So the bridges at a middle stop are used in pairs, and the degree of that stop must be even. Only the start and the end of the walk can have an odd degree. Konigsberg has four land areas with an odd degree, so no such walk exists. This was Euler's answer, and it is usually counted as the start of graph theory.

• The graph keeps only what the question needs : the shape of the river and the length of the bridges do not matter for this question, so they are removed.
• Two bridges between the same areas are two edges : A and B are joined by two edges, and so are A and C. A graph that allows this is called a multigraph.
• Degrees decide the walk : a walk that crosses every edge exactly once needs zero or two vertices of odd degree. Konigsberg has four.

How is a graph written as a matrix ?

A picture is good for people, but a program needs numbers. The usual way to store a graph is the adjacency matrix. It has one row and one column for each vertex, and entry (i, j) counts the edges between vertex i and vertex j.

For the Konigsberg graph, with the vertex order A, B, C, D, the adjacency matrix is shown in the table below. The 2 between A and B stands for bridges a and b. The 2 between A and C stands for bridges c and d.

Three properties are visible in the table. First, the matrix is symmetric, because a bridge from A to B is also a bridge from B to A. A directed graph gives a matrix that is not symmetric. Second, each row sum is the degree of that vertex, so the degrees 5, 3, 3 and 3 come straight out of the matrix. Third, all entries add up to 14, which is twice the number of edges, because each edge appears once in each of its two rows. The Adjacency Matrix page shows more examples.

• Undirected graph, symmetric matrix : entry (i, j) equals entry (j, i).
• Row sum = degree : the matrix gives the Euler test directly. Count the rows with an odd sum.
• Once a graph is a matrix, linear algebra applies : for example, entry (i, j) of the matrix raised to the power k counts the walks of length k from vertex i to vertex j.

Where are graphs used in engineering ?

Once you start looking for vertices and edges, you find them in most engineering systems. The hard part is the step the page stressed above: deciding what a vertex means and what an edge means in your problem. The same graph algorithms then work on all of them.

In a communication network, routers or base stations are the vertices and links are the edges. Each edge can carry a weight such as delay or cost, and routing protocols such as OSPF compute the shortest path over this weighted graph. In an electric circuit, the nodes are vertices and the components are edges, and Kirchhoff's laws are written over the loops and nodes of that graph. In a social network, people are vertices and friendships are edges, while on the web, pages are vertices and links are directed edges. The graph database Neo4J in the videos below stores data in exactly this form.

Cellular networks give one more example. Neighboring cells should not use the same PCI or the same frequency. Let's make each cell a vertex and each neighbor relation an edge. Then choosing the values is a graph coloring problem: each vertex gets a color, and two vertices joined by an edge must get different colors.

• First define the vertex and the edge : the same algorithm gives a useful answer only when this mapping matches the question.
• Weights turn a graph into a network : delay, cost or capacity on each edge makes shortest path and maximum flow questions possible.
• Many planning tasks are coloring problems : PCI and frequency planning ask for different values on neighboring vertices.

Video Digest

The videos below are grouped by depth. The short clips give the basic picture from this page. The lectures go further into applications, from graph databases to the statistics of social networks.