Keywords |
  • Mathematics

Graph theory

A graph is a collection of elements in a system of inter-relations. Geometrically, these elements are represented by points (vertices) interconnected by the arcs of a curve (the edges). According to whether we choose to direct the edges or to give them a weight (a cost of passage); we speak of directed graphs or weighted graphs.

Les graphes complets sont ceux dont tous les sommets sont reliés deux à deux.
Complete graphs are those where all the vertices are connected pairwise.
Credits: S. Tummarello

The theory of graphs is concerned with their multiple properties: the existence of the shortest or cheapest routes, of particular cycles (Eulerian, Hamiltonian etc.), the number of intersections in the plane, colouring problems, etc.

Le graphe K3,3 n'est pas planaire : les arêtes se coupent en au moins un point dans le plan.
The graph K3,3 is not planar: the edges intersect at at least one point in the plane.
Credits: S. Tummarello

Graph theory goes back to the problem of the bridges of Königsberg: is it possible to walk through this town via a circuit that passes once and only once over each of the seven bridges? In modern terms, the problem is to show the existence of a Eulerian cycle in the associated graph: In 1736, Euler showed that such a route did not exist.

Le graphe associé au problème des ponts de Königsberg.
The graph associated with the problem of the bridges of Königsberg.
Credits: S. Tummarello

Today, graphs have very many applications in modelling networks (roads, information, etc.). Moreover, graph theory has brought up algorithm problems (the travelling salesman problem, graph colouring, calculation of the largest sub-graph common to two graphs etc.), which are crucial in complexity theory (NP-complete problems, the P=NP conjecture).



Fill out my online form.