Théorie des Graphes

Une courte présentation… pour vous mettre en appétit.

Origine historique : le problème d’Euler

• Euler, l'un des plus grands mathématiciens, aimait à faire une promenade dans sa bonne ville de Koenigsberg. Il affectionnait tout particulièrement de parcourir les 7 ponts qui enjambent la rivière.

L'âge venant, il se demanda si sans sacrifier à sa promenade, il pouvait en raccourcir la longueur en ne parcourant chaque pont qu'une seule fois.

Ce problème est sans doute l'un des plus anciens en théorie des graphes : celui de l'existence d'un cycle passant une et une seule fois par chaque arête.

Euler • Leonhard Euler (1707 - 1783) était un

mathématicien et un physicien suisse.

Il est né en Suisse, à Bâle, en 1707, et il y étudie les mathématiques ; par la suite il travaille en tant que professeur de mathématiques à Saint-Pétersbourg, et plus tard à Berlin, puis retourne à Saint-Petersbourg. Il est considéré comme le mathématicien le plus prolifique de tous les temps. Il domine les mathématiques du XVIIIe siècle et développe très largement ce qui s'appelle alors la nouvelle analyse.

Complètement aveugle pendant les dix-sept dernières années de sa vie, il produit presque la moitié de la totalité de son travail durant cette période.

Rappel : le problème d’Euler

• Euler, l'un des plus grands mathématiciens, aimait à faire une promenade dans sa bonne ville de Koenigsberg. Il affectionnait tout particulièrement de parcourir les 7 ponts qui enjambent la rivière.

L'âge venant, il se demanda si sans sacrifier à sa promenade, il pouvait en raccourcir la longueur en ne parcourant chaque pont qu'une seule fois.

Ce problème est sans doute l'un des plus anciens en théorie des graphes : celui de l'existence d'un cycle passant une et une seule fois par chaque arête.

Formalisation du problème d’Euler• La rivière sépare la ville de Koenigsberg

en 4 parties, a, b, c et d. Un pont relie 2 de ces parties. On peut alors représenter notre problème par un graphe avec 4 sommets (représentant une partie de la ville) et 7 arêtes (où chaque arête représente l'un des 7 ponts de Koenigsberg).

• On parle de graphe eulérien lorsqu’on peut passer par chacun des sommets en ne parcourant qu’une et une seule fois chacune des arêtes.

Euler a montré qu'il est impossible de parcourir tous les ponts de Koenigsberg seulement une fois au cours d'une promenade. Il a alors développé une théorie très riche et fructueuse : la théorie des graphes

D’autres problèmes pour différents aspects d’une même théorie.

Cette année, nous verrons principalement les problèmes suivants :

• Coloration d’un graphe : problèmes d’incompatibilité

• Cheminement dans un graphe : problèmes de faisabilité.

• Graphe étiquetés : problèmes de longueur minimale

• Graphes probabilistes : problème de dynamique de populations.

Coloration d’un graphe

Combien de couleurs doit-on avoir pour colorier la carte de l’Afrique ?

En utilisant le moins de couleurs possibles, de sorte que deux pays voisins aient des couleurs différentes

Coloration d’un graphe

A, B, C, D, E, F, G, H désignent 8 espèces de poissons. Dans le tableau ci-dessous, le caractère * signifie que les espèces ne peuvent cohabiter dans un même aquarium.

Combien faut-il au minimum d’aquarium ?

  A B C D E F G H

A      

B        

C      

D        

E        

F          

G        

H          

Cheminement dans un graphe• Le problème d’Euler est un

problème de cheminement :

est-il possible de passer par chacun des sommets en ne parcourant qu’une et une seule fois chacune des arêtes ?

Cheminement dans un graphe

Question : peut-on dessiner cette enveloppe sans tracer deux fois le même trait ?

Même question si on impose en plus de revenir au point de départ.

Graphe étiquetés

• On cherche un plus court chemin dans le cas de graphes valués, où chaque arête e est associée à une valeur, appelée souvent son poids, c(e). La valuation des arêtes peut représenter des coûts de transit, des distances kilométriques, le temps nécessaire pour parcourir les arêtes,...

Graphe étiquetés• On cherche un plus court

chemin entre la ville orange et la ville rouge.

• Où la valuation des arêtes peut représenter des coûts de transit, des distances kilométriques, le temps nécessaire pour parcourir les arêtes,...

Graphes probabilistesEn 1907, Markov a entamé l’étude de phénomènes aléatoires où le résultat d’une expérience aléatoire peut influencer l’expérience suivante. Ce type de processus est appelé « chaîne de Markov ».

Un exemple : Le temps au pays d’Oz.Le pays d’Oz connaît exactement 3 types de temps :

• Beau temps noté B • Pluvieux noté P • Neigeux noté N

Les règles d’évolution du temps au pays d’Oz sont immuables et ne souffrent aucune exception ; ainsi :1.        S’il fait beau, il ne fera pas beau le lendemain et il y a autant de chances qu’il pleuve ou qu’il neige le lendemain.2.        S’il pleut ou s’il neige, il y a une chance sur deux qu’il fasse le même temps le lendemain et une chance sur quatre qu’il fasse beau le lendemain.

Graphes probabilistesUn exemple : Le temps au pays d’Oz.Le pays d’Oz connaît exactement 3 types de temps :

• Beau temps noté B • Pluvieux noté P • Neigeux noté N

Les règles d’évolution du temps au pays d’Oz sont immuables et ne souffrent aucune exception ; ainsi :1.        S’il fait beau, il ne fera pas beau le lendemain et il y a autant de chances qu’il pleuve ou qu’il neige le lendemain.2.        S’il pleut ou s’il neige, il y a une chance sur deux qu’il fasse le même temps le lendemain et une chance sur quatre qu’il fasse beau le lendemain.

Graphes probabilistes : entre géométrie et calcul matriciel !

Voici donc exposés certains des problèmes que nous

rencontrerons au cours de l’année …

Avec pour chaque problème les mêmes questions :

Un problème posé a-t-il ou non des solutions ?Si oui, en a-t-il une unique ? Une meilleure ?Peut-on la trouver ? Peut-on donner un mode d’emploi (algorithme) pour la trouver ?