ArithmétiqueNotion · Glossaire
Multigraphe
Un multigraphe est un graphe dans lequel plusieurs arêtes peuvent relier le même couple de sommets. Contrairement à un graphe simple où deux sommets distincts sont reliés par au plus une arête, le multigraphe autorise la présence d'arêtes multiples (ou arêtes parallèles). On peut également autoriser des boucles, c'est-à-dire des arêtes reliant un sommet à lui-même. Les multigraphes apparaissent naturellement dans la modélisation de réseaux où plusieurs connexions distinctes peuvent exister entre deux nœuds.
Sommaire
Ce que vous allez apprendre
- Reconnaître des arêtes parallèles entre un même couple de sommets.
- Comprendre pourquoi la convention sur les boucles doit être annoncée.
- Vérifier sur un exemple le degré des sommets et le double comptage d'une boucle.
- Distinguer un multigraphe d'un graphe simple et d'un graphe seulement pondéré.
En clair
Imaginez trois gares A, B et C. Deux voies distinctes relient A à B, tandis qu'une seule relie B à C. Un dessin qui conserve séparément les deux voies entre A et B ne peut pas être un graphe simple : c'est un multigraphe.
Les gares sont les sommets et les voies sont les arêtes. Les deux voies A–B sont dites parallèles. Une voie qui partirait de C pour revenir à C formerait une boucle, si la convention choisie autorise les boucles.
Définition
Un multigraphe non orienté est formé de sommets et d'arêtes, avec la possibilité d'associer plusieurs arêtes distinctes au même couple de sommets. Ces arêtes multiples sont aussi appelées arêtes parallèles. Elles ont les mêmes extrémités, mais restent des objets différents : on peut donc les nommer séparément, par exemple e1 et e2.
La convention sur les boucles doit être annoncée. Dans la convention retenue ici, une arête peut avoir deux fois le même sommet pour extrémité ; elle forme alors une boucle. D'autres ouvrages réservent le mot « multigraphe » aux arêtes parallèles sans boucle et emploient un autre terme lorsque les boucles sont admises.
Un graphe simple impose au contraire au plus une arête entre deux sommets distincts et exclut les boucles. Le multigraphe est donc adapté à un réseau dans lequel plusieurs connexions distinctes entre les mêmes nœuds doivent rester visibles.
Un exemple, pas à pas
Considérons les sommets A, B et C. Les arêtes e1 et e2 relient toutes deux A à B ; l'arête e3 relie B à C ; la boucle ℓ relie C à lui-même. La figure conserve les quatre arêtes comme quatre objets distincts.
1. Entre A et B, on compte deux arêtes : e1 et e2. Elles sont parallèles.
2. Entre B et C, on compte une seule arête, e3.
3. La boucle ℓ a deux fois C pour extrémité. Avec la convention usuelle du degré dans un multigraphe non orienté, elle contribue donc pour deux au degré de C.
On obtient ainsi les degrés 2 pour A, 3 pour B et 3 pour C. Le contrôle consiste à additionner ces degrés : 2 + 3 + 3 = 8, soit deux fois les quatre arêtes du multigraphe.
En pratique
Dans un réseau de transport, deux villes restent deux sommets même si plusieurs liaisons distinctes les relient. Un multigraphe conserve chaque liaison ; un graphe simple convient seulement si seule l'existence d'au moins une liaison importe.
Dans un réseau de communication, plusieurs canaux entre deux équipements peuvent être représentés par des arêtes parallèles. Le choix du multigraphe est pertinent lorsque le nombre ou l'identité des canaux doit rester accessible.
Avant de tracer le réseau, il faut décider si une connexion d'un nœud vers lui-même a un sens dans le modèle. Cette décision fixe si les boucles sont admises et évite une ambiguïté lors de la lecture.
À ne pas confondre
Graphe simple. Entre deux sommets distincts, un graphe simple contient au plus une arête et il ne contient aucune boucle. Deux liaisons distinctes entre A et B suffisent donc à exclure ce modèle, mais pas un multigraphe.
Graphe pondéré. Une valeur portée par une arête ne crée pas plusieurs arêtes. Une seule arête A–B de poids 2 reste une arête, tandis que deux arêtes A–B distinctes forment une paire d'arêtes parallèles, même sans poids.
Limites et pièges
Convention sur les boucles. Le mot « multigraphe » ne garantit pas à lui seul que les boucles sont permises. Il faut lire ou annoncer la convention, puis vérifier si une arête peut avoir deux fois le même sommet pour extrémité.
Arêtes superposées. Deux traits ayant les mêmes extrémités peuvent se masquer dans un dessin. Il faut les décaler ou les étiqueter séparément ; sinon, le tracé donne à tort l'apparence d'une seule arête.
Comptage d'une boucle. Dans un multigraphe non orienté, une boucle touche deux fois son sommet et compte pour deux dans son degré. Dans l'exemple, oublier ce double comptage donnerait 2 au lieu de 3 pour le degré de C et ferait échouer le contrôle des degrés.
Pour aller plus loin
Graphe simple — Pour comparer précisément les restrictions qui interdisent arêtes parallèles et boucles.
arête d'un graphe — Pour approfondir le rôle des extrémités et la représentation d'une connexion.
degré d'un sommet d'un graphe — Pour maîtriser le comptage des arêtes incidentes, notamment celui des boucles.
Boucle — Pour examiner le cas particulier d'une arête dont les deux extrémités coïncident.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres