Logique et ensemblesObjet mathématique · Glossaire
Sous-graphe
En théorie des graphes, un sous-graphe d'un graphe G = (V, E) est un graphe G' = (V', E') tel que V' est un sous-ensemble de V et E' est un sous-ensemble de E, avec les extrémités de chaque arête de E' appartenant à V'. Un sous-graphe induit par un sous-ensemble V' de sommets contient toutes les arêtes de G reliant deux sommets de V'. Un graphe partiel est un sous-graphe conservant tous les sommets. La notion de sous-graphe est fondamentale en théorie des graphes, notamment pour les problèmes de sous-graphe isomorphe.
Sommaire
Ce que vous allez apprendre
- Identifier les deux ensembles qui définissent un sous-graphe.
- Distinguer sous-graphe ordinaire, sous-graphe induit et graphe partiel.
- Vérifier ces trois constructions sur un même graphe de cinq sommets.
- Repérer les erreurs d’arête orpheline, d’induction incomplète et de connexité supposée.
En clair
Imaginez un réseau de cinq stations reliées par des voies. On peut n’en garder que quatre, puis choisir certaines voies qui relient encore ces stations. Le réseau obtenu est un sous-graphe du réseau initial.
Deux choix sont donc contrôlés : les sommets conservés et les arêtes conservées. Si toutes les arêtes existantes entre les sommets choisis sont automatiquement gardées, le sous-graphe est induit. Si tous les sommets restent présents, il est partiel.
Définition
Un graphe G est décrit par un ensemble V de sommets et un ensemble E d’arêtes. Un graphe G′, formé d’un ensemble V′ de sommets et d’un ensemble E′ d’arêtes, est un sous-graphe de G lorsque . De plus, les deux extrémités de chaque arête choisie dans E′ doivent appartenir à V′. On ne peut donc pas conserver une arête tout en supprimant l’un de ses sommets.
Le choix des sommets ne détermine pas en général celui des arêtes : on peut omettre certaines arêtes de G entre les sommets conservés. Dans un sous-graphe induit par V′, ce choix disparaît. Pour un graphe simple non orienté, l’ensemble des arêtes est exactement . Toutes les arêtes du graphe initial ayant leurs deux extrémités dans V′ sont présentes.
Un graphe partiel est la variante pour laquelle V′ = V : tous les sommets sont conservés, mais E′ peut ne contenir qu’une partie des arêtes. Enfin, chercher un sous-graphe isomorphe consiste à chercher dans G une structure ayant les mêmes adjacences qu’un graphe donné, indépendamment du nom ou du tracé de ses sommets.
De quoi c'est fait
Quatre données organisent la construction. Le graphe ambiant G fournit les choix possibles. L’ensemble V′ indique les sommets retenus. L’ensemble E′ indique les arêtes retenues. Enfin, l’incidence précise quelles extrémités chaque arête relie.
Le choix de E′ dépend de V′, car chaque arête conservée doit avoir ses extrémités dans V′. Dans un sous-graphe induit, la dépendance est plus forte : V′ impose entièrement E′. Dans un graphe partiel, c’est au contraire l’égalité V′ = V qui est imposée, tandis que les arêtes restent sélectionnables.
La position des points, la longueur des traits, leur couleur et les croisements dessinés ne définissent pas le sous-graphe. Les ensembles de sommets et d’arêtes, avec leurs incidences, suffisent à le construire et à vérifier ses adjacences.
Un exemple, pas à pas
Prenons un graphe non orienté G. Ses sommets sont A, B, C, D et E. Ses arêtes sont AB, AC, BC, BD, CD et DE. On choisit d’abord V′ = {A, B, C, D}.
1. Gardons seulement AB, BC et CD. Le graphe H obtenu est un sous-graphe : ces trois arêtes appartiennent à G et toutes leurs extrémités appartiennent à V′.
2. Construisons maintenant le sous-graphe induit par V′. Il faut reprendre toutes les arêtes de G dont les deux extrémités sont parmi A, B, C et D : AB, AC, BC, BD et CD. L’arête DE est écartée, car E n’est pas dans V′.
3. Pour obtenir un graphe partiel, conservons les cinq sommets et choisissons AB, BC, CD et DE. Le contrôle se refait directement : chaque arête retenue vient de G, ses extrémités sont présentes et l’ensemble des sommets reste V.
Une représentation des quatre graphes permet de contrôler visuellement quels sommets et quelles arêtes ont été conservés dans chaque cas.
En pratique
Pour étudier une zone d’un réseau, on choisit ses sommets. Le sous-graphe induit convient lorsque toutes les liaisons existantes entre eux comptent ; un sous-graphe ordinaire convient si seules certaines liaisons sont pertinentes.
Pour simplifier les connexions sans retirer d’élément du réseau, on cherche un graphe partiel. Le critère observable est que le nombre et l’identité des sommets ne changent pas, tandis que des arêtes peuvent disparaître.
Pour repérer un motif, on cherche un sous-graphe isomorphe au modèle. Cette approche est préférable à la comparaison des dessins lorsque seuls les sommets reliés entre eux importent, et non leur position sur la page.
En coloration, l’examen d’un sous-graphe peut révéler une contrainte locale. Par exemple, trois sommets deux à deux reliés forment un sous-graphe complet et doivent recevoir des couleurs deux à deux distinctes.
À ne pas confondre
Un sous-ensemble de sommets n’est pas encore un sous-graphe. Il fournit seulement V′ ; il faut aussi préciser E′, ou annoncer que le sous-graphe est induit. Dans l’exemple, {A, B, C, D} ne dit pas à lui seul si l’arête AC est conservée.
Un dessin inclus dans un autre dessin ne suffit pas non plus. Le critère porte sur les sommets, les arêtes et leurs extrémités, pas sur la position graphique. Deux représentations très différentes peuvent décrire le même sous-graphe.
Limites et pièges
Arête orpheline. Si une arête retenue touche un sommet supprimé, l’objet proposé n’est pas un sous-graphe. Il faut soit retirer cette arête, soit réintroduire toutes ses extrémités dans V′.
Induit incomplet. Après avoir annoncé un sous-graphe induit, oublier une seule arête de G entre deux sommets de V′ suffit à invalider cette qualification. Dans l’exemple, omettre AC, BD ou toute autre arête interne donne seulement un sous-graphe ordinaire.
Partiel sans tous les sommets. Un graphe ne peut être dit partiel de G que s’il conserve exactement V. Le graphe H de l’exemple n’est donc pas partiel, puisqu’il omet E, même s’il utilise uniquement des arêtes de G.
Connexité supposée. La définition n’exige pas que le sous-graphe soit connexe. Un choix valide peut isoler un sommet ou produire plusieurs composantes ; il faut vérifier la connexité séparément si le problème la demande.
Pour aller plus loin
Graphe complet — Étudier le cas où chaque paire de sommets est reliée et reconnaître ces configurations parmi les sous-graphes.
clique - graphe - — Relier un ensemble de sommets deux à deux adjacents au sous-graphe complet qu’il induit.
coloration d'un graphe — Voir comment les adjacences d’un graphe, et donc celles de ses sous-graphes, contraignent l’attribution des couleurs.
graphe connexe — Vérifier séparément si les sommets d’un sous-graphe restent reliés par des chemins.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres