Groupe graphes
2001-2003

Théorie des graphes
en TES option « Maths »

Bref historique

| 1736, Euler : les ponts de Königsberg
| 1852, De Morgan (Guthrie) : quatre couleurs
| 1946, Kuhn, Ford et Fulkerson, Roy, etc.
| … recherche opérationnelle …
| Depuis 1960, applications à l’informatique

Applications en chimie…

A la Sociologie…

A la Biologie…

A la recherche opérationnelle

| R.O.

Etc.

Une situation…

Un graphe…

| Pour répondre à cette question, il est assez naturel de construire un schéma faisant apparaître les neuf planètes et les liaisons existant entre certaines d’entre elles.

Mais qu’est-ce qu’un graphe ?

| Un graphe est constitué de sommets dont certains sont reliés par des arêtes.
| Si les arêtes sont orientées, le graphe est dit orienté.
| Deux sommets reliés par une arête sont dits adjacents.
| Le nombre de sommets du graphe est l’ordre du graphe.
| Le degré d’un sommet est le nombre d’arêtes dont ce sommet est une extrémité.
| Un graphe est complet lorsque tous ses sommets sont adjacents

Propriétés des sommets

Graphe complet

Multigraphes

| Lorsque 2 sommets sont reliés par plusieurs arêtes, on parle de multigraphe…

Graphe orienté

| Lorsque les arêtes sont orientées, on dit que le graphe est orienté

Graphe pondéré

| Un graphe étiqueté est un graphe dont toutes les arêtes sont affectées d’étiquettes
| Lorsque les étiquettes sont des réels positifs, le graphe est dit pondéré.

Graphe probabiliste

| Lorsque dans un graphe orienté et pondéré, la somme des poids des arêtes sortant de chaque sommet vaut 1, on parle de graphe probabiliste

Représentations d’un graphe

Matrice d’un graphe

| La matrice associée à un graphe d’ordre n dont les sommets sont numérotés de 1 à n est une matrice carrée de dimension n où le terme figurant en ligne i colonne j est égal au nombre d’arêtes reliant i à j.

Circuits dans un graphe

| Une chaîne est une liste ordonnée de sommets telle que tout sommet (sauf le dernier) de la liste soit adjacent au suivant.
| La longueur d’une chaîne est le nombre d’arêtes qui la composent.
| Un graphe est connexe s’il existe toujours une chaîne entre deux sommets distincts
| Une chaîne est fermée lorsque l’origine et l’extrémité sont identiques.
| Un cycle est une chaîne fermée dont toutes les arêtes sont distinctes.
| Une chaîne est eulérienne si elle contient chaque arête du graphe une et une seule fois.
| Si une chaîne eulérienne est un cycle, on parle de cycle eulérien.
| Une chaîne est hamiltonienne lorsque tous les sommets du graphe y figurent de manière distincte une fois et une seule

Exemples de circuits

Chaîne eulérienne

Nombre chromatique

| Colorer un graphe consiste à affecter une couleur à chaque sommet de sorte que deux sommets adjacents ne portent pas la même couleur.
| Le nombre chromatique est le plus petit nombre de couleurs nécessaire à son coloriage.

Résultats fondamentaux

Degrés…

| La somme des degrés des sommets d’un graphe non orienté est égale à deux fois le nombre d’arêtes du graphe.
| Corollaire : Un graphe a un nombre pair de sommets de degré impair.

Matrice d’un graphe

| Soit A la matrice associée à un graphe. Le terme aij de la matrice An donne le nombre de chaînes de longueur n reliant i à j.

Nombre chromatique

| Le nombre chromatique d’un graphe complet d’ordre n vaut n.

Théorème d’Euler

| Un graphe connexe admet une chaîne eulérienne si et seulement si le nombre de sommets de degré impair vaut 0 ou 2.
| Un graphe connexe admet un cycle eulérien si et seulement si tous ses sommets sont de degré pair.

2° Chaînes eulériennes

Chaîne eulérienne

En termes de graphes…

Construction d’une chaîne eulérienne

Insertion d’un cycle

Et on itère…

Et encore…

Et une dernière fois !

Les segments dans le plan

Encore un graphe…

MAIS…

Et en modifiant l’énoncé ?

Une solution avec 8 segments…

3° Circuits touristiques

Circuits touristiques

Circuits touristiques

Matrice associée au graphe

M4

M5 et M8

Annexe : Puissances de M

4° Coloriages

L’aquarium

Un premier graphe
de compatibilité

Un graphe d’incompatibilité…

L’algorithme de Powell – Welsh

Constitution des aquariums

Remarques…

Autour de l’algorithme de P - W

Un algorithme parfois « glouton »

Une explication…

Et les 4 couleurs pour terminer….

4 couleurs suffisent pour colorer un graphe planaire…

Graphes complets…

4 couleurs suffisent…

Le nombre chromatique est bien 4…

5° L’algorithme de Dijkstra

Edsger Dijkstra

| Le mathématicien Edsger Dijkstra a beaucoup oeuvré en informatique, il y a appliqué les méthodes d'approche de l'informatique. Il fut l'un des concepteurs du langage ALGOL, il a conçu et codé la première version du compilateur d'ALGOL 60. Il fut l'un des plus virulents détracteurs du GOTO.
| Edsger Dijkstra est mort le 6 août 2002.

L’algorithme sur un exemple

Étape 0

Étape 1

Étape 2

Étape 3

Étape 4

Étape 5

Étape 6

Étape 7

Étape 8

Étape 9

Le parcours final

6° De Marienthal à Haguenau…

De Marienthal à Strasbourg

Pour simplifier…

Le graphe de la situation

Dijkstra…

Solution

7° Chaînes de Markov

Le temps au pays d’OZ

Les arbres de la situation

| Le processus d’évolution du temps au pays d’Oz est une chaîne de Markov à 3 états

Le graphe de la situation

L’évolution du processus

Prévisions…

| Au fil des jours et en fonction de l’état initial, le processus évolue…
| Le but est de prévoir son évolution…

Vecteur d’état…

Prévoir le temps du lendemain…

Et le surlendemain ?

En termes de matrice et de graphe

Etc.

Une propriété très intéressante…

La météo au pays d’OZ…

7° Automates finis

Les automates finis

| Un automate fini est caractérisé par :
| Un ensemble fini d’états.
| Un état initial.
| Des transitions permettant de passer d’un état à un autre.
| La description d’un automate fini peut se faire au moyen d’un graphe

Un exemple : Feux tricolores

Le graphe étiqueté

Les multiples de 3

Solution classique…

Et avec un automate ?

Reconnaissance d’un décimal
signé ou non

Une solution….

Diapositive 106