Softpanorama (slightly skeptical) Open Source Software Educational Society

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

Graph Algorithms

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:

• directed graphs (digraphs )
• undirected 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 -vertex tree contains edges, so all non-trivial trees contain at least two leaf vertices.

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

• Reachability. Can you get to B from A?
• Shortest path (min-cost path). Find the path from B to A with the minimum cost (determined as some simple function of the edges traversed in the path) (Dijkstra's and Floyd's algorithms)
• Visit all nodes. Traversal. Depth- and breadth-first traversals
• Transitive closure. Determine all pairs of nodes that can reach each other (Floyd's algorithm)
• Dominators  a node d dominates a node n if every path from the start node to n must go through d. Notationally, this is written as d dom n. By definition, every node dominates itself. There are a number of related concepts:
  • immediate dominator
  • pre-dominator
  • post-dominator.
  • dominator tree
• Minimum spanning tree. A spanning three is a set of edges such that every node is reachable from every other node, and the removal of any edge from the tree eliminates the reachability property. A minimum spanning tree is the smallest such tree. (Prim's and Kruskal's algorithms)
• Topological sort

Some differences between graphs lists and trees: 

• The nodes are labeled, so that we can refer to each by name. Each node may have both multiple edges connected to it and multiple nodes exiting form it.
• Unlike trees and lists graphs don't necessarily have a unique start node.
• Similarly, graphs don't necessarily have a unique end node. As with lists and trees, we can make the edges unidirectional (directed graph) or bidirectional.
• Each list is a tree, each tree is a graph. Reverse is not true. 
• In some graphs it is possible to follow a sequence of edges and return to the node you started. That path (sequence of nodes traversed) is called a cycle.
  • Graphs with cycles are called cyclic graphs.
  • If there are no cycles in a graph, it is an acyclic graph.
  • When writing recursive graph algorithms that are not restricted to acyclic graphs, you may need to mark the nodes in the graph to ensure that you don't repeatedly use the same node.

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

Notes: Those pages are written by people for whom English is not a native language. Some amount of grammar and spelling errors should be expected. This is a Spartan WHYFF (We Help You For Free) site. It cannot replace the best teachers and the best books. The site contain some obsolete pages as it develops like a living tree... Some links on older pages are broken. Please try to use Google, Open directory, etc. to find a replacement link (see HOWTO search the WEB for details). We would appreciate if you can mail us a correct link. Search Amazon by keywords:     Open directory Research Index

Old News ;-)

SICStus Prolog

• Trees: Binary Tree Operations
• UGraphs: Graph and Digraph Operations
   

  Unweighted Graph Operations

  Directed and undirected graphs are fundamental data structures representing arbitrary relationships between data objects. This package provides a Prolog implementation of directed graphs, undirected graphs being a special case of directed graphs.

  An unweighted directed graph (ugraph) is represented as a list of (vertex-neighbors) pairs, where the pairs are in standard order (as produced by keysort with unique keys) and the neighbors of each vertex are also in standard order (as produced by sort), every neighbor appears as a vertex even if it has no neighbors itself, and no vertex is a neighbor to itself.

  An undirected graph is represented as a directed graph where for each edge (U,V) there is a symmetric edge (V,U).

  An edge (U,V) is represented as the term U-V. U and V must be distinct.

  A vertex can be any term. Two vertices are distinct iff they are not identical (==).

  A path from u to v is represented as a list of vertices, beginning with u and ending with v. A vertex cannot appear twice in a path. A path is maximal in a graph if it cannot be extended.

  A tree is a tree-shaped directed graph (all vertices have a single predecessor, except the root node, which has none).

  A strongly connected component of a graph is a maximal set of vertices where each vertex has a path in the graph to every other vertex.

  Sets are represented as ordered lists (see Ordsets).

  To load the package, enter the query
   

  | ?- use_module(library(ugraphs)).
  

  The following predicates are defined for directed graphs.
   

  vertices_edges_to_ugraph(+Vertices, +Edges, -Graph)

  Is true if Vertices is a list of vertices, Edges is a list of edges, and Graph is a graph built from Vertices and Edges. Vertices and Edges may be in any order. The vertices mentioned in Edges do not have to occur explicitly in Vertices. Vertices may be used to specify vertices that are not connected by any edges.
   

  vertices(+Graph, -Vertices)

  Unifies Vertices with the vertices in Graph.
   

  edges(+Graph, -Edges)

  Unifies Edges with the edges in Graph.
   

  add_vertices(+Graph1, +Vertices, -Graph2)

  Graph2 is Graph1 with Vertices added to it.
   

  del_vertices(+Graph1, +Vertices, -Graph2)

  Graph2 is Graph1 with Vertices and all edges to and from them removed from it.
   

  add_edges(+Graph1, +Edges, -Graph2)

  Graph2 is Graph1 with Edges and their "to" and "from" vertices added to it.
   

  del_edges(+Graph1, +Edges, -Graph2)

  Graph2 is Graph1 with Edges removed from it.
   

  transpose(+Graph, -Transpose)

  Transpose is the graph computed by replacing each edge (u,v) in Graph by its symmetric edge (v,u). Takes O(N^2) time.
   

  neighbors(+Vertex, +Graph, -Neighbors)

  neighbours(+Vertex, +Graph, -Neighbors)

  Vertex is a vertex in Graph and Neighbors are its neighbors.
   

  complement(+Graph, -Complement)

  Complement is the complement graph of Graph, i.e. the graph that has the same vertices as Graph but only the edges that are not in Graph.
   

  compose(+G1, +G2, -Composition)

  Computes Composition as the composition of two graphs, which need not have the same set of vertices.
   

  transitive_closure(+Graph, -Closure)

  Computes Closure as the transitive closure of Graph in O(N^3) time.
   

  symmetric_closure(+Graph, -Closure)

  Computes Closure as the symmetric closure of Graph, i.e. for each edge (u,v) in Graph, add its symmetric edge (v,u). Takes O(N^2) time. This is useful for making a directed graph undirected.
   

  top_sort(+Graph, -Sorted)

  Finds a topological ordering of a Graph and returns the ordering as a list of Sorted vertices. Fails iff no ordering exists, i.e. iff the graph contains cycles. Takes O(N^2) time.
   

  max_path(+V1, +V2, +Graph, -Path, -Cost)

  Path is a longest path of cost Cost from V1 to V2 in Graph, there being no cyclic paths from V1 to V2. Takes O(N^2) time.
   

  min_path(+V1, +V2, +Graph, -Path, -Cost)

  Path is a shortest path of cost Cost from V1 to V2 in Graph. Takes O(N^2) time.
   

  min_paths(+Vertex, +Graph, -Tree)

  Tree is a tree of all the shortest paths from Vertex to every other vertex in Graph. This is the single-source shortest paths problem.
   

  path(+Vertex, +Graph, -Path)

  Given a Graph and a Vertex of Graph, returns a maximal Path rooted at Vertex, enumerating more paths on backtracking.
   

  reduce(+Graph, -Reduced)

  Reduced is the reduced graph for Graph. The vertices of the reduced graph are the strongly connected components of Graph. There is an edge in Reduced from u to v iff there is an edge in Graph from one of the vertices in u to one of the vertices in v.
   

  reachable(+Vertex, +Graph, -Reachable)

  Given a Graph and a Vertex of Graph, returns the set of vertices that are reachable from that Vertex, including Vertex itself. Takes O(N^2) time.
   

  random_ugraph(+P, +N, -Graph)

  Where P is a probability, unifies Graph with a random graph of vertices 1..N where each possible edge is included with probability P.

  The following predicates are defined for undirected graphs only.

  min_tree(+Graph, -Tree, -Cost)

  Tree is a spanning tree of Graph with cost Cost, if it exists.
   

  clique(+Graph, +K, -Clique)

  Clique is a maximal clique (complete subgraph) of n vertices of Graph, where n \geq K. n is not necessarily maximal.
   

  independent_set(+Graph, +K, -Set)

  Set is a maximal independent (unconnected) set of n vertices of Graph, where n \geq K. n is not necessarily maximal.
   

  coloring(+Graph, +K, -Coloring)

  colouring(+Graph, +K, -Coloring)

  Coloring is a mapping from vertices to colors [1,n] of Graph such that all edges have distinct end colors, where n \leq K. The mapping is represented as an ordered list of Vertex-Color pairs. n is not necessarily minimal.

  • User's Manual

    ---

  • Table of Contents
• WGraphs: Weighted Graph and Digraph Operations

[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). ...
www.cs.uiuc.edu/class/sp06/ 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. ...
www.research.ibm.com/people/r/rama/Papers/pldi00.ps 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(m⁴n), 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(m^3.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

• Low-degree Graph Partitioning via Local Search with Applications to Constraint Satisfaction, Max Cut, and Coloring
  Magnús M. Halldórsson and Hoong Chuin Lau
  Vol. 1, no. 3, pp. 1-13, 1997.
  Submitted: February 1996. Revised: March 1997.
  Communicated by Martin Fürer.
  • article (compressed PostScript)
  • article (PDF)

JGAA Volume 3, 1999

• Subgraph Isomorphism in Planar Graphs and Related Problems
  David Eppstein
  Vol. 3, no. 3, pp. 1-27, 1999.
  Submitted: December 1995. Revised: November 1999.
  Communicated by Roberto Tamassia.
  • article (compressed PostScript)
  • article (PDF)

JGAA Volume 4, 2000

• Approximation Algorithms for Some Graph Partitioning Problems
  G. He, J. Liu and C. Zhao
  Vol. 4, no. 2, pp. 1-11, 2000.
  Submitted: July 2000. Revised: August 2000.
  Communicated by David Eppstein.
   
  • article (PDF)

JGAA Volume 5, 2001

• Connectivity of Planar Graphs
  Hubert de Fraysseix and Patrice Ossona de Mendez
  Vol. 5, no. 5, pp. 93-105, 2001.
  Submitted: February 1999. Revised: April 2000.
  Communicated by Takao Nishizeki, Roberto Tamassia and Dorothea Wagner.
   
  • article (PDF)

JGAA Volume 7, 2003

• Finding Shortest Paths With Computational Geometry
  Po-Shen Loh
  Vol. 7, no. 3, pp. 287-303, 2003.
  Submitted: October 2002. Revised: June 2003.
  Communicated by Joseph S. B. Mitchell.
   
  • article (PDF)

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.

An Introduction to Graph Algorithms by Ute Loerch, Department of Computer Science, University of Auckland, Auckland, New Zealand, ute@cs.auckland.ac.nz 

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

• Scribes of Spring 94 lectures Talks were scribed by the students and revised by the lecturer. The complete set of notes was subsequently edited and formatted by Sariel Har-Peled . Thanks, Sariel ! You can either download the complete notes as a single postscript file (150 pages), Or each lecture separately. Cover
  • Cover page
  • Table of Content
  • List of Figures
  Lecture #1: Introduction to Graph Theory
  • Basic Definitions and Notations
  • Intersection Graphs
  • Circular-arc Graphs
  • Interval Graphs
  • Line graphs of bipartite graphs

Recommended Links

• Wikipedia
  • Graph theory
  • Graph (mathematics)
  • Glossary of graph theory
• Combinatorial Optimization & Graph Algorithms
• Graph Theory Lessons

• Graphs

  • Graphs Transitive Closure

  • breadth-first and depth-first search

  • single-source-shortest-path

  • all-pairs-shortest-path

  • minimum spanning tree

• Algorithms and Software for Partitioning Graphs
• Graphs Theory - Algorithms - Complexity
• Graph Theory Research Group

• The Stony Brook Algorithm Repository

  • 1.4 Graph Problems -- polynomial-time problems

  • 1.5 Graph Problems -- hard problems

• Library of Efficient Data Types and Algorithms (LEDA)

• Graphs

  • Graphs Transitive Closure

  • breadth-first and depth-first search

  • single-source-shortest-path

  • all-pairs-shortest-path

  • minimum spanning tree

• Computer Science papers by Cliff Stein
• Linear Graph Reduction: Confronting the Cost of Naming, my PhD dissertation, available in gzip'd PostScript (279K). gzip'd PostScript
• Optimal Algorithms -- Peter M. Maurer, University of South Florida
   
• Data Structures And Number Systems by Brian Brown
   
• Maze classification and algorithms -- A short description of mazes and how to create them. Definition of different mazetypes and their algorithms.
   
• Numerical methods
   
• Stack Free Recursion -- A paper describing the "Stack Free Recursion" algorithm. C code with C++ comments.
   
• comp.graphics.algorithms Frequently Asked Questions
   
• Journal of Graph Algorithms and Applications Electronic Edition
   
• 05C Graph theory

Shortest Path

Shortest Path Problem Web Pages

• Shortest path chapter   http://www.utdallas.edu/~chandra/documents/networks/net3.pdf
• Shortest Path, from Harvey Greenberg Mathematical Programming Glossary
• Shortest Paths: Dijkstra's Algorithm, by Chris Palmer
• All-Points Shortest Path (A Second Solution), from The Caltech Archetypes / eText Project Web Page
• All Points Shortest Path, by Yolanda Palomo
• Dijkstra's Shortest Path Algortithm Animation in Java, by Carla Laffra of Pace University
• The Shortest Path Problem, by Daniel Castellon, Gianluca DiNunzio, and Enairo Urdaneta
• The Shortest Path algorithm from Cornell University Web Page
• The Optimal Path Problem , a paper by Ernesto Martins, Marta Pascoal, Deolinda Rasteiro and José Luis Santos, that is on line for now.
• About optimal path problem, from my "questions from old examinations" Web page.
• Codes for the shortest path problem, from my "Fortran Source Codes" Web page.
   
• Path me and I'll path you! from tutOR
• Case Study: Shortest-Path Algorithms by Ian Foster
• The Shortest Path Problem, by Jonathan Jenkyn
• A Tutorial on Network Optimization, by Girard Cornuijols and Michael A. Trick
• Shortest Path Problem, by Ikeda
• Obliq-3D: A High-Level, Fast-Turnaround 3D Animation System, by Marc A. Najork and Marc H. Brown
• Algorithm/Data Structure Animations for Educational Use by Marco Nissen
• Path.c, a C code for the all pairs shortest path problem by Wolfgang Schreiner
• An Animation of the k-Shortest Paths Algorithm, by Mark Manasse, and Greg Nelson
•  
• Finding Alternative Routes, from THE SCIENCE AND TECHNOLOGY OF DECISION-MAKING Web Page
• Finding Routes when Values of Time are Nonlinear, from THE SCIENCE AND TECHNOLOGY OF DECISION-MAKING Web Page
• Shortest Path, from The Stony Brook Algorithm Repository Web Page
• Dijkstra's Algorithm: A Shortest Path Algorithm, by Isidore Pires

Graph Drawing

Graph Drawing Tools

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

Coloring

Joseph Culberson's Graph Coloring Resources Page

Libraries

LEDA moved to Algorithmic Solutions Software GmbH

LEDA Combinatorial and Graph Algorithms

Combinatorica

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

The Stony Brook Algorithm Repository

Pearson Books - Boost Graph Library, The

History

"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. http://mathworld.wolfram.com/Graph.html ) 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.

This 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 K₅ and the complete bipartite graph K_3,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 K₅ 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 K_3,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.

Humor

The Graph Theory Hymn

THE GRAPH THEORY HYMN

Text by BOHDAN ZELINKA
Music by ZDENĔK RYJÁČEK
English text by DONALD A. PREECE          

            1.
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.

    2.
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.

    3.
Here's the problem; see if you can solve it!
Try it out at home an scraps of paper!
STARTING OUT AND ENDING AT THE SAME SPOT,
YOU MUST CROSS EACH BRIDGE JUST ONCE EACH EV'NING.

    Refrain:
Eulerian graphs all have this restriction:
THE DEGREE OF ANY POINT IS EVEN.
That's the oldest graph result
That mankind has ever known.

   4.
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.

    5.
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."

    Refrain:
Eulerian graphs …

    6.
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.

    7.
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.

    Refrain:
Eulerian graphs …

    8.
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.

    9.
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!