Dans ce cours, nous utiliserons la virgule pour séparer les éléments d'un ensemble, en référence à la façon dont la plupart des langages de programmation séparent les éléments.
En mathématiques, on utilise usuellement plutôt le point-virgule.
Les graphes sont des objets mathématiques
très utilisés, notamment en informatique.
Des protocoles pour le routage à l'intérieur des systèmes autonomes et d'autres protocoles pour le routage entre les systèmes autonomes
Ils se prêtent très bien à la modélisation d'un nombre important de problèmes, notamment ceux impliquant de grands nombres de relations entre différentes entités :
Relations sociales : relations entre des individus
Réseaux routiers : relations entre des croisements (carrefours, ronds-points, échangeurs d'autoroute)
Réseaux Internet : relations entre des routeurs
Plan du Web : relations entre les sites Web (liens)
Automates : relations entre les états de l'automate
Bases de données : relation entre les tables.
Gestion de projets : relation entre les différentes parties du projet
...
Avant de commencer, regardons d'où provient cette notion : la ville de Königsberg comporte 7 ponts pasant au dessus du Pregel, représentés sur le plan ci-dessus. Le problème consistait à déterminer s'il existe ou non une promenade dans les rues de Königsberg permettant de passer une et une seule fois par chaque pont, et de revenir à son point de départ.
Pour résoudre ce problème, on commence par partir du problème réel qu'on va peu à peu représenté par des notions de plus en plus abstraite jusqu'à aboutir au graphe.
Images CC tirées de la page wikipédia sur le problème des 7 ponts
Sur le graphe de droite, on voit que les points représentent la partie nord de la ville, la partie sud de la ville et les deux iles. Les traits représentent eux le passage d'un pont.
Une telle promenade n'existe pas, et c'est Euler qui donna la solution de ce problème en caractérisant les graphes que l'on appelle aujourd'hui « eulériens » en référence à l'illustre mathématicien.
1.1 Idée générale du graphe non orienté (1er partie de la définition)
Définitions générales
Un graphe non orienté est une structure relationnelle qui met en relation des données entre elles. La relation est symétrique : si A est en relation avec B, B est en relation avec A.
Les sommets sont les données dont on désire connaître les relations. On les représente graphiquement par un cercle le plus souvent.
Les sommets sont caractérisés par leurs étiquettes.
Sur le graphe ci-dessus, les étiquettes sont donc A, B, C, D, E, F et G.
Les arêtes sont les liens symétriques reliant directement deux sommets entre eux. On les représente habituellement comme un simple trait reliant deux sommets.
Sur le graphe ci-dessus, on voit qu'il y a une arête entre A et B : on en déduit que A est en relation avec B et que B est en relation avec A puisque la relation est symétrique.
Pas contre, A n'est pas en relation directement avec F car il n'y a pas d'arête entre A et F.
L'ordre d'un graphe correspond à son nombre de sommets.
Ce graphe est d'ordre 7.
Le degré d'un sommet correspond au nombre d'arêtes liées à ce sommet.
Ci-dessous, le degré du sommet A est 3, le degré de G est 2.
Deux sommets sont adjacents si ils sont reliés par une arête.
A et B sont adjacents, D et E sont adjacents...
Définition mathématique formelle du graphe non orienté
Un graphe non orienté simple est un couple G = (S,A) contenant deux ensembles :
Un ensemble S des sommets ;
Un ensemble A des arêtes où une arête est un ensemble {s1, s2} de 2 sommets.
Ci-dessous, les arêtes sont indiquées en rouge.
S = {a, b, c, d, e, f}
A = { {a,b}, {a,c}, {a,d}, {b,c}, {d,e}, {d,f} }
Les arêtes sont symbolisées par des ensembles car l'ensemble {a,b} est équivalent à l'ensemble {b,a}. Cela correspond bien à la notion de symétrie voulue.
Cette définition de l'arête vue comme un ensemble a deux conséquences majeures :
Les boucles ne sont donc pas représentables rigoureusement puisqu'un élément ne peut apparaitre qu'un unique fois dans un ensemble : {b,b} n'est pas un ensemble de deux éléments mais correspond juste à {b}.
Les arêtes multiples entre deux sommets ne sont représentables avec notre interprétation formelle : sur le graphe ci-dessous, on devrait noter A = { ... {a,d}, {a,d} ...} ce qui n'est pas rigoureuseument possible : l'élément {a,d} apparaitrait deux fois dans A.
Nous ne pourrons donc pas représenter rigoureusement deux salles comportant deux portes communes avec cette définition.
Un graphe non orienté simple est un graphe non orienté qui ne possède aucune boucle et aucune arête multiple. C'est le graphe non orienté étudié cette année.
Lorsqu'on parle de graphe non orienté sans précision, on parle le plus souvent d'un graphe simple.
Un multigraphe non orienté est un graphe non orienté qui possède des boucles et/ou des arêtes multiples.
01° Donner les ensembles S et A de ce graphe non orienté G = (S, A) :
Consigne supplémentaire
Vous donnerez l'ensemble A en ordonnant les arêtes selon l'ordre lexicographique :
{a,c} < {a,d} < {b,a} par exemple.
...CORRECTION...
S = {a, b, c, d}
A = { {a, b}, {a, c}, {b, c}, {c, d} }
02° Dessiner un graphe G' qui aurait exactement les mêmes ensembles S et A mais une représentation graphique différente.
...CORRECTION...
1.2 Chaîne dans un graphe non orienté : succession d'arêtes
flowchart LR
subgraph a[Chaînes]
subgraph b[Chaînes simples]
c[Chaînes élémentaires]
end
b
end
Définitions
Une chaîne est une succession d'arêtes permettant de passer d'un sommet de départ à un sommet d'arrivée.
La longueur d'une chaîne correspond au nombre d'arêtes à emprunter pour relier les deux sommets.
On utilise parfois le terme chemin, normalement plutôt destiné aux graphes orientés.
Une chaîne simple est une chaîne dans laquelle toutes les arêtes sont différentes.
Une chaîne élémentaire est une chaîne simple dans laquelle tous les sommets sont différents.
Exception : si le sommet de départ et d'arrivée sont le même, on ne tient pas compte de cette répétition dans la définition.
Une chaîne élémentaire est nécessairement une chaîne simple puisqu'emprunter deux fois la même arête amène nécessairement vers un sommet déjà visité.
Exemples
Exemple 1 : chaîne ni simple ni élémentaire
La chaîne {d,a}{a,b}{b,a} ci-dessus est de longueur 3 car on emprunte 3 arêtes.
Notez que nous aurions pu donner les arêtes simplement par {a,d}{a,b}{a,b} puisqu'une arête ne possède deux extrémités symétriques.
Ce n'est pas une chaîne simple puisqu'on utilise deux fois l'arête {a,b} sur les étapes 2 et 3.
Ce n'est pas une chaîne élémentaire puisqu'elle n'est pas simple (et qu'on rencontre le sommet a deux fois sans qu'il soit le sommet de départ et d'arrivée).
On peut également écrire la chaîne en donnant les sommets rencontrés d-a-b-a = {a,d}{a,b}{a,b}; mais attention : sa longueur est bien 3, pas 4. C'est le nombre d'arêtes qui est important.
Exemple 2 : chaîne élémentaire
La chaîne b-a-d-e = {a,b}{a,d}{d,e} est une chaîne élémentaire de longueur 3 puisqu'on utilise jamais deux fois le même sommet.
Remarque : cette chaîne est donc également simple puisqu'on n'utilise jamais deux fois la même arête.
Exemple 3 : chaîne simple mais non élémentaire
La chaîne b-a-d-g-a-c = {b,a}{a,d}{d,g}{g,a}{a,c} est une chaîne simple de longueur 5 puisqu'on utilise jamais deux fois la même arête.
Par contre, elle n'est pas élémentaire puisqu'on utilise deux fois le sommet a sans qu'il soit le départ et l'arrivée.
Pourquoi faire ?
Cette décomposition va nous permettre d'éviter de faire tourner les algorithmes de recherche sur des boucles infinies.
Nous n'allons utiliser que des chaînes simples car une chaîne NON simple permet de tourner en rond.
Or, une chaîne simple se décompose toujours en une concaténation de chaînes élémentaires. L'étude locale des chaînes élémentaires et des combinaisons qu'on peut en faire permet de retrouver les propriétés globales du graphe.
03° On travaillera sur le graphe ci-dessous.
Donner une chaîne élémentaire de longueur 6.
Donner une chaîne de longueur 6 qui soit simple mais pas élémentaire.
Donner une chaîne de longueur 6 qui ne soit pas simple (et donc pas élémentaire non plus).
...CORRECTION...
C - B - F - G - E - D - A
C - B - F - G - E - F - D passe deux fois en F.
C - B - A - D - F - B - C utilise deux fois l'arête {B, C}.
1.3 Chaînes particulières : boucle et cycle
Boucle
Une boucle est une arête reliant directement un sommet à lui-même.
Un graphe possèdant une boucle n'est pas un graphe simple mais plutôt un multigraphe.
Cycle
Un cycle est une chaîne fermée, partant d'un sommet et y revenant.
Un cycle simple est une chaîne simple fermée (simple donc on n'emprunte jamais deux fois la même arête).
Le cycle {d,a}{a,b}{b,c}{c,a}{a,g}{g,d} est un cycle de longueur 6 car il emprunte 6 arêtes différentes pour revenir à d.
Ce n'est pas un cycle élémentaire puisqu'il passe deux fois par le sommet a.
Un cycle élémentaire est un cycle simple dans lequel on ne rencontre jamais un même sommet deux fois (à part le sommet de départ-arrivée).
Le cycle {a,b}{b,c}{c,a} ci-dessous est un cycle élémentaire car il ne passe jamais deux fois par le même sommet si on met de côté le sommet de départ-arrivée.
La question de savoir si une boucle est un cycle élémentaire de longueur 1, ou pas, n'est pas réellement tranchée dans la littérature. Cela dépend du point du vue et surtout du type de graphe sur lequel on travaille.
Pourquoi faire ?
Les cycles simples contiennent nécessairement au moins un cycle élémentaire. Pour éviter de faire tourner en rond nos fonctions dans les graphes, il nous faudra donc simplement éviter les cycles élémentaires.
A titre d'exemple, voici le résultat d'un programme dont la seule consigne est de tourner à gauche dès qu'il le peut :
Cliquez sur l'image pour lancer l'animation du cycle
La détection de cycle dans un graphe est assez facile : il suffit de l'explorer et de stopper si on retombe sur un sommet que nous avons déjà visité. Cela veut dire que nous venons de détecter un cycle élémentaire.
L'exploration complète du graphe ne peut pas fonctionner ainsi par contre : on ne veut pas arrêter le système lorsqu'il arrive en a puisqu'on peut encore explorer ce que se passe vers d. Nous allons voir dans la partie algorithmique comment explorer efficacement un graphe. Mais l'idée fondamentale est bien celle-ci : ne jamais utiliser deux fois une arête. Lors de l'exploration, nous allons donc nous limiter aux chaînes simples.
Acyclique
Un graphe acyclique est un graphe dans lequel il n'existe pas de cycle simple : si on programme notre fonction d'exploration pour ne jamais emprunter deux fois une même arête, on ne peut pas tourner en rond.
Il faudra prendre plus de précautions si on ne connaît pas la nature du graphe.
04° Donner un cycle élémentaire
de longueur 3
de longueur 4
de longueur 5
de longueur 6
de longueur 7
...CORRECTION...
Elémentaire donc pas deux fois le même sommet.
3 : A - B - C - A
4 : A - B - F - D - A
5 : A - B - F - E - D - A
6 : A - B - F - G - E - D - A
7 : A - C - B - F - G - E - D - A
On peut faire quelques sujets de Grand Oral intéressants sur les deux problèmes décrits ci-dessous.
Cycle Eulérien
Un cycle simple utilise une arête une fois au maximum, mais certaines arêtes peuvent ne pas être utilisées. Un cycle Eulerien est un cycle dans lequel on utilise toutes les arêtes (une unique fois). Le nom "cycle Euleurien" fait bien entendu référence aux passages de ponts dans le problème des 7 ponts de Königsberg.
Cycle Hamiltonien
Un cycle élémentaire utilise un sommet une fois au maximum, mais certains sommets peuvent ne pas être visités. Un cycle Hamiltonien est un cycle dans lequel on visite tous les sommets (une unique fois). Dans un graphe hamiltonien, on peut donc ne pas emprunter certaines arêtes.
Un algorithme capable de déterminer si un graphe quelconque contient un cycle hamiltonien fait partie des problèmes NP-complet, alors que créer un algorithme capable de déterminer si un graphe quelconque est eulérien est un problème polynomial.
1.4 Les primitives de création et modification (2e partie de la définition du graphe)
Quelques primitives des graphes non orientés
S'agissant d'un type abstrait, on donne une version immuable, l'économie de la mémoire n'ayant aucune importance tant qu'on reste dans le domaine abstrait.
nvGraphe() -> GrapheNonOrienté VIDE
estGrapheVide(g:GrapheNonOriente) -> bool
Prédicat qui renvoie Vrai si le graphe non orienté est vide, c'est à dire que son contenu est ({},{}).
Renvoie le sommet qu'on atteint en utilisant la i-ème arête de A qui comporte le sommet s.
Les primitives ordre() degre() sont nécessaires pour utiliser les autres primitives. Sans elles, impossible de savoir si les préconditions "indice valide" sont vraies, ou pas.
Exemples
On considère le graphe G = (S,A) suivant :
S = {a, b, c, d, e, f}
A = { {a,b}, {a,c}, {a,d}, {b,c}, {d,e}, {d,f} }
Regardons les arêtes de A qui comporte le sommet d par exemple :
A = { {a,b}, {a,c}, {a,d}, {b,c}, {d,e}, {d,f} }
utiliserArete(graphe, d, 0) renvoie a
utiliserArete(graphe, d, 1) renvoie e
utiliserArete(graphe, d, 2) renvoie f
08° Donner les sommets rencontrées si on utilise cet algorithme sur le graphe G proposé :
S = {a, b, c, d, e, f}
A = { {a,b}, {a,c}, {a,d}, {b,c}, {d,e}, {d,f} }
Dans l'algorithme proposé, on considère que le graphe G=(S,A) ci-dessus est accessible depuis la variable graphe.
On utilise la numérotation habituelle en informatique : on commence par 0.
graphe ← (S,A)
s ← sommet(graphe, 3)
deplacements ← tableau vide
Ajouter s dans deplacements
TANT QUEs est différent du sommet e
s ← utiliserArete(graphe, s, 0)
Ajouter le sommet s à la fin du tableau deplacements
Fin du TANT QUE
Renvoyerdeplacements
Quel va être le problème majeur lors de l'exploration des graphes ?
...CORRECTION...
Le sommet 3 initial est le sommet d : c'est celui d'indice 3 dans l'ensemble S fourni.
On réalise la boucle TANT QUE le sommet s n'est pas le sommet e.
On utilise à chaque fois la première arête où le sommet s en cours apparait.
Si on applique cela, on obtient :
deplacement = [d]
deplacement = [d, a]
deplacement = [d, a, b]
deplacement = [d, a, b, a]
deplacement = [d, a, b, a, b]
...
On voit donc qu'on va tourner en boucle en utilisant constamment ensuite l'arête entre a et b.
Un graphe orienté est une structure relationnelle qui met en relation des données entre elles. Les relations ne sont pas nécessairement symétriques : si A est en relation avec B, B n'est pas obligatoirement en relation avec A.
Les liens d'un graphe orienté sont nommés arcs.
Les sommets sont les données dont on désire connaître les relations. On les représente graphiquement par un cercle le plus souvent.
Les sommets sont caractérisés par leurs étiquettes.
Sur le graphe ci-dessus, les étiquettes sont donc a, b, c, d, e, et f.
Les arcs sont les liens reliant un sommet source s1 et un sommet destination s2. Il s'agit donc d'un couple (s1, s2). On les représente graphiquement comme une flèche s1->s2 reliant deux sommets.
Sur le graphe ci-dessus, on voit qu'il y a un arc entre b et c mais pas entre c et c.
Par contre, il peut exister des liens dans les deux sens. Dans ce cas, on aura un arc dans un sens et un arc dans l'autre sens : c'est ce qu'on observe entre a et b par exemple.
L'ordre d'un graphe correspond à son nombre de sommets.
Ce graphe est d'ordre 6.
Chaque sommet possède deux degrés.
Le degré entrant correspond au nombre d'arcs qui mènent à ce sommet s. Il s'agit de compter les arcs tels que (*,s).
Le degré sortant correspond au nombre d'arcs qui sortent de ce sommet s. Il s'agit de compter les arcs tels que (s,*).
Le degré entrant du sommet a est 3 car il existe 3 arcs qui mènent à a : (b,a) (c,a) (d,a)
Le degré sortant du sommet a est 2 car il existe 2 arcs qui sortent de a : (a,b) (a,d)
On dit que s1 est adjacent à s2 si et seulement si il existe un arc (s1,s2), c'est à dire de s1 vers s2.
Dans un graphe orienté, l'adjacence est donc liée à la notion de marche avant, de successeurs.
La liste d'adjacence d'un sommet s1 contient les successeurs s2 possibles en partant du sommet s1.
Dans un graphe orienté, l'adjacence n'est donc pas nécessairement symétrique.
La liste d'adjacence de a est [b,d].
La liste d'adjacence de c est [a].
Définiton mathématique formelle du graphe orienté
Un graphe orienté simple est un couple G = (S,A) contenant deux ensembles :
Un ensemble S des sommets ;
Un ensemble A des arcs où un arc est un couple(s1, s2) de 2 sommets.
Avec cet exemple, on voit qu'on peut se déplacer directement de a vers b mais pas de b vers a en un seul déplacement.
Les arcs sont symbolisés par des couples car le couple (a,b) symbolise un arc "a vers b", différent du couple (b,a) qui symbolise un arc "b vers a". Cela correspond bien à la notion de non-symétrie voulue.
Cette définition des arcs comme des 2-uplets a deux conséquences majeures :
Les boucles sont représentables formellement puisqu'une boucle sur b peut être représentée par le couple (b, b).
Les arcs multiples entre deux sommets ne sont pas représentables rigoureusement. Sur le graphe ci-dessous, on devrait créer un ensemble où l'élément (a,d) apparait deux fois :
A = { ... (a,d), (a,d) ...}.
Nous ne pourrons donc pas représenter rigoureusement deux salles comportant deux portes communes avec cette définition.
Un graphe orienté simple est un graphe orienté qui ne possède aucune boucle et aucune arête multiple.
Notez que la définition est similaire à celle du graphe non orienté, même si le graphe orienté peut contenir des boucles de façon rigoureuse.
Un multigraphe orienté est un graphe orienté qui peut possèder des arêtes multiples.
09° Donner les ensembles S et A de ce graphe orienté G = (S, A) :
Consigne supplémentaire
Vous donnerez l'ensemble A en ordonnant les arêtes selon l'ordre lexicographique :
Nous allons revoir les notions de chaînes et cycles vues pour les graphes non orientés.
On les nomme habituellement plutôt chemins et circuits dans les graphes orientés.
2.2 Chemin dans un graphe orienté : succession d'arcs
flowchart LR
subgraph a[Chemins]
subgraph b[Chemins simples]
c[Chemins élémentaires]
end
b
end
Définitions
Un chemin est une succession d'arcs correctement orientés permettant de passer d'un sommet de départ à un sommet d'arrivée.
La longueur d'un chemin correspond au nombre d'arcs à emprunter pour relier les deux sommets.
Un chemin est donc l'équivalent orienté d'une chaîne.
Un chemin simple est un chemin dans lequel tous les arcs sont différents.
Un chemin élémentaire est un chemin simple dans lequel tous les sommets sont différents.
Exception : si le sommet de départ et d'arrivée sont le même, on ne tient pas compte de cette répétition dans la définition.
Exemples
Exemple 1 : chemin pas simple
C'est beaucoup plus "dur" à réaliser qu'avec un graphe orienté car revenir par un arc inverse ne compte pas comme l'utilisation du même lien. Avec un graphe orienté, il faut vraiment retourner sur ses pas et reprendre l'arc pour l'utiliser deux fois.
Le chemin (d,a)(a,b)(b,c)(c,a)(a,b)(b,c)(c,a)(a,d)(d,e) ci-dessus est de longueur 9 car on emprunte 9 arcs.
Ce n'est pas un chemin simple puisqu'on utilise deux fois certains arcs ( (a,b) (b,c) (c,a) ).
Attention, (a,b) et (b,a) ne représentent pas le même arc, contrairement aux arêtes {a,b} et {b,a}.
Ce n'est pas un chemin élémentaire qu'on rencontre deux fois certains sommets sans qu'ils soient le sommet de départ et d'arrivée.
Exemple 2 : chemin élémentaire
Le chemin (d,a)(a,b)(b,c) est un chemin élémentaire de longueur 3 puisqu'on utilise jamais deux fois le même sommet.
Remarque : ce chemin est également simple puisqu'on n'utilise jamais deux fois le même arc.
Exemple 3 : chemin simple mais non élémentaire
Le chemin d-a-b-c-a-d-e = (d,a)(a,b)(b,c)(c,a)(a-d)(d-e) est un chemin simple de longueur 6 puisqu'on utilise jamais deux fois le même arc.
Par contre, il n'est pas élémentaire puisqu'on traverse deux fois le sommet a ou le sommet d, sans qu'ils soient à la fois le départ et l'arrivée.
Pourquoi faire ?
Un chemin se décompose toujours en une concaténation de chemins élémentaires. L'étude locale des chemins élémentaires et des combinaisons qu'on peut en faire permet de retrouver les propriétés globales du graphe.
10° Lancer l'animation ci-dessous puis répondre aux questions.
Cliquez sur l'image pour lancer l'animation du chemin
Définir le nom de ce chemin : chemin, chemin simple, chemin élémentaire ?
Donner les arcs suivies le long de ce chemin.
Compléter le chemin pour le rendre non élémentaire.
...CORRECTION...
C'est un chemin élémentaire car il n'emprunte chaque sommet qu'une fois au maximum. C'est donc également un chemin et un chemin simple.
(d,a) (a,b) (b,c)
(d,a) (a,b) (b,c) (c,a) : on revient en a qu'on a déjà visité sans qu'il soit le sommet de départ : ce chemin n'est plus élémentaire.
2.3 Chemins particuliers : boucle et circuit
Boucle
Une boucle est une arc reliant directement un sommet à lui-même.
Un graphe orienté possèdant une boucle n'est pas un graphe simple même si la boucle est parfaitement représentable dans un graphe orienté.
Circuit ("cycle orienté")
Un circuit est un chemin fermé, partant d'un sommet et y revenant.
Le mot circuit de voitures fait bien référence à ce type de chemin : on suit un chemin dans un sens particulier et on y revient.
Un circuit simple est un chemin simple fermé (simple donc on n'emprunte jamais deux fois le même arc).
Le circuit d-a-b-c-a-d = (d,a)(a,b)(b,c)(c,a)(a,d) est un circuit de longueur 5 car il emprunte 5 arcs différents pour revenir à d.
Ce n'est pas un circuit élémentaire puisqu'il passe deux fois par le sommet a.
Un circuit élémentaire est un circuit simple dans lequel on ne rencontre jamais un même sommet deux fois (à part le sommet de départ-arrivée).
Le circuit a-b-c = (a,b)(b,c)(c,a) ci-dessous est un cycle élémentaire car il ne passe jamais deux fois par le même sommet si on met de côté le sommet de départ-arrivée.
Et c'est là qu'on voit bien la différence avec le graphe non orienté : dans un graphe orienté, le circuit ci-dessous est bien un circuit élémentaire.
Pourquoi faire ?
Exactectement comme sur les graphes non orientés.
La détection de cycle consiste à détecter un circuit élémentaire : le fait de revenir sur un sommet déjà visité.
L'exploration complète du graphe nécessite par contre de juste se limiter aux chemins simples, sinon nous risquons de passer à côté de certains chemins.
Acyclique
Un graphe acyclique est un graphe dans lequel il n'existe pas de cycle simple : si on programme notre fonction d'exploration pour ne jamais emprunter deux fois une même arête, on ne peut pas tourner en rond.
Il faudra prendre plus de précautions si on ne connaît pas la nature du graphe.
11° Donner un circuit élémentaire
de longueur 2
de longueur 3
de longueur 4
de longueur 5
de longueur 6
...CORRECTION...
(a,b) (b,a)
(a,b) (b,c) (c,a)
(a,e) (e,f) (f,d) (d,a)
(a,b) (b,c) (c,e) (e,d) (d,a)
(a,b) (b,c) (c,e) (e,f) (f,d) (d,a)
Nous n'utiliserons pas ici les primitives sur les graphes orientés. Ce sont les mêmes que sur les graphes non orientés. On utilise juste le terme arc plutôt qu'arête. Les deux bouts de cours ci-dessous sont donc comme un compléments, inutile de les étudier réellement. A part leurs noms, rien ne change réellement.
La seule vraie différence vient de l'existence de deux primitives de déplacement avancer() pour utiliser un arc "dans le bon sens" et reculer() pour remonter vers un sommet successeur.
[OPTIONNEL] 2.4 Les primitives de création et modification (2e partie de la définition du graphe)
Quelques primitives des graphes orientés
S'agissant d'un type abstrait, on donne une version immuable, l'économie de la mémoire n'ayant aucune importance tant qu'on reste dans le domaine abstrait.
nvGraphe() -> GrapheOrienté VIDE
estGrapheVide(g:GrapheOriente) -> bool
Prédicat qui renvoie Vrai si le graphe orienté est vide, c'est à dire que son contenu est ({},{}).
Renvoie le sommet qu'on atteint en utilisant le i-ème arc (x,s) entrant qui comporte le sommet s en dernière position.
Les primitives ordre() degre() sont nécessaires pour utiliser les autres primitives. Sans elles, impossible de savoir si les préconditions "indice valide" sont vraies, ou pas.
Exemples
On considère le graphe G = (S,A) suivant :
S = {a, b, c, d, e, f}
A = { {a,b}, {a,c}, {a,d}, {b,c}, {d,e}, {d,f} }
Regardons les arêtes de A qui comporte le sommet d par exemple :
A = { {a,b}, {a,c}, {a,d}, {b,c}, {d,e}, {d,f} }
utiliserArete(graphe, d, 0) renvoie a
utiliserArete(graphe, d, 1) renvoie e
utiliserArete(graphe, d, 1) renvoie f
12° Nous pourrions croire que les deux graphes ci-dessous sont similaires. Après tout, nous avons remplacé chaque arête du graphe non orienté par un couple d'arcs sur le graphe orienté.
Vous allez voir que les deux graphes n'ont pourtant pas les mêmes propriétés.
Commençons par observer un cycle sur le graphe orienté :
Cliquez sur l'image pour lancer l'animation du cycle
Question A
Pour éviter de tourner en rond, notre programme informatique refuse d'emprunter un arc déjà utilisé. Le circuit visible sur l'exemple est-il circuit simple ou un circuit élémentaire ?
Transformons le graphe en sa version non orientée. C'est facile, il suffit de transformer toute liaison en arête. Normalement, il est donc plus simple de se déplacer.
Regardons si nous pouvons réaliser un cycle simple comme sur notre graphe orienté.
Cliquez sur l'image pour lancer l'animation du chemin simple sur un graphe non orienté
Question B
Pour éviter de tourner en rond, notre programme informatique refuse d'emprunter une arête déjà utilisée. Après avoir visualisé l'animation, pourquoi n'est-il pas possible de réaliser sur le graphe non orienté le cycle simple qui correspondrait au circuit simple du graphe orienté ?
...CORRECTION...
Question A
On emprunte une série d'arcs tous différents (le circuit est donc simple) mais on passe deux fois pas a (le circuit n'est donc pas élémentaire).
Question B
On ne peut pas réaliser le cycle simple car lorsqu'on emprunte l'arête {d, a}, l'algorithme ne pourra plus l'emprunter pour revenir.
2.6 Différence entre l'exploration d'un graphe orienté et non orienté
Idée générale
Nous avons vu que pour explorer l'intégralité d'un graphe, il ne faut pas être trop restrictif (sinon on va rater des zones possibles), ni trop laxiste (sinon on risque de tourner en rond).
Pour cela, l'idée fondamentale est de ne pas permettre d'emprunter une liaison déjà utilisée.
Graphe non orienté : activation d'une arête
Pour les graphes non orientés, cela veut dire ne pas accepter d'utiliser deux fois la même arête (quelque soit le sens de la première utilisation). Activer l'arête {a,b} va donc empêcher de l'emprunter en sens inverse.
Graphe orienté : activation d'un arc
Pour les graphes orientés, cela veut dire ne pas accepter d'utiliser deux fois le même arc. Activer l'arc (a,b) ne va donc pas empêcher d'emprunter l'arc inverse (b,a) s'il existe.
Cette partie TOTALEMENT HORS PROGRAMME va vous permettre de tracer les graphes que vous voulez assez facilement.
Le but est donc de vous montrer comment cela fonctionne de façon à ce que vous puissiez facilement l'utiliser pour vos propres besoins en allant chercher la documentation qui va bien ou formuler correctement vos prompts.
Vous ne trouverez donc ici que quelques exemples et pas un vrai "cours" sur la façon de tracer des graphes en HTML.
Nous allons utiliser une bibliothèque Javascript nommée mermaid ("sirène") et créer via HTML les graphes que nous voulons.
Notez que mermaid possède de nombreuses intégrations automatiques sur beaucoup de plateformes collaboratives, sur beaucoup d'éditeurs de scripts, ect...
L'intégrer dans une page HTML est l'un des moyens de l'utiliser de façon autonome, mais tout le code markdown qui vous allez taper ici sera le même d'une plateforme à l'autre.
13° Utiliser un éditeur de texte pour créer cette page HTML. Vous noterez qu'elle télécharge directement la bibliothèque depuis le serveuer jsdelivr.net. Ce n'est donc pas la manière la plus RGPD-compatible qui soit pour vos utilisateurs.
Vous pouvez constatez sur les deux exemples fournis qu'on définit par l'ensemble des sommets puis qu'on donne l'ensemble des arêtes.
<!DOCTYPE html><html><head><metacharset="utf-8"/><title>Les graphes avec mermaid</title><scriptsrc="https://cdn.jsdelivr.net/npm/mermaid/dist/mermaid.min.js"></script></head><body><section><h1>Mes graphes à moi que j'ai</h1><p>Premier graphe LR pour Left-Right:</p><divclass="mermaid">
flowchart LR
sa["A"]
sb["B"]
sc["C"]
sd["D"]
sa o--o sb
sa o--o sc
sb o--o sc
sc o--o sd
</div><p>Deuxième graphe TB pour Top-Bottom:</p><divclass="mermaid">
flowchart TB
sa["A"]
sb["B"]
sc["C"]
sd["D"]
sa o--o sb
sa o--o sc
sb o--o sc
sc o--o sd
</div></section></body></html>
Pour voir le résultat, il vous suffit de lancer directement votre fichier HTML pour que votre navigateur l'interpréte et vous permette de le visualiser.
14° La forme des sommets et des arêtes est liée à la façon dont vous les fournissez.
Ce programme vous montre différentes représentations des sommets et des arêtes.
<!DOCTYPE html><html><head><metacharset="utf-8"/><title>Les graphes avec mermaid</title><scriptsrc="https://cdn.jsdelivr.net/npm/mermaid/dist/mermaid.min.js"></script></head><body><section><h1>Mes graphes à moi que j'ai</h1><p>Troisième graphe </p><divclass="mermaid">
flowchart TB
sa[("A")]
sb[["B"]]
sc(("C"))
sd("D")
sa o--o sb
sa x--x sc
sb x--x sc
sc <--> sd
</div></section></body></html>
Pour voir le résultat :
Au début de mermaid, on pouvait demander à avoir de belles arêtes sans motif, juste des traits. Depuis quelques années maintenant, ce n'est plus possible pour le moment.
15° Tentons de représenter le graphe non orienté que nous avons utilisé de nombreuses fois :
Voici le programme HTML qui nous serions tentés de taper :
<!DOCTYPE html><html><head><metacharset="utf-8"/><title>Les graphes avec mermaid</title><scriptsrc="https://cdn.jsdelivr.net/npm/mermaid/dist/mermaid.min.js"></script></head><body><section><h1>Mes graphes à moi que j'ai</h1><p>Quatrième graphe </p><divclass="mermaid">
flowchart LR
sa(("A"))
sb(("B"))
sc(("C"))
sd(("D"))
se(("E"))
sf(("F"))
sa x--x sb
sa x--x sc
sb x--x sc
sa x--x sd
sd x--x se
sd x--x sf
</div></section></body></html>
Le graphe est bien le même que celui que j'ai représenté avec LaTex mais, malheureusement, c'est le code interne de mermaid qui décide où placer les sommets :
Le visuel est donc différent mais c'est le même graphe.
16° Ne pas pouvoir placer nous-même les noeuds est donc à la fois un avantage (pas besoin de les fournir) et un désavantage (si l'apparence ne correspond pas à ce que nous voulions).
Par contre, puisque c'est un module Javascript, on peut utiliser CSS pour modifier les couleurs par exemple.
<!DOCTYPE html><html><head><metacharset="utf-8"/><title>Les graphes avec mermaid</title><scriptsrc="https://cdn.jsdelivr.net/npm/mermaid/dist/mermaid.min.js"></script></head><body><section><h1>Mes graphes à moi que j'ai</h1><p>Avec des sous-graphes</p><divclass="mermaid">
flowchart LR
subgraph g[côté gauche]
sa(("A"))
sb(("B"))
sc(("C"))
sa x--x sb
sb x--x sc
sc x--x sa
end
subgraph d[côté gauche]
sd(("D"))
se(("E"))
sf(("F"))
sd x--x se
sd x--x sf
end
sa x--x sd
style g fill:#9999ff,stroke:#444444,stroke-width:2px
style sc fill:#ff9999,stroke:#000000,stroke-width:6px
</div></section></body></html>
17° Par contre, on peut assez facilement demander de tracer des graphes orientés, surtout si leurs formes se rapprochent d'un arbre ou d'une liste.
Notez bien qu'on doit néanmoins représenter les arbres vides. J'utilise par contre CSS pour que les arbres vides ne s'"affichent" pas.
Notez également l'utilisation de & pour indiquer que les deux liaisons sont à réaliser avec le même niveau d'importance.
<!DOCTYPE html><html><head><metacharset="utf-8"/><title>Les graphes avec mermaid</title><scriptsrc="https://cdn.jsdelivr.net/npm/mermaid/dist/mermaid.min.js"></script></head><body><section><h1>Arbre</h1><p>Pour dessiner un arbre binaire :</p><divclass="mermaid">
flowchart TB
a((A))
b((B))
c((C))
d((D))
e((E))
f((F))
g(("∅"))
a --> b & c
b --> d & e
c --> f & g
style g fill:#FFFFFF,stroke:#FFFFFF,stroke-width:1px,color:#FFFFFF
</div></section></body></html>
CONCLUSION
Pour finir, signalons que même si cette activité tente de fixer le vocabulaire de façon claire, le vocabulaire n'est pas vraiment homogène sur les graphes. Et c'est encore pire lorsqu'on regarde comment les anglosaxons gèrent cela.
Voici donc une dernière représentation qui regroupe les notions similaires et vous permettra de voir qu'à part ARC et ARETE, la plupart des termes sont interchangeables.
flowchart LR
subgraph one[Graphe non orienté]
asno[Sommet]
ano[Arête]
cno[Chaîne]
cyno[Cycle]
end
subgraph three[Mot courant]
data[Sommet]
lien[Arête]
cheminement[Chemin]
cycle[Cycle]
end
subgraph two[Graphe orienté]
aso[Sommet]
ao[Arc]
co[Chemin]
cyo[Circuit]
end
asno x--x data x--x aso
ano x--x lien x--x ao
cno x--x cheminement x--x co
cyno x--x cycle x--x cyo
