Théorie des graphes : Cours de theorie des graphes
Télécharger PDFThéorie des graphes
1. Définition et concepts de base
La théorie des graphes constitue un domaine des mathématiques qui, historiquement, s'est aussi développé au sein de disciplines diverses telles que la chimie (modélisation des structures), la biologie (génome), les sciences sociales (modélisation des relations) ou en vue d'applications industrielles (problème du voyageur de commerce). Elle constitue l'un des instruments les plus courants et les plus efficaces pour résoudre des problèmes discrets posés en Recherche Opérationnelle (RO).
Un graphe permet de représenter simplement la structure, les connexions et les cheminements possibles d'un ensemble complexe comprenant un grand nombre de situations, en exprimant les relations, les dépendances entre ses éléments (exemples : réseau de communication, réseaux ferroviaires ou routiers, arbre généalogique, diagramme de succession de tâches en gestion de projet, etc.). En plus de son existence purement mathématique, le graphe est aussi une structure de données puissante pour l'informatique.
1.1 Définition "intuitive" d'un graphe
Définition 1.1 : Un graphe est un schéma constitué par un ensemble (ici supposé fini) de points et par un ensemble de traits reliant chacun de deux. Les points sont appelés les sommets du graphe, et les traits les arcs du graphe.
Exemple 1.1 : Dans le graphe ci-après, on a : - un ensemble de sommets : {a, b, c, d, e, f, g, h}, - un ensemble d'arcs : {1, 2, 3, 4, 5, 6, 7, 8, 9}.
Remarque 1.1 : "La position des sommets et la forme des arcs sur une figure n'importe pas ; seul importe de savoir comment les sommets sont reliés". Les graphes 1.3 et 1.4 sont dits isomorphes.
Notation 1.1 : L'arc 3 va du sommet e au sommet f. On dit qu'il est de la forme (e, f) et on écrit par convention que 3 = (e, f). On remarque que si la forme (g, c) existe, on peut désigner l'arc 6. Cependant, la forme (f, e) n'existe pas pour désigner l'arc 1 uniquement car 4 = (f, e) également.
1.2 Définition mathématique d'un graphe
Définition 1.2 : Un graphe G = (X, U) est le couple constitué : 1. par un ensemble X = {x₁, x₂, ..., xₙ}, 2. par une famille d'éléments U = {u₁, u₂, ..., uₘ} du produit cartésien X × X = {(x, y) / x ∈ X et y ∈ X}.
1.3 Ordre d'un graphe
Définition 1.3 : On appelle ordre du graphe G = (X, U) le nombre de sommets du graphe.
Notation 1.2 : L'ordre de G est donc le cardinal de X et noté |X|.
Exemple 1.2 : Le graphe de la figure 1.3 est d'ordre 8.
1.4 Orientation d'un graphe
Définition 1.4 (Arc) : Un arc est une paire ordonnée de sommets (x, y).
Définition 1.5 (Graphe non orienté) : Un "graphe non orienté" sera appelé un multigraphe et noté G = (X, E) avec E ⊂ P₂(X) (l'ensemble des parties à deux éléments de X).
Exemple 1.3 : Réseau de piétons.
Remarque 1.2 : Dans un multigraphe, il peut y avoir plusieurs arcs entre deux sommets.
Définition 1.6 (Arc) : Un arc est une paire ordonnée de sommets (x, y).
Définition 1.7 (Graphe orienté) : Un digraphe ou un "graphe orienté" est un graphe dont toutes les arêtes sont orientées.
Exemple 1.4 : Réseau de vol.
1.5 Multiplicité
Définition 1.8 (Boucle et extrémités) : Un arc de la forme (x, x) est une boucle.
Soit un arc de la forme (x, y), x et y sont appelés les extrémités de l'arc : - x est l'extrémité initiale de l'arc, - y est l'extrémité finale de l'arc.
Définition 1.9 (Multiplicité d'une paire (x, y)) : La multiplicité d'une paire (x, y) est le nombre d'arcs (du graphe G) ayant comme extrémité initiale x et comme extrémité finale y.
Notation 1.4 : La multiplicité d'une paire (x, y) est notée : m⁺G(x, y). On pose m⁻G(x, y) = m⁺G(y, x) et mG(x, y) = m⁻G(x, y) + m⁺G(x, y). - Si x ≠ y alors mG(x, y) est le nombre d'arcs ayant une extrémité en x et une en y. - Si x = y alors mG(x, y) vaut deux fois le nombre de boucles en x.
1.6 Degrés
a) Degré d'un sommet
Définition 1.10 : Pour un graphe ou un multigraphe, on appelle degré du sommet x, et on note d(x), le nombre d'arcs ayant une extrémité en x. Attention : une boucle sur un sommet est comptée deux fois.
Exemple 1.5 : Dans le graphe de la figure 1.3, dG(e) = 5, dG(c) = ?.
Lemme 1.1 (Lemme des poignées de main) : La somme des degrés des sommets d'un multigraphe est égale à deux fois le nombre d'arcs.
Exemple 1.6 : Dans le graphe 1.6, on a les degrés : d(x₁) = 2, d(x₂) = 1, d(x₃) = 3, d(x₄) = 2, d(x₅) = 1, d(x₆) = 1, et le nombre d'arcs est égal à 5.
b) Degré d'un graphe
Définition 1.11 : Le degré d'un graphe est le degré maximum de tous ses sommets.
Un graphe dont tous les sommets ont le même degré est dit régulier. Si le degré commun est k, alors on dit que le graphe est k-régulier.
Exemple 1.7 : Dans l'exemple 1.6, le degré du graphe est 3.
Exercice 1.1 : Est-il possible de relier 15 ordinateurs de sorte que chaque appareil soit relié avec exactement trois autres ?
1.7 Relations entre sommets
Définition 1.12 (Sommets voisins) : - Le sommet y est un successeur du sommet x s'il existe un arc de la forme (x, y). - Le sommet y est un prédécesseur du sommet x s'il existe un arc de la forme (y, x). - Le sommet y est un voisin ou adjacent du sommet x s'il existe un arc de la forme (x, y) ou (y, x) (autrement dit si y est un successeur ou un prédécesseur de x). - Un sommet pendant est un sommet qui n'a qu'un seul voisin.
Notation 1.5 : - L'ensemble des successeurs du sommet x est noté Γ⁺(x). - L'ensemble des prédécesseurs du sommet x est noté Γ⁻(x). - L'ensemble des voisins ou des sommets adjacents du sommet x est noté Γ(x) = Γ⁺(x) + Γ⁻(x).
Exemple 1.8 : Dans le graphe de la figure 1.3, Γ(e) = Γ⁺(e) + Γ⁻(e) = {f, h} ∪ {f, d} = {f, d, h}.
1.8 Quelques types de graphes
a) p-graphe
Définition 1.13 : Soit un graphe G = (X, U), si le nombre d'arcs qui vont d'un sommet x à un sommet y de X est inférieur ou égal à p (pour tous les sommets x et y de U), alors on dit que G est un p-graphe.
Notation 1.6 : G = (X, U) est un p-graphe ⇔ ∀(x, y) ∈ X² / |{u ∈ U, u = (x, y)}| ≤ p.
Exemple 1.9 : Le graphe de la figure 1.3 est un 2-graphe (m⁺G(f, e) = 2).
b) Graphe simple
Définition 1.14 : Un graphe simple est un multigraphe : - sans boucles, - tel qu'il n'y ait jamais plus d'une arête entre deux sommets quelconques.
Exemple 1.7 : Un exemple de graphe simple.
c) Graphe complet
Définition 1.15 : Un graphe est complet si chaque sommet du graphe est relié directement à tous les autres sommets.
Exemple 1.8 : Un exemple de graphe complet.
d) Graphe biparti
Définition 1.16 : Un graphe est biparti si ses sommets peuvent être divisés en deux ensembles X et Y, de sorte que toutes les arêtes du graphe relient un sommet dans X à un sommet dans Y.
Exemple 1.9 : Un exemple de graphe biparti.
Exercice 1.2 : Un tournoi oppose 6 équipes. Chaque équipe doit affronter toutes les autres. 1. Construisez un graphe représentant toutes les parties possibles. 2. Quel type de graphe obtenez-vous ? 3. Si chaque équipe ne joue qu'un match par jour, combien de jours faudra-t-il pour terminer le tournoi ?
2. Représentations d'un graphe
Nous aimons bien communiquer par des dessins, mais les machines n'y sont pas encore adaptées : il faut donc trouver d'autres façons de représenter les graphes.
La solution consiste à utiliser des matrices, et il y a différentes méthodes.
2.1 Matrice d'incidence sommets-arcs
Définition 1.17 : La matrice d'incidence ou d'incidence sommets-arcs d'un graphe G = (X, U) sans boucle est une matrice telle que chaque colonne correspond à un arc de G et chaque ligne à un sommet de G. Si u = (i, j) ∈ U, la colonne u a tous ses termes nuls, sauf : - aᵢⱼ = +1, - aⱼᵢ = −1.
Exemple 1.10 : On donne comme exemple la matrice d'incidence sommets-arcs du graphe partiel sans boucle engendré par l'ensemble des arcs du graphe de la figure 1.3 privé de l'arc 5 (la boucle).
2.2 Matrice d'adjacence ou d'incidence sommets-sommets
Définition 1.18 : La matrice d'adjacence ou d'incidence sommets-sommets d'un graphe G = (X, U) est une matrice carrée où chaque ligne correspond à un sommet de G et chaque colonne correspond également à un sommet de G. Le terme général de la matrice est : aᵢⱼ tel que : - aᵢⱼ = m⁺G(xᵢ, xⱼ) signifie que le sommet xᵢ est adjacent au sommet xⱼ, - aᵢⱼ = 0 sinon.
En cas de boucle (pour le sommet i, par exemple), on place un 1 sur la diagonale (en position (i, i)).
Exemple 1.11 : On donne comme exemple la matrice d'adjacence sommets-sommets associée au graphe de la figure 1.
Remarque 1.3 : La matrice d'adjacence d'un graphe non orienté est symétrique : aᵢⱼ = aⱼᵢ.
3. Connexité dans les graphes
3.1 Chaînes et cycles
Définition 1.19 : Une chaîne dans G est une suite de la forme (x₀, u₁, x₁, u₂, ..., xₖ₋₁, uₖ, xₖ) ayant pour éléments alternativement des sommets (xᵢ) et des arcs (uᵢ), commençant et se terminant par un sommet, et telle que les extrémités de uᵢ soient xᵢ₋₁ et xᵢ, i = 1, ..., k. Si x₀ = a et xₖ = b, on dira que la chaîne relie a et b. En plus, on dira que la chaîne a une longueur k (c'est le nombre d'arcs de la chaîne). Une chaîne doit comporter au moins un arc.
Le graphe 1.10 contient les chaînes (x₁, u₃, x₃, u₄, x₄) et (x₄, u₄, x₃, u₂, x₂, u₁, x₁), entre autres.
On ne change pas une chaîne en inversant l'ordre des éléments dans la suite correspondante ; ainsi les chaînes (x₁, u₃, x₃, u₄, x₄) et (x₄, u₄, x₃, u₃, x₁) sont identiques.
On appelle distance entre deux sommets la longueur de la plus petite chaîne les reliant.
Le diamètre d'un graphe est la plus longue des distances entre deux sommets.
Une chaîne est élémentaire si chaque sommet y apparaît au plus une fois.
Une chaîne est simple si chaque arc apparaît au plus une fois. Dans le graphe 1.10, (x₁, u₁, x₂, u₂, x₃) est une chaîne simple et élémentaire.
Une chaîne telle que x₀ = xₖ est appelée chaîne fermée. Dans le graphe 1.10, (x₂, u₂, x₃, u₄, x₄, u₄, x₃, u₂, x₂) est une chaîne fermée.
Une chaîne fermée simple est appelée cycle si seul le sommet de départ apparaît deux fois dans la chaîne. Dans le graphe 1.10, (x₂, u₂, x₃, u₄, x₄, u₅, x₂) est un cycle.
Théorème 1.1 : Un graphe est biparti et seulement s'il ne contient aucun cycle de longueur impaire.
3.2 Chemins et circuits
Ces notions sont les mêmes définitions que les précédentes, mais en considérant des concepts orientés.
Un chemin conduisant du sommet x au sommet y est une suite de la forme (x₀, u₁, x₁, u₂, ..., xₖ₋₁, uₖ, xₖ). Sur le digraphe 1.11, on peut voir par exemple le chemin (x₃, u₂, x₂, u₁, x₁). Par convention, tout chemin comporte au moins un arc.
On appelle distance entre deux sommets d'un digraphe la longueur du plus petit chemin les reliant. S'il n'existe pas de chemin entre les sommets x et y, on pose d(x, y) = ∞. Par exemple, sur le digraphe 1.11, d(x₁, x₂) = 2, d(x₄, x₃) = 1, d(x₃, x₄) = ∞.
Un circuit est un chemin avec x₀ = xₖ. Le digraphe 1.11 contient un circuit en partant de x₁.
Les notions de longueur, de chemins et de circuits sont analogues à celles des chaînes et des cycles pour le cas non orienté.
3.3 Fermeture transitive d'un graphe
Le calcul de la fermeture transitive permet de répondre aux questions concernant l'existence de chemins entre x et y dans G et ce pour tout couple de sommets (x, y).
Définition 1.20 : On appelle fermeture transitive d'un graphe G =