[ Français | English ]
The famous problem of the bridges of Königsberg, solved by Euler, is viewed as the first formal result in graph theory. This theory has developed during the second half of the 19th century (with Hamilton, Heawood, Kempe, Kirchhoff, Petersen, Tait), and has boomed since the 1930s (with König, Hall, Kuratowski, Whitney, Erdös, Tutte, Edmonds, Berge, Lovász, Seymour, and many other people). It is clearly related to Algebra, Topology, and other topics from Combinatorics. It applies to -- and gets motivating new problems from -- Computer Science, Operations Research, Game Theory, Decision Theory.
The number of concepts that can be defined on graphs is very large, and many generate deep problems or famous conjectures (for instance the four colour problem). In fact, many of these concepts or theoretical questions arise from practical reasons (and not just from the mathematicians' imaginations) for solving real problems modeled on graphs. Moreover, researchers in Graph Theory try if possible to find efficient algorithms for solving these problems.
The main classical problems in Graph Theory are : flow and connectivity (network reliability), matching (assignment), Eulerian walks (traversing each edge once; more generally, the "Chinese Postman Problem"), Hamiltonian walks (traversing once each vertex: the "Travelling Salesman Problem"), vertex- or edge- coloring, stable sets, dominating sets. Some of the above (maximum flow, maximum matching, Eulerian walk) can be efficiently solved, while the others are very hard ("NP-complete").
A generalization of the concept of graph, introduced by Claude Berge in 1960, is that of hypergraph, where, simply, the edges may have arbitrary size and not only size two.
We present in an annex a small bibliographical reference on Graph Theory, and a more precise description of our research topics.
Graph Theory - Games on Graphs - Graph Algorithms
Back to our home
page