Introduction to graph theory

Vous êtes ici : Accueil du site > Archives > Maths in english > Introduction to graph theory

Graph theory

PDF - 407.5 ko
Introduction à la théorie des graphes pour la DNL math en anglais.

We will be studying "routing problems"

One of the most common problems in urban service systems is the design of routes for vehicles or people. In some instances, these routes must be designed so that they traverse in an exhaustive way the streets in a neighborhood or in a specific part of a city or, occasionally, in a whole city. Alternatively, the objective may be to visit a set of given geographical points in a city in order to provide some service there or to deliver or collect goods.

For obvious reasons, these two classes of problems are referred to as edge-covering and node-covering problems, respectively. Topics covered in these lessons :

- The seven bridges of Königsberg.
- Eulerian graphs. Discovering Euler’s theorems.
- The traveling salesman problem
Here an intro with some game.
Here an applet showing an algorithm to minimze the distance.
- The chinese mailman problem.
- Link to an MIT video on graph theory

Documents joints

Graphs-Cities-Konigsberg, PDF, 407.5 ko
Introduction à la théorie des graphes pour la DNL math en anglais.
Graphs-Cities-Konigsberg, LaTeX, 10.4 ko
Fichier source.