<p>Most people cite Euler's 1741 "Bridges of Königsburg" paper as the oldest graph algorithm.  Unfortuantely, Euler doesn't actually describe his algorithm in detail, but only gives a half-hearted example:</p>

<blockquote>
  <p>“When it has been determined that such a journey can be made, one
  still has to find how it should be arranged. For this I use the
  following rule: let those pairs of bridges which lead from one area to
  another be mentally removed, thereby considerably reducing the number
  of bridges; it is then an easy task to construct the required route
  across the remaining bridges. and the bridges which have been removed
  will not significantly alter the route found, as will become clear
  after a little thought. <b>I do not therefore think it worthwhile to give
  any further details concerning the finding of the routes.</b>”</p>
</blockquote>

<p>The first complete proof that all even connected graphs have Eulerian tours is apparently due to Heirholzer more than a century later.</p>

<ul>
<li><p>Leonhard Euler. Solutio problematis ad geometriam situs pertinentis. <i>Commentarii academiae scientiarum Petropolitanae</i> 8:128–140, 1741. Presented to the St. Petersburg Academy on August 26, 1735. Reprinted in <i>Opera Omnia</i> 1(7):1–10. </p></li>
<li><p>Carl Hierholzer. Über die Möglichkeit, einen Linienzug Ohne Wiederholung und ohne Unterbrechnung zu umfahren. <i>Mathematische Annalen</i> 6:30–32, 1873.</p></li>
</ul>

CC BY-SA 3.0
2011-12-12T11:09:10.247Z
2011-12-14T08:54:15.103Z
2011-12-14T08:54:15.103Z
Jeffε
<p>Usually, Schrijver provides a good source for history. You can look at the following books and an article.</p>

<ul>
<li>Alexander Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Springer 2003.</li>
<li>Alexander Schrijver. Theory of Linear and Integer Programming. Wiley 1998.</li>
<li>Alexander Schrijver. On the history of the transportation and maximum flow problems. Mathematical Programming 91(3), 2002, 437-445. <a href="http://dx.doi.org/10.1007/s101070100259">http://dx.doi.org/10.1007/s101070100259</a> </li>
<li>Alexander Schrijver. On the history of combinatorial optimization (till 1960).  Handbook of Discrete Optimization, Elsevier, 2005.  <a href="http://homepages.cwi.nl/~lex/files/histco.pdf">http://homepages.cwi.nl/~lex/files/histco.pdf</a></li>
</ul>

CC BY-SA 3.0
2011-12-12T10:54:00.737Z
+1 for Schrijver.  I added a fourth recommended source, which points to early papers by Frobenius [1912] and Kőnig [1915] on bipartite matching, Boruvka [1926] on minimum spanning trees,  Menger [1927] on his so-called "$n$-arc theorem" and again [1930] on the traveing salesman problem, and Tolstoi [1930] on the transportation problem.
Jeffε
CC BY-SA 3.0
2011-12-12T12:28:03.320Z
@JɛﬀE: Thank you very much for the addition.
Yoshio Okamoto
CC BY-SA 3.0
2011-12-12T15:43:29.160Z
Thank you. The last one, on the history of combinatorial optimization, is exactly what I was looking for.
dan_x
CC BY-SA 3.0
2011-12-12T09:12:33.050Z
2011-12-12T10:43:34.193Z
2011-12-12T10:43:34.193Z
Yoshio Okamoto
<p>(Apologies if this is misplaced or too broad.  I'm open to suggestions on how to reformulate it.)</p>

<p>I'm interested in tracing back the "ancient" history of max-flow algorithms, and discrete optimization algorithms in general.  Ford-Fulkerson is my straw-man of a starting point.  What were the significant advances prior to that?  How far back can we go while still being able to make a reasonable argument that somebody was working on max-flow?  How about graph algorithms?  How about discrete optimization in general?</p>

<p>I'd also be happy to get references to places where this is discussed.</p>

<ds.algorithms><graph-algorithms><ho.history-overview>
Early references for discrete optimization
dan_x
# Early references for discrete optimization

(Asked by: username_0 on 2011-12-12)

(Apologies if this is misplaced or too broad. I'm open to suggestions on how to reformulate it.)

I'm interested in tracing back the "ancient" history of max-flow algorithms, and discrete optimization algorithms in general. Ford-Fulkerson is my straw-man of a starting point. What were the significant advances prior to that? How far back can we go while still being able to make a reasonable argument that somebody was working on max-flow? How about graph algorithms? How about discrete optimization in general?

I'd also be happy to get references to places where this is discussed.

**Tags:** ds.algorithms, graph-algorithms, ho.history-overview


---

## 2 answers

### Answer by username_2 on 2011-12-12. Score: 14 | Accepted answer

Usually, Schrijver provides a good source for history. You can look at the following books and an article.

* Alexander Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Springer 2003.
* Alexander Schrijver. Theory of Linear and Integer Programming. Wiley 1998.
* Alexander Schrijver. On the history of the transportation and maximum flow problems. Mathematical Programming 91(3), 2002, 437-445. <http://dx.doi.org/10.1007/s101070100259>
* Alexander Schrijver. On the history of combinatorial optimization (till 1960). Handbook of Discrete Optimization, Elsevier, 2005. <http://homepages.cwi.nl/~lex/files/histco.pdf>

> **Comments:**
> **username_1**: +1 for Schrijver.  I added a fourth recommended source, which points to early papers by Frobenius [1912] and Kőnig [1915] on bipartite matching, Boruvka [1926] on minimum spanning trees,  Menger [1927] on his so-called "$n$-arc theorem" and again [1930] on the traveing salesman problem, and Tolstoi [1930] on the transportation problem.  
> **username_2**: @JɛﬀE: Thank you very much for the addition.  
> **username_0**: Thank you. The last one, on the history of combinatorial optimization, is exactly what I was looking for.  

---

### Answer by username_1 on 2011-12-12. Score: 7

Most people cite Euler's 1741 "Bridges of Königsburg" paper as the oldest graph algorithm. Unfortuantely, Euler doesn't actually describe his algorithm in detail, but only gives a half-hearted example:

> “When it has been determined that such a journey can be made, one
> still has to find how it should be arranged. For this I use the
> following rule: let those pairs of bridges which lead from one area to
> another be mentally removed, thereby considerably reducing the number
> of bridges; it is then an easy task to construct the required route
> across the remaining bridges. and the bridges which have been removed
> will not significantly alter the route found, as will become clear
> after a little thought. **I do not therefore think it worthwhile to give
> any further details concerning the finding of the routes.**”

The first complete proof that all even connected graphs have Eulerian tours is apparently due to Heirholzer more than a century later.

* Leonhard Euler. Solutio problematis ad geometriam situs pertinentis. *Commentarii academiae scientiarum Petropolitanae* 8:128–140, 1741. Presented to the St. Petersburg Academy on August 26, 1735. Reprinted in *Opera Omnia* 1(7):1–10.
* Carl Hierholzer. Über die Möglichkeit, einen Linienzug Ohne Wiederholung und ohne Unterbrechnung zu umfahren. *Mathematische Annalen* 6:30–32, 1873.


---

