Graphes - UQAC

Les graphes et ses 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.

En tant que structures de données, les graphes sont une généralisation des
structures qu'on a vues jusqu'à présent, dans la mesure où chaque élément
d'un graphe peut posséder plusieurs prédécesseurs et plusieurs
successeurs.

2. Quelques exemples d'application pouvant être modelées par un graphe

a. Le problème des ponts de Königsberg La ville de Königsberg en Prusse
(maintenant Kaliningrad) comprenait 4 quartiers, séparés par les bras
du Prégel. 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 est comme ci-
dessous :






[pic]


















Il peut de se modéliser à l'aide d'un graphe ci-dessous, les quartiers
sont représentés par les 4 sommets et les 7 ponts par des arêtes :


[pic]


Un cycle eulérien, c'est un chemin qui passe une unique fois par toutes les
arrêtes et qui revient à son point de départ. Une chaîne eulérienne, c'est
comme un cycle, mais il n'y a pas besoin de retourner au point de départ.

b. Choix d'un itinéraire : 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

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 (ou l'un des
plus courts
chemins, s'il existe plusieurs solutions) entre Bordeaux et Grenoble.


c. 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 possibles, des sommets voisins
(reliés par une arête) étant nécessairement de couleurs.


[pic]

d. 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 et terminologie
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ée. 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é






Terminologie : un petit vocabulaire réduit

|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 non orienté. |
|chemin |suite d'arcs connexes reliant un sommet à un autre |
| |dans un graphe orienté. |
| |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... |
|circuit |chemin dont l'origine et l'extrémité sont identiques|
| |(graphe orienté) |
|connexe |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 non 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êtes issues d'un sommet dans un graphe |
|sommet |non orienté ; nombre d'arcs arrivant ou partant d'un|
| |sommet dans un arc orienté |
|diamètre |Le diamètre d'un graphe est la plus longue des |
| |distances entre deux sommets. |
|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é ; sur le dessin, les |
| |liens entre les sommets sont des segments, et on ne |
| |parle alors plus d'arcs mais d'arêtes ; |
| |tout graphe orienté peut donc être transformé en |
| |graphe simple, en remplaçant les arcs par des arêtes|
|longueur d'un |nombre d'arcs du chemin (ou d'arêtes de la chaîne) |
|chemin (ou | |
|d'une chaîne) | |
|Ordre d'un |nombre de sommets du graphe |
|graphe | |
|Prédécesseur, |Dans l'arc (x;y), x est prédécesseur de y qui est le|
|successeur |successeur de x |
|rang |le ra