Graphes - UQAC

Chapitre 5





Les graphes et leurs algorithmes


1. Introduction :

La notion de graphe est une structure combinatoire permettant de
représenter de nombreuses situations rencontrées dans des applications
faisant intervenir des mathématiques discrètes et nécessitant une solution
informatique. Circuits électriques, réseaux de transport (ferrés, routiers,
aériens), réseaux d'ordinateurs, ordonnancement d'un ensemble de tâches
sont les principaux domaines d'application où la structure de graphe
intervient.


2. Quelques exemples d'application dans les graphes



Exemple 1. Le problème des ponts de Königsberg

La ville de Königsberg comprenait 4 quartiers, séparés par des ponts. Les
habitants de Königsberg se demandaient s'il était possible, en partant d'un
quartier quelconque de la ville, de traverser tous les ponts sans passer
deux fois par le même et de revenir à leur point de départ.
Le plan de la ville peut se modéliser à l'aide d'un graphe ci-dessous, les
quartiers sont représentés par les 4 sommets, les 7 ponts par des arêtes :

[pic]
Exemple 2. Choix d'un itinéraire
Sachant qu'une manifestation d'étudiants bloque la gare de Poitiers, et
connaissant la durée des trajets suivants :

Bordeaux [pic] Nantes 4 h
Bordeaux [pic] Marseille 9 h
Bordeaux [pic] Lyon 12 h
Nantes[pic] Paris-Montparnasse 2 h
Nantes [pic] Lyon 7 h
Paris Montparnasse [pic] Paris Lyon 1 h (en autobus)
Paris-Lyon [pic] Grenoble 4 h 30
Marseille [pic] Lyon 2 h 30
Marseille[pic] Grenoble 4 h 30
Lyon [pic] Grenoble 1 h 15

Question : Comment faire pour aller le plus rapidement possible de Bordeaux
à Grenoble ?

Les données du problème sont faciles à représenter par un graphe dont les
arêtes sont
étiquetées par les durées des trajets :

[pic]

Il s'agit de déterminer, dans ce graphe, le plus court chemin entre
Bordeaux et Grenoble.


Exemple 3. Organisation d'une session d'examens

Des étudiants A, B, C, D, E et F doivent passer des examens dans
différentes disciplines, chaque examen occupant une demi-journée :

Chimie : étudiants A et B
Électronique : étudiants C et D
Informatique : étudiants C, E, F et G
Mathématiques : étudiants A, E, F et H
Physique : étudiants B, F, G et H

On cherche à organiser la session d'examens la plus courte possible.

On peut représenter chacune des disciplines par un sommet, et relier par
des arêtes les
sommets correspondant aux examens incompatibles (ayant des étudiants en
commun) :

Il s'agit alors de colorier chacun des sommets du graphe en utilisant le
moins de couleurs possible, des sommets voisins (reliés par une arête)
étant nécessairement de couleurs différentes.


[pic]

Exemple 4. Planification de travaux

Pour rénover une maison, il est prévu de refaire l'installation électrique
(3 jours), de réaménager (5 jours) et de carreler (2 jours) la salle de
bains, de refaire le parquet de la salle de séjour (6 jours) et de
repeindre les chambres (3 jours), la peinture et le carrelage ne devant
être faits qu'après réfection de l'installation électrique. Si la
rénovation est faite par une entreprise et que chacune des tâches est
accomplie par un employé différent, quelle est la durée minimale des
travaux ?
On peut représenter les différentes étapes de la rénovation sur un graphe
dont les arcs sont étiquetés par la durée minimale séparant deux étapes

[pic]

Il s'agit de déterminer la durée du plus long chemin du début à la fin des
travaux.

De manière générale, un graphe permet de représenter simplement la
structure, les connexions, les cheminements possibles d'un ensemble
complexe comprenant un grand nombre de situations, en exprimant les
relations, les dépendances entre ses éléments. En plus de son existence
purement mathématique, le graphe est aussi une structure de données
puissante pour l'informatique.

3. Définition
Un graphe G est constitué de 2 ensembles V et E. V est un ensemble non vide
de sommets. E est un ensemble de paires de sommets de V. Ces paires sont
appelés arêtes. V(G) et E(G) représentent, respectivement l'ensemble des
sommets et d'arêtes du graphe G. On écrit aussi G = (V,E) pour représenter
le graphe.
Dans un graphe non orienté, la paire de sommets représentant une arête
n'est pas ordonnées. Autrement dit, les (v1, v2) et (v2, v1) représentent
la même arête.
Dans un graphe orienté (diagraphe), chaque arête est représentée par la
paire orientée ; v1 étant l'origine et v2 l'extrémité de l'arête
dans ce cas, on ne parle plus d'arête mais d'arc. Par conséquent,
et représentent deux arcs différents. La figure ci-dessous
représentent deux graphes.
[pic]
graphe
orienté
[pic] [pic]
graphes non orienté


4. Terminologie : avant de continuer, il est utile de présenter la
terminologie (même réduite) utilisée dans la théorie des graphes.

|Terme | |
| |Signification |
|adjacence |deux arcs sont adjacents s'ils ont une extrémité |
| |commune; |
| |deux sommets sont adjacents s'il existe un arc, ou |
| |une arête, les reliant |
|arc |couple (x,y) dans un graphe orienté |
|arête |nom d'un arc, dans un graphe non orienté |
|boucle |arc reliant un sommet à lui-même |
|chaîne |Nom d'un chemin dans un graphe non orienté ; |
| |séquence d'arcs avec une extrémité commune dans un |
| |graphe orienté. |
|chemin |suite d'arcs connexes reliant un sommet à un autre. |
| | |
| |Par exemple (a;b) (b;c) (c;d) (d;b) (b;e) est un |
| |chemin reliant a à e ; |
| |on le note (a,b,c,d,b,e). |
| |Un chemin est une chaîne, la réciproque étant fausse|
|chemin eulérien|désigne un chemin simple passant une fois et une |
| |seule par toutes les arêtes du graphe ; il n'existe|
| |pas toujours... |
|chemin |désigne un chemin simple qui passe une fois et une |
|hamiltonien |seule par chaque sommet |
|chromatique |c'est le nombre minimal de couleurs nécessaires pour|
|(nombre) |colorier tous les sommets du graphe sans que deux |
| |sommets adjacents aient la même couleur ; |
| |pour les cartes de géographie, le nombre chromatique|
| |est 4 ; ce fut, |
| |en 1976, la première démonstration informatique d'un|
| |théorème mathématiques, sous réserve qu'il n'y ait |
| |pas eu de bug dans le programme... il aura fallu 700|
| |pages de listing ! |
|circuit | chemin dont l'origine et l'extrémité sont |
| |identiques |
|Connexité |Un graphe est connexe s'il existe toujours une |
| |chaîne, ou un chemin, entre deux sommets |
| |quelconques. Par exemple le plan d'une ville doit |
| |être connexe. |
|Complet |un graphe est complet si quels que soient deux |
| |sommets distincts, il existe un arc (ou une arête) |
| |les reliant dans un sens ou dans l'autre |
|Cycle |nom d'un circuit dans un graphe non orienté ; |
| |dans un graphe orienté, un cycle est une chaîne dont|
| |l'extrémité initiale coïncide avec l'extrémité |
| |finale |
|degré d'un |nombre d'arête issues d'un sommet dans un graphe non|
|sommet |orienté ; nombre d'arcs arrivant ou partant d'un |
| |sommet dans un arc orienté ; on peut vérifier |
| |facilement que la somme des degrés de tous les |
| |sommets, est donc le double du nombre des arêtes |
| |(puisque chacune est comptée deux fois). |
|Diamètre |le diamètre d'un graphe est la plus grande chaîne |
| |(chemin) de toutes reliant deux sommets quelconques|
| |du graphe |
|Distance |la distance entre deux sommets d'un graphe est la |
| |plus petite longueur des chaînes, ou des chemins, |
| |reliant ces deux sommets. |
|graphe orienté |désigne un graphe où le couple (x,y) n'implique pas |
| |l'existence du couple (y,x) ; sur le dessin, les |
| |liens entre les sommets sont des flèches |
|graphe simple |désigne un graphe non orienté n'ayant pas de boucle |
| |ni plus d'une arête reliant deux sommets. Sur le |
|