Euler Circuits in Graphs

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:
  1. To 2: 2; To 3: 1;
  2. To 2: 2; To 3: 1;
  3. To 0: 2; To 1: 2; To 3: 1;
  4. 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. 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."); } }