Königsberg (today called Kaliningrad) is a town in Western Russia
which in ancient arranged on two islands and the adjecent mainland in the
river Pregel. The first island was connected with two bridges to each
side of the river and the second island was connected with one bridge
to each side of the river, furthermore there was a bridge between the
islands. Mathematicians and other inhabitants of Königsberg discussed
whether it was possible to walk all the bridges without using any bridge
twice, hereby one had to use each bridge to go from one side to the other
without turning in the middle.
Wikipedia
has the following picture of an ancient map of Königsberg with
the river and bridges highlighted:
The Swiss mathematician
Leonhard Euler
(1707-1783) took this problem as a starting point of
a general theory of graphs. That is, he first made a mathematical model
of the problem. He denoted the four pieces of lands with "nodes" in a
graph: So let 0 and 1 be the mainland and 2 be the larger island (with
5 bridges connecting it to the other pieces of land) and 3 be the smaller
island (with 3 bridges connecting it to the other pieces of land).
Now one could give for each node a list of nodes it was connected to,
with a multiplicity factor telling how many bridges were there:
To 2: 2; To 3: 1;
To 2: 2; To 3: 1;
To 0: 2; To 1: 2; To 3: 1;
To 0: 1; To 1: 1; To 2: 1;
In Javascript, such a data structure would be represented as an array
of arrays. One could create the data structure as follows:
var a = new Array();
var a[0] = new Array(); a[0][2] = 2; a[0][3] = 1;
var a[1] = new Array(); a[1][2] = 2; a[1][3] = 1;
var a[2] = new Array(); a[2][0] = 2; a[2][1] = 2; a[2][3] = 1;
var a[3] = new Array(); a[3][0] = 2; a[3][1] = 2; a[3][2] = 1;
Euler analysed now that there are two situations.
If the starting point and the end point of the trip are the same -
this situation could be called a circuit - then for every node the
sum of the connectives must be even, as each time the node is visited,
the visitor comes in on one bridge and leaves on another bridge.
If the starting point and the end point of the trip are different -
this situation could be called a path - then there are two nodes which
must have an odd number of bridges: The node where the trip stars and
the node where the trip ends. All other nodes must have an even number
of nodes.
Furthermore, Euler observed that all nodes must be connected. Otherwise
there would be two nodes i and j so that whenever one starts a trip at
i one cannot reach node j in whatever way one is going. For example if
there would only be an even number of bridges between 0 and 1 and also
between 2 and 3 but no other bridges then one cannot go from 0 to 3, as
all pathes starting at 0 can only visit the nodes 0 and 1.
These criteria directly decide that the Königsberg bridge problem
has no solution. All nodes have an odd number of bridges connecting to
them and it are four nodes. The main contribution of Euler - besides
formalising the problem as outlined above - is also to show that the
above criteria are sufficient. That is, whenever the first and third
criterion are satisfied, there is a circuit using each bridge once;
whenever the second and third condition are satisfied, there is a
path using each bridge once, but the path starts in a different node
than it ends.
The following Javascript programs check the conditions. First the
program reach(i,a) lists in an array all the nodes which can be
reached from i without caring whether a bridge is used once or
several times.
function reach(i,a,b)
{ if (i in b) { return; }
b[i] = 1;
for (j in a[i])
{ reach(j,a,b); }
return; }
.....
for (i in a)
{ b = new Array();
reach(i,a,b);
for (j in a)
{ if (!(j in b))
{ return("The graph "+display(a)+" is not connected."); } } }
.....
The function uses a subfunction "reach". Note that this function
is recursive: when coming into a node i, it marks it as reached by making
an entry into b and then visits all nodes j in recursive calls which
are connected to i.
Furthermore, it does this only in the case that i is not yeat marked
as reached, in order to avoid that the program recursively visits a node
and revisits it and revisits it and so on. The list of nodes reached from
i in the graph a are then returned. In order to be sure that every node
is visited, the main program has then to compare whether the nodes in b
and in a are the same. In the current implementation, a loop checks whether
from every i in a every node can be reached; however, it would be sufficient
to check it only for one node i.
The second part to be checked is the Euler condition on the number of
bridges - in graph theory they are called edges - for each node. For an
Euler circuit, this number of edges has to be even in every node.
The program part to do this is the following.
function euler(..)
{ ....
for (i in a)
{ k = 0;
for (j in a[i])
{ k = k+a[i][j]; }
if (k%2 == 1)
{ h = h+1; } }
if (h == 0)
{ return("The graph "+display(a)+" has an Euler circuit."); }
if (h == 2)
{ return("The graph "+display(a)+" has an Euler path."); }
var t="The graph "+display(a)+" has "+h+" nodes with odd connections.");
return(t); }
One can compute the Euler circuit or Eulerpath with the following
function which returns an array of the path (or circuit in the
case that s == t) from s to t; note that the arrays a and u are
parameters; a[i][j] says how many bridges there are between nodes
i and j; u[i][j] says how many of these are already used and
u[i][j] is 0 at the beginning. As the direction of the usage
of the bridges does not matter, each usage must update u[i][j]
as well as u[j][i]. The path is stored in v and w; v is the
final part, w is the part which might still have to be checked
on whether a self-loop from the nodes in w to itself through some
bridges needs to be inserted in order to make the Euler path or
circuit complete.
function findeuler(a,s,t,u)
{ var v = new Array(0); var w = new Array(0);
var i = s; var j = 0; var k; w.push(i); var r;
do
{ j = "new";
for (k in a[i])
{ if (u[i][k] < a[i][k]) { j = k; } }
if (j != "new") { w.push(j); u[i][j]++; u[j][i]++; i = j; } }
while ((i != t) && (j != "new"))
while (w.length > 0)
{ i = w.shift(); v.push(i);
j = "new";
for (k in a[i])
{ if (u[i][k] < a[i][k])
{ j = k; } }
if (j != "new")
{ u[i][j]++; u[j][i]++;
r = findeuler(a,j,i,u); w = r.concat(w); } }
return(v); }
If you view the source of this page in Firefox (Webdevelopper, view source),
you find all Javascript programs related to this topic in the begin of
this file and can copy them into the Scratchpad to study them more in detail.
You can click the below buttons in order to get sample graphs for each of
the possible outcomes, the last button illustrates some checks which are
done in order to make sure that the graph is coded in a consistent way
(that is, if a[i][j] exists then a[j] should exist and a[i][j] should be
equal to a[j][i] and so on).
Hamiltonian Circuits in Graphs
Besides studying whether one can use each bridge once, one could also study
whether one can make a circuit using each node once (when then many edges
remain unused). This was investigated first by
William
Rowan Hamilton (1805-1865). He is an Irish astronomer, mathematician
and physicist.
While one can easily test for the existence of an Euler circuit, this
is much more difficult for Hamilton circuits and no fast programs are
known. Here a sample program.
function subhamilton(i,a,b)
{ var j; var k = 1;
b[i] = 1;
for (j in b)
{ if (b[j]==0)
{ k=0; } }
if (k == 1) { b[i] = 0; return(0 in a[i]); }
for (j in a[i])
{ if ((b[j]==0)&&(k == 0)) { k = subhamilton(j,a,b); } }
b[i] = 0; return(k); }
....
function hamilton(..)
{ ....
var b = new Array();
for (i in a)
{ b[i] = 0; }
if (subhamilton(0,a,b) == 1)
{ return("The graph "+display(a)+" has a Hamiltonian circuit."); }
else
{ return("The graph "+display(a)+" has no Hamiltonian circuit."); } }
