May the source be with you, but remember the KISS principle ;-)

Contents Bulletin Scripting in shell and Perl Network troubleshooting History Humor

Graph Algorithms

Old News See Also Recommended Books Recommended Links Lecture Notes and E-books Libraries Dominators Graph Drawing

Minimum spanning trees

Shortest Path Problem Web Pages

Usage of Prolog for exploring graph problems Maximal Common Subgraph (MCS) algorithm Transitive clousure History Humor Etc

Graph theory is the study of the properties of graphs. Graph algorithms are one of the oldest classes of algorithms and they have been studied for almost 300 years (in 1736 Leonard Euler formulated one of the first graph problems Königsberg Bridge Problem, see history).

There are two large classes of graphs:

Some algorithms differ by the class. Moreover the set of problems for digraphs and undirected graphs are  different.  There are special cases of digraphs and graphs that have thier own sets of problem. One example for digraphs will be program graphs.  Program graphs are important in compiler construction and were studied in detail after the invention of the computers.

Graphs are made up of vertices and edges. The simplest property of a vertex is its degree, the number of edges incident upon it. The sum of the vertex degrees in any undirected graph is twice the number of edges, since every edge contributes one to the degree of both adjacent vertices. Trees are undirected graphs which contain no cycles. Vertex degrees are important in the analysis of trees. A leaf of a tree is a vertex of degree 1. Every $n$-vertex tree contains $n-1$ edges, so all non-trivial trees contain at least two leaf vertices.

Among classic algorithms/problems on digraphs we can note the following:

Some differences between graphs lists and trees: 

Here is a nice outline of typical problems at CSE 392 - Programming Challenges Graph Algorithms (Week 10)

Top updates

Bulletin Latest Past week Past month
Google Search


Old News ;-)

Process large-scale graph data with Apache Giraph, GraphLab, and other open source technology

Learn about Apache Giraph, GraphLab, and other open source systems for processing graph-structured big data.  More >

Problem Solving and Search in AI

This kind of problem is often solved by a graph search method. We represent the problem as a set of

which are snapshots of the world and
which transform one state into another
States can be mapped to nodes of a graph and operators are the edges of the graph. Before studying the missionaries and cannibals problem, we look at a simple graph search algorithm in Prolog. the missionaries and cannibals program will have the same basic structure.

Graph Representation

A graph may be represented by a set of edge predicates and a list of vertices.

	edge(1, 5).	edge(1, 7).
	edge(2, 1).	edge(2, 7).
	edge(3, 1).	edge(3, 6).
	edge(4, 3).	edge(4, 5).
	edge(5, 8).
	edge(6, 4).	edge(6, 5).
	edge(7, 5).
	edge(8, 6).	edge(8, 7).

	vertices([1, 2, 3, 4, 5, 6, 7, 8]).


Finding a path

	path(Start, Finish, Visited, Path).
is the name of the starting node
is the name of the finishing node
is the list of nodes already visited.
is the list of nodes on the path, including Start and Finish.

The Path Program

	path(Node, Node, _, [Node]).
	path(Start, Finish, Visited, [Start | Path]) :-
		edge(Start, X),
		not(member(X, Visited)),
		path(X, Finish, [X | Visited], Path).
Here is an example of the path algorithm in action.
Representing the state
Now we return to the problem of representing the missionaries anc cannibals problem:
	state(Missionaries, Cannibals, Side)


Representing the Solution
	[move(1, 1, right), move(2, 0, left)]


	[MostRecent_State | ListOfPreviousStates]
Overview of Solution
	state(0, 0, right).


Top-level Prolog Code
% mandc(CurrentState, Visited, Path)

mandc(state(0, 0, right), _, []).
mandc(CurrentState, Visited, [Move | RestOfMoves]) :-
	newstate(CurrentState, NextState),
	not(member(NextState, Visited)),
	make_move(CurrentState, NextState, Move),
	mandc(NextState, [NextState | Visited], RestOfMoves]).

make_move(state(M1, C1, left), state(M2, C2, right), move(M, C, right)) :-
	M is M1 - M2,
	C is C1 - C2.
make_move(state(M1, C1, right), state(M2, C2, left), move(M, C, left)) :-
	M is M2 - M1,
	C is C2 - C1.


Possible Moves
	carry(2, 0).
	carry(1, 0).
	carry(1, 1).
	carry(0, 1).
	carry(0, 2).


Feasible Moves
	M <= M1 and C <= C1


	M + M1 <= 3 and C + C1 <= 3


Legal Moves
	legal(X, X).
	legal(3, X).
	legal(0, X).
Generating the next state
newstate(state(M1, C1, left), state(M2, C2, right)) :-
	carry(M, C),
	M <= M1,
	C <= C1,
	M2 is M1 - M,
	C2 is C1 - C,
	legal(M2, C2).
newstate(state(M1, C1, right), state(M2, C2, left)) :-
	carry(M, C),
	M2 is M1 + M,
	C2 is C1 + C,
	M2 <= 3,
	C2 <= 3,
	legal(M2, C2).

The complete code, with instructions for use, is available at

Methods of Search

In the preceding example, the state space is explored in an order determined by Prolog. In some situations, it might be necessary to alter that order of search in order to make search more efficient. To see what this might mean, here are two alternative methods of searching a tree.

Depth first search begins by diving down as quickly as possible to the leaf nodes of the tree. Traversal can be done by:

There are many other search methods and variants on search methods. We do not have time to cover these in COMP9414, but you can find out about some of them in the text by Bratko. For example, chapter 12 deals with best-first search.

Some Simple Graph Problems

Consider the problem of finding connected components in a directed graph. Assume we have a node and we want to find all the nodes that are in the same connected component as the given node.

The first thought that comes to mind is: given a node X, find those nodes Y that are reachable from X and from which you can get back to X. So we will assume that edges are given by an edge/2 relation:

sameSCC(X,Y) :- reach(X,Z), reach(Z,Y).

:- table reach/2.
reach(X,Y) :- reach(X,Z), edge(Z,Y).

Indeed given a node X, this will find all nodes in the same strongly connected component as X, however it will in general take O(n*e) time, where n is the number of nodes and e is the number of edges. The reason is that given an X, there are n possible Z values and for each of them, we will find everything reachable from them, and each search can take O(e) time.

However, we can do better. It is known that this problem can be solved in O(e) time. The idea is, given a node X, to find all nodes reachable from X following edges forward. Then find all nodes reachable from X following edges backward (i.e., follow edges against the arrow.) Then intersect the two sets. That will be the set of nodes in X's SCC, because if Y is in both these sets, you can follow the edges forward from X to Y and then since there is also a backwards path from X to Y, there is forward path from Y to X, so you can get from X to Y and back to X following edges forward. So the program that does this is:

% sameSCC(+X,-Y)
sameSCC(X,Y) :- reachfor(X,Y), reachback(X,Y).

:- table reachfor/2, reachback/2.
reachfor(X,Y) :- reachfor(X,Z),edge(Z,Y).

reachback(X,Y) :- reachback(X,Z),edge(Y,Z).

Let's now consider its complexity to see why it is O(e). For a fixed value X, the computation of the query reachfor(X,Y) takes O(e) time. Then we may have O(n) calls to reachback(X,Y) (one for each Y) but they all use one underlying call to reachback(X,_) which takes O(e) and is done only once. So when we add all that up (assuming a connected graph), we get O(e) time.

SWI-Prolog 5.6.32 Reference Manual Section A.4

Authors: Richard O'Keefe & Vitor Santos Costa

Implementation and documentation are copied from YAP 5.0.1. The library(ugraph) library is based on code originally written by Richard O'Keefe. The code was then extended to be compatible with the SICStus Prolog ugraphs library. Code and documentation have been cleaned and style has been changed to be more in line with the rest of SWI-Prolog.

The ugraphs library was originally released in the public domain. YAP is convered by the Perl artistic license, which does not imply further restrictions on the SWI-Prolog LGPL license.

The routines assume directed graphs, undirected graphs may be implemented by using two edges.

Originally graphs where represented in two formats. The SICStus library and this version of library( only uses the S-representation. The S-representation of a graph is a list of (vertex-neighbors) pairs, where the pairs are in standard order (as produced by keysort) and the neighbors of each vertex are also in standard order (as produced by sort). This form is convenient for many calculations. Each vertex appears in the S-representation, also if it has no neighbors.

vertices_edges_to_ugraph(+Vertices, +Edges, -Graph)
Given a graph with a set of Vertices and a set of Edges, Graph must unify with the corresponding S-representation. Note that the vertices without edges will appear in Vertices but not in Edges. Moreover, it is sufficient for a vertice to appear in Edges.
?- vertices_edges_to_ugraph([],[1-3,2-4,4-5,1-5], L).
L = [1-[3,5], 2-[4], 3-[], 4-[5], 5-[]]

In this case all vertices are defined implicitly. The next example shows three unconnected vertices:

?- vertices_edges_to_ugraph([6,7,8],[1-3,2-4,4-5,1-5], L).
L = [1-[3,5], 2-[4], 3-[], 4-[5], 5-[], 6-[], 7-[], 8-[]] ? 
vertices(+Graph, -Vertices)
Unify Vertices with all vertices appearing in graph Graph. Example:
?- vertices([1-[3,5],2-[4],3-[],4-[5],5-[]], L).
L = [1, 2, 3, 4, 5]
edges(+Graph, -Edges)
Unify Edges with all edges appearing in Graph. In the next example:
?- edges([1-[3,5],2-[4],3-[],4-[5],5-[]], L).
L = [1-3, 1-5, 2-4, 4-5]
add_vertices(+Graph, +Vertices, -NewGraph)
Unify NewGraph with a new graph obtained by adding the list of Vertices to the Graph. Example:
?- add_vertices([1-[3,5],2-[]], [0,1,2,9], NG).
NG = [0-[], 1-[3,5], 2-[], 9-[]]
del_vertices(+Vertices, +Graph, -NewGraph)
Unify NewGraph with a new graph obtained by deleting the list of Vertices and all the edges that start from or go to a vertex in Vertices to the Graph. Example:
?- del_vertices([2,1],
NL = [3-[],4-[5],5-[],6-[],7-[6],8-[]]
add_edges(+Graph, +Edges, -NewGraph)
Unify NewGraph with a new graph obtained by adding the list of edges Edges to the graph Graph. Example:
?- add_edges([1-[3,5],2-[4],3-[],4-[5],5-[],6-[],7-[],8-[]],
NL = [1-[3,5,6], 2-[3,4], 3-[2], 4-[5], 5-[7], 6-[], 7-[], 8-[]]
del_edges(+Graph, +Edges, -NewGraph)
Unify NewGraph with a new graph obtained by removing the list of Edges from the Graph. Notice that no vertices are deleted. In the next example:
?- del_edges([1-[3,5],2-[4],3-[],4-[5],5-[],6-[],7-[],8-[]],
NL = [1-[5],2-[4],3-[],4-[],5-[],6-[],7-[],8-[]]
transpose(+Graph, -NewGraph)
Unify NewGraph with a new graph obtained from Graph by replacing all edges of the form V1-V2 by edges of the form V2-V1. The cost is O(|V|^2). Notice that an undirected graph is its own transpose. Example:
?- transpose([1-[3,5],2-[4],3-[],4-[5],5-[],6-[],7-[],8-[]], NL).
NL = [1-[],2-[],3-[1],4-[2],5-[1,4],6-[],7-[],8-[]]
neighbours(+Vertex, +Graph, -Vertices)
Unify Vertices with the list of neighbours of vertex Vertex in Graph. Example:
?- neighbours(4,[1-[3,5],2-[4],3-[],
                 4-[1,2,7,5],5-[],6-[],7-[],8-[]], NL).
NL = [1,2,7,5]
neighbors(+Vertex, +Graph, -Vertices)
American version of neighbours/3.
complement(+Graph, -NewGraph)
Unify NewGraph with the graph complementary to Graph. Example:
?- complement([1-[3,5],2-[4],3-[],
               4-[1,2,7,5],5-[],6-[],7-[],8-[]], NL).
NL = [1-[2,4,6,7,8],2-[1,3,5,6,7,8],3-[1,2,4,5,6,7,8],
compose(+LeftGraph, +RightGraph, -NewGraph)
Compose, by connecting the drains of LeftGraph to the sources of RightGraph. Example:
?- compose([1-[2],2-[3]],[2-[4],3-[1,2,4]],L).
L = [1-[4], 2-[1,2,4], 3-[]]
ugraph_union(+Graph1, +Graph2, -NewGraph)
NewGraph is the union of Graph1 and Graph2. Example:
?- ugraph_union([1-[2],2-[3]],[2-[4],3-[1,2,4]],L).
L = [1-[2], 2-[3,4], 3-[1,2,4]]
top_sort(+Graph, -Sort)
Generate the set of nodes Sort as a topological sorting of graph Graph, if one is possible. A toplogical sort is possible if the graph is connected and acyclic. In the example we show how topological sorting works for a linear graph:
?- top_sort([1-[2], 2-[3], 3-[]], L).
L = [1, 2, 3]
top_sort(+Graph, -Sort0, -Sort)
Generate the difference list Sort-Sort0 as a topological sorting of graph Graph, if one is possible.
transitive_closure(+Graph, -Closure)
Generate the graph Closure as the transitive closure of graph Graph. Example:
 ?- transitive_closure([1-[2,3],2-[4,5],4-[6]],L).
L = [1-[2,3,4,5,6], 2-[4,5,6], 4-[6]]
reachable(+Vertex, +Graph, -Vertices)
Unify Vertices with the set of all vertices in graph Graph that are reachable from Vertex. Example:
?- reachable(1,[1-[3,5],2-[4],3-[],4-[5],5-[]],V).
V = [1, 3, 5]

SICStus Prolog

[PDF] CS 526 Topic 2: History and Perspective

File Format: PDF/Adobe Acrobat - View as HTML
The Dominator Graph. Lemma 4:. The dominators of a node form a chain. ... Finding Dominators in A Flow Graph. Input : A flow graph G = (N, As). ... cs526/Notes/3controlflow.4up.pdf - Similar pages

[PS] On Loops, Dominators, and Dominance Frontiers G. RamalingamIBM TJ ...

File Format: Adobe PostScript - View as HTML
A simple and optimal algorithm for finding immediate dominators inreducible graphs. Technical Report D-261/96, TOPPS Bibliography, 1996. ... Similar pages

Graphs, Euler and Hamilton circuits

The subject we now call graph theory, and perhaps the wider topic of topology,  was founded on the work of Leonhard Euler, and a single famous problem called the Seven Bridges problem. Probably the first paper on graph theory was by Euler. In 1736 he wrote Solutio problematis ad geometriam situs pertinentis, Commetarii Academiae Scientiarum Imperialis Petropolitanae which translates into English as "The solution of a problem relating to the geometry of position." Euler was one of the first to expand geometry into problems that were independent of measurement. In the paper Euler discusses what was then a trendy local topic, whether or not it is possible to stroll around Konigsberg (now called Kaliningrad) crossing each of its bridges across the Pregel River exactly once. Euler generalized the problem and gave conditions which would solve any such stroll. You can see a map of the actual seven bridges of  Konigsberg at this site at St. Andrews Univ.

Graph Theory

The development of graph theory is very similar the development of probability theory, where much of the original work was motivated by efforts to understand games of chance. The large portions of graph theory have been motivated by the study of games and recreational mathematics. Generally speaking, we use graphs in two situations. Firstly, since a graph is a very convenient and natural way of representing the relationships between objects we represent objects by vertices and the relationship between them by lines. In many situations (problems) such a pictorial representation may be all that is needed. Example of such applications are chemical molecule and map coloring as shown in the diagrams below. Other examples are signal-flow graphs, Konigsberg bridges, tracing maze etc.

[PDF] Combinatorica: A System for Exploring Combinatorics and Graph ...
File Format: PDF/Adobe Acrobat - View as HTML

Kernels in planar digraphs

For a plane digraph the kernel number is the minimum number of faces to be deleted (i.e., the vertices of the boundary) such that the remaining digraph has a kernel. We show that determining whether the kernel number is at most some constant $k$ is NP-complete for every $k\geq 0$.

Graph Theory Lessons

Report 031-2004 A Greedy Approach to Compute a Minimum Cycle Bases of a Directed Graph by Christian Liebchen and Romeo Rizzi

We consider the problem of computing a minimum cycle basis of a directed graph with m arcs and n nodes. We adapt the greedy approach proposed by Horton and hereby obtain a very simple exact algorithm of complexity O(m4n), being as fast as the first algorithm proposed for this problem. Moreover, the speed-up of Golynski and Horton applies to this problem, providing an exact algorithm of complexity O(mωn), in particular O(m3.376n). Finally, we prove that these greedy approaches fail for more specialized subclasses of directed cycle bases.

Report 019-2004  Complexity and Approximability of k-splittable flow problems

We consider s,t-flow problems in connected graphs with the additional requirement that one can decompose the flow into at most k paths for a given number k. Such flows are called k-splittable flows. In the multi-commodity case they generalize unsplittable flows. In this paper, we consider the problem MkSF, which means to find a maximum k-splittable s,t-flow. We show complexity and approximability results for this problem depending on k. Results work for directed and undirected graphs. Firstly, we show that for all constant integer k > 1 MkSF is strongly NP-hard and cannot be approximated with a guarantee better than 5/6. This is the first constant bound for the non-approximability of this problem. Secondly, we study MkSF with k depending on m, the number of edges, and n, the number of nodes of the graph. We prove that MkSF is NP-hard for 2 <= k <= m-n+1. We show that it is polynomially solvable for k >= m-n+2. Thus, there is no gap in the analysis. For the special case of simple graphs we show that MkSF is polynomially solvable for k = m - c for each integer constant c. That also holds for k=m-(log log p(m,n))^eps for every polynom p in n and m, eps in (0,1). It is well known that every flow in a graph can be decomposed into at most m paths and cycles. We show as a general result that the number of paths in such a decomposition can always be limited to m - n + 2.

JGAA Volume 1, 1997

JGAA Volume 3, 1999

JGAA Volume 4, 2000

JGAA Volume 5, 2001

JGAA Volume 7, 2003

Class notes CS251B -- Winter 1997 Topic #28: MINIMUM SPANNING TREES

Citations Experimental analysis of dynamic minimum spanning tree algorithms - Amato, Cattaneo, Italiano (ResearchIndex)

Maintaining Shortest Paths in Digraphs with.. - Demetrescu.. (2000)   (4 citations) 

....the fully dynamic single source shortest paths problem in digraphs with positive real arc weights. We are not aware of any experimental study in the case of arbitrary arc weights. On the other hand, several papers report on experimental works concerning different dynamic graph problems (see e.g. [2, 3, 11]) In this paper we make a step toward this direction and we present the first experimental study of the fully dynamic single source shortest paths problem in digraphs with arbitrary (negative and non negative) arc weights. We implemented and experimented several algorithms for updating shortest ....

G. Amato, G. Cattaneo, and G. F. Italiano. Experimental analysis of dynamic minimum spanning tree algorithms. In ACM-SIAM Symp. on Discrete Algorithms, pp. 1--10, 1997.

Journal of Graph Algorithms and Applications now has electronic edition

Scalable Libraries for Graph Partitioning School of Information Studies, Syracuse University

The key problem in efficiently executing irregular and unstructured data parallel applications is partitioning the data to minimize communication while balancing the load. Partitioning such applications can be posed as a graph-partitioning problem based on the computational graph. We are currently developing a library of partitioners (especially based on physical optimization) which aim to find good suboptimal solutions in parallel. The initial target use of these partitioning methods are for runtime support of data parallel compilers (HPF).

An Introduction to Graph Algorithms by Ute Loerch, Department of Computer Science, University of Auckland, Auckland, New Zealand, 

These lecture notes contain the reference material on graph algorithms for the course: Algorithms and Data Structures (415.220FT) and are based on Dr Michael Dinneen's lecture notes of the course 415.220SC given in 1999. Topics include computer representations (adjacency matrices and lists), graph searching (BFS and DFS), and basic graph algorithms such as computing the shortest distances between vertices and finding the (strongly) connected components.

Advanced Topics in Graph Algorithms

Recommended Links

Softpanorama Top Visited

Softpanorama Recommended

Shortest Path

Shortest Path Problem Web Pages

Graph Drawing

Graph Drawing Tools

Graph Drawing Research Group

GDR A Visualization Tool for Graph Algorithms

GraphEd -- Graph Editor and Layout Program

Maximal Common Subgraph (MCS) algorithm

Maximal Common Subgraph (MCS) algorithm

Transitive Closure

Transitive Closure of a Graph - Warshall's Algorithm

Graphs- Transitive Closure

Transitive closure algorithms based on graph traversal

[PDF] Digraphs Outline and Reading Digraphs Directed DFS Transitive ...

Perl: TransitiveClosure

Efficient transitive closure computation in large digraphs
... components. The representation generalizes a previous method for compressing
the transitive closure of an acyclic graph. The new ...

1.4.5 Transitive Closure and Reduction

Find Transitive Closure of Parent-Child Relationship in Oracle9i

Boost Graph Library: Transitive Closure

Citebase - Mantaining Dynamic Matrices for Fully Dynamic ...

PPT] Chapter 9: More Graph Algorithms

Transitive Closure -- from MathWorld

Transitive Closure and Reduction

LEDA Guide- Transitive Closure and Transitive Reduction


Joseph Culberson's Graph Coloring Resources Page


LEDA moved to Algorithmic Solutions Software GmbH

LEDA Combinatorial and Graph Algorithms


The Stony Brook Algorithm Repository

Pearson Books - Boost Graph Library, The


"Euler's proof of the nonexistence of a so-called Eulerian (i.e., closed) path across all seven bridges of Königsberg, now known as the Königsberg bridge problem, is a famous precursor to graph theory. In fact, the study of various sorts of paths in graphs (e.g., Euler paths, Eulerian circuits, Hamiltonian paths, and Hamiltonian circuits) has many applications in real-world problems." (Eric W. Weisstein. "Graph." From MathWorld--A Wolfram Web Resource. ) See also Wilson, Robin J.: "200 years of graph theory---a guided tour" Theory and applications of graphs (Proc. Internat. Conf., Western Mich. Univ., Kalamazoo, Mich., 1976), pp. 1--9. Lecture Notes in Math., Vol. 642, Springer, Berlin, 1978. MR58 #15981.

A longer version appeared in book form: Biggs, Norman L.; Lloyd, E. Keith; Wilson, Robin J.: "Graph theory: 1736--1936" Clarendon Press, Oxford, 1976. 239 pp. MR56#2771 

Seven Bridges of Königsberg - Wikipedia, the free encyclopedia

Department of Mathematics The Bridges of Konigsburg

Königsburg was founded by the Teutonic Knights in 1255 at the meeting point of two branches of the river Pregel, and went on to be the capital of Prussia. It was flattened by bombing raids during the Second World War, and was annexed by the Soviet Union in 1945, at which stage it was renamed Kaliningrad. Today, it is in the small Russian parcel of land on the Baltic Sea that is wedged between Lithuania and Northeastern Poland.

Many famous figures in history were born in Königsburg, including the philosopher Immanuel Kant, the mathematicians Christian Goldbach and David Hilbert, and the physicist Gustav Kirchhoff. To mathematicians, though, Königsburg is best known for a puzzle associated with its seven bridges (shown in blue on the map): its citizens pondered for a long time whether it was possible to walk about the city in such a way that you cross all seven bridges over the river Pregel exactly once.

Leonhard EulerThis might seem like a fun but inconsequential problem. However it was the inspiration for a 1736 paper by the great Swiss mathematician Leonhard Euler (1707-1783) which arguably began the field of topology. In this paper, Euler proved that there was no such path around the city. In fact Euler gives a simple criterion which determines whether or not there is a solution to any similar problem with any number of bridges connecting any number of landmasses!

Euler first simplified the problem, replacing each landmass by a vertex (yellow dot) and each bridge by an arc (black path). Such a configuration of vertices and connecting arcs is nowadays known as a graph. The original problem is equivalent to the problem of travelling around the graph in such a way that you cross each arc exactly once. Defining the degree of a vertex to be the number of arcs that lead to it, Euler proved:

Theorem There exists a (at least one) path on a graph which travels along each arc exactly once if and only if the graph has at most two vertices of odd degree.

Königsberg Bridge Problem -- From MathWorld

Graphs History - Graphs Information

Graph theory had its origins in a seminal 1736 contribution of the famous Swiss mathematician Leonhard Euler, who was then living in Germany. In Königsberg, Germany, the Pregel 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. People who lived in the area wondered whether it was possible to traverse each of the bridges exactly once and return to one's starting point. This remained an open question for many years; no one had been able to show how to do it, but none had a proof that it wasn't possible, either. Euler's analysis came up with the answer, which was in the negative.

Euler's insight was in reducing the concrete problem of the bridges over the Pregel at Königsberg into an abstract representation using a graph. He considered that the situation of the bridges could be abstracted to a graph having four points connected in a certain way with seven edges. He then had to analyze whether it was possible to traverse the edges of the graph once each, so as to return to the point from whence one began. Such a path is now called, in his honor, an Eulerian path, and the criterion he evolved for the existence of such a path in a graph allowed for a simple proof to show why it was not possible to solve the Königsberg Bridge Problem, which is now given as an introduction to most graph theory texts.

After the solution to this problem by Euler, the study of graph theory was strangely relegated to the back burner for over two hundred years, but the period after the second world war saw a great increase in interest, motivated to a great extent by the rapid pace of research in the sciences, as well as the needs of the industry. 

Graph Theory

The origin of graph theory can be traced back to Euler's work on the Konigsberg bridges problem (1735), which subsequently led to the concept of an Eulerian graph. The study of cycles on polyhedra by the Thomas P. Kirkman (1806 - 95) and William R. Hamilton (1805-65) led to the concept of a Hamiltonian graph.

The concept of a tree, a  connected graph without cycles, appeared implicitly in the work of Gustav Kirchhoff (1824-87), who employed graph-theoretical ideas in the calculation of currents in electrical networks or circuits. Later, Arthur Cayley (1821-95), James J. Sylvester(1806-97), George Polya(1887-1985), and others use 'tree' to enumerate chemical molecules.

The study of planar graphs originated in two recreational problems involving the complete graph K5 and the complete bipartite graph K3,3. These graphs proved to be planarity, as was subsequently demonstrated by Kuratowski. First problem was presented by A. F. Mobius around the year 1840 as follows

Once upon a time, there was a king with five sons.
In his will  he stated  that  after  his  death the sons
should  divide  the  kingdom into  five provinces so
that  the  boundary  of  each  province should have
a  frontiers  line  in  common with each of the other
four provinces.

Here the problem  is whether one can draw five mutually neighboring regions in the plane.

The king further stated that all five brothers should
join  the provincial capital by roads so that no two
roads intersect. 

Here the problem is that deciding whether the graph K5 is planar.

The origin of second problem is unknown but it is first mentioned by H. Dudeney in 1913 in its present form.

The puzzle is to lay a water, gas, and electricity
to  each  of  the  three  houses without any pipe
crossing another.

This problem is that of deciding whether the graph K3,3 is planar.

The celebrated four-color problem was first posed by Francis Guthrie in 1852. and a celebrated incorrect "proof" by appeared in 1879 by Alfred B. Kempe. It was proved by Kenneth Appel and Wolfgang Haken in 1976 and a simpler and more systematic proof was produced by Neil Roberton, Daniel Sanders, Paul Seymour, and Robin Thomas in 1994.


The Graph Theory Hymn


English text by DONALD A. PREECE

Seven bridges spanned the River Pregel,
Many more than might have been expected;
Königsberg's wise leaders were delighted
To have built such very splendid structures.

Crowds each ev'ning surged towards the river,
People walked bemused across the bridges,
Pondering a simple-sounding challenge
Which defeated them and left them puzzled.

Here's the problem; see if you can solve it!
Try it out at home an scraps of paper!

Eulerian graphs all have this restriction:
That's the oldest graph result
That mankind has ever known.

All the folk in Königsberg were frantic!
All their efforts ended up in failure!
Happily, a learn-ed math'matician
Had his house right there within the city.

Euler's mind was equal to the problem:
"Ah", he said, "You're bound to be disheartened.
Crossing each bridge only once per outing
Can't be done, I truly do assure you."

Eulerian graphs …

Laws of Nature never can be altered,
We can'd change them, even if we wish to.
Nor can flooded rivers or great bridges
Interfere with scientific progress.

War brought strife and ruin to the Pregel;
Bombs destroyed those seven splendid bridges.
Euler's name and fame will, notwithstanding,
Be recalled with Königsberg's for ever.

Eulerian graphs …

Thanks to Euler, Graph Theory is thriving.
Year by year it flourishes and blossoms,
Fertilising much of mathematics
And so rich in all its applications.

Colleagues, let us fill up all our glasses!
Colleagues, let us raise them now to toast the
Greatness and the everlasting glory
Of our Graph Theory, which we love dearly!




Groupthink : Understanding Micromanagers and Control Freaks : Toxic Managers : BureaucraciesHarvard Mafia : Diplomatic Communication : Surviving a Bad Performance Review : Insufficient Retirement Funds as Immanent Problem of Neoliberal Regime : PseudoScience : Who Rules America : Two Party System as Polyarchy : Neoliberalism  : The Iron Law of Oligarchy : Libertarian Philosophy


Skeptical Finance : John Kenneth Galbraith : Keynes : George Carlin : Skeptics : Propaganda  : SE quotes : Language Design and Programming Quotes : Random IT-related quotes : Oscar Wilde : Talleyrand : Somerset Maugham : War and Peace : Marcus Aurelius : Eric Hoffer : Kurt Vonnegut : Otto Von Bismarck : Winston Churchill : Napoleon Bonaparte : Ambrose Bierce : Oscar Wilde : Bernard Shaw : Mark Twain Quotes


Vol 26, No.1 (January, 2013) Object-Oriented Cult : Vol 25, No.12 (December, 2013) Rational Fools vs. Efficient Crooks: The efficient markets hypothesis : Vol 25, No.08 (August, 2013) Cloud providers as intelligence collection hubs : Vol 23, No.10 (October, 2011) An observation about corporate security departments : Vol 23, No.11 (November, 2011) Softpanorama classification of sysadmin horror stories : Vol 25, No.05 (May, 2013) Corporate bullshit as a communication method : Vol 25, No.10 (October, 2013) Cryptolocker Trojan (Win32/Crilock.A) : Vol 25, No.06 (June, 2013) A Note on the Relationship of Brooks Law and Conway Law


Fifty glorious years (1950-2000): the triumph of the US computer engineering : Donald Knuth : TAoCP and its Influence of Computer Science : Richard Stallman : Linus Torvalds  : Larry Wall  : John K. Ousterhout : CTSS : Multix OS Unix History : Unix shell history : VI editor : History of pipes concept : Solaris : MS DOSProgramming Languages History : PL/1 : Simula 67 : C : History of GCC developmentScripting Languages : Perl history   : OS History : Mail : DNS : SSH : CPU Instruction Sets : SPARC systems 1987-2006 : Norton Commander : Norton Utilities : Norton Ghost : Frontpage history : Malware Defense History : GNU Screen : OSS early history

Classic books:

The Peter Principle : Parkinson Law : 1984 : The Mythical Man-MonthHow to Solve It by George Polya : The Art of Computer Programming : The Elements of Programming Style : The Unix Hater’s Handbook : The Jargon file : The True Believer : Programming Pearls : The Good Soldier Svejk : The Power Elite

Most popular humor pages:

Manifest of the Softpanorama IT Slacker Society : Ten Commandments of the IT Slackers Society : Computer Humor Collection : BSD Logo Story : The Cuckoo's Egg : IT Slang : C++ Humor : ARE YOU A BBS ADDICT? : The Perl Purity Test : Object oriented programmers of all nations : Financial Humor : Financial Humor Bulletin, 2008 : Financial Humor Bulletin, 2010 : The Most Comprehensive Collection of Editor-related Humor : Programming Language Humor : Goldman Sachs related humor : Greenspan humor : C Humor : Scripting Humor : Real Programmers Humor : Web Humor : GPL-related Humor : OFM Humor : Politically Incorrect Humor : IDS Humor : "Linux Sucks" Humor : Russian Musical Humor : Best Russian Programmer Humor : Microsoft plans to buy Catholic Church : Richard Stallman Related Humor : Admin Humor : Perl-related Humor : Linus Torvalds Related humor : PseudoScience Related Humor : Networking Humor : Shell Humor : Financial Humor Bulletin, 2011 : Financial Humor Bulletin, 2012 : Financial Humor Bulletin, 2013 : Java Humor : Software Engineering Humor : Sun Solaris Related Humor : Education Humor : IBM Humor : Assembler-related Humor : VIM Humor : Computer Viruses Humor : Bright tomorrow is rescheduled to a day after tomorrow : Classic Computer Humor


The Last but not Least

Copyright © 1996-2014 by Dr. Nikolai Bezroukov. was created as a service to the UN Sustainable Development Networking Programme (SDNP) in the author free time. This document is an industrial compilation designed and created exclusively for educational use and is distributed under the Softpanorama Content License. Site uses AdSense so you need to be aware of Google privacy policy. Original materials copyright belong to respective owners. Quotes are made for educational purposes only in compliance with the fair use doctrine. This is a Spartan WHYFF (We Help You For Free) site written by people for whom English is not a native language. Grammar and spelling errors should be expected. The site contain some broken links as it develops like a living tree...

You can use PayPal to make a contribution, supporting hosting of this site with different providers to distribute and speed up access. Currently there are two functional mirrors: (the fastest) and


The statements, views and opinions presented on this web page are those of the author and are not endorsed by, nor do they necessarily reflect, the opinions of the author present and former employers, SDNP or any other organization the author may be associated with. We do not warrant the correctness of the information provided or its fitness for any purpose.

Last modified: February 19, 2014