ArithmétiqueObjet mathématique · Glossaire
Graphe simple
Un graphe simple est un graphe sans boucles (arêtes reliant un sommet à lui-même) et sans arêtes multiples (plusieurs arêtes entre une même paire de sommets). C'est la forme la plus courante de graphe en théorie des graphes combinatoire. Un graphe simple sur n sommets peut avoir au maximum n*(n-1)/2 arêtes. Par opposition, un multigraphe autorise plusieurs arêtes entre deux sommets, et un pseudographe autorise aussi les boucles.
Sommaire
Ce que vous allez apprendre
- Reconnaître un graphe simple par l'absence de boucles et d'arêtes multiples.
- Calculer le nombre maximal d'arêtes pour n sommets.
- Distinguer graphe simple, multigraphe et pseudographe.
- Vérifier un exemple à quatre sommets en énumérant ses paires.
En clair
Imaginez quatre points nommés A, B, C et D, puis des traits qui relient certains points. Dans un graphe simple, aucun trait ne repart vers le point dont il est issu. Entre deux points donnés, il ne peut pas non plus y avoir deux traits distincts.
Les points sont les sommets et les traits sont les arêtes. Le mot « simple » décrit donc deux interdictions faciles à vérifier : aucune boucle sur un sommet et aucune répétition entre une même paire de sommets.
Définition
Dans le cadre non orienté considéré ici, un graphe simple est formé d'un ensemble de sommets et d'un ensemble d'arêtes. Chaque arête relie deux sommets distincts et une même paire de sommets détermine au plus une arête. La première condition exclut les boucles, dont les deux extrémités seraient le même sommet. La seconde exclut les arêtes multiples entre une même paire.
Si le nombre de sommets est noté n, chaque arête possible correspond à une paire de sommets distincts. Le nombre maximal d'arêtes est donc :
Cette borne est atteinte lorsque toutes les paires de sommets sont reliées. Avec quatre sommets, il existe ainsi au plus six arêtes. Si plusieurs arêtes doivent relier deux sommets, l'objet est un multigraphe. Si des boucles sont également admises, la source emploie le terme pseudographe.
De quoi c'est fait
Un graphe simple réunit d'abord des sommets, qui sont les objets représentés, et des arêtes, qui indiquent quelles paires de sommets sont reliées. Chaque arête possède deux extrémités distinctes prises parmi les sommets. Une paire donnée ne peut apparaître qu'une fois dans l'ensemble des arêtes.
Les sommets disponibles déterminent donc les arêtes possibles, tandis que les arêtes déterminent les voisinages entre sommets. Ensemble, ces deux données suffisent à reconstruire le graphe et à compter ses arêtes. La position des points, la longueur des traits, leur couleur et les croisements éventuels appartiennent seulement au dessin : ils ne changent pas le graphe tant que les mêmes paires de sommets restent reliées.
Un exemple, pas à pas
Données. Les quatre sommets sont A, B, C et D. Les quatre arêtes relient les paires A–B, A–C, B–C et C–D. La figure matérialise exactement ces quatre relations.
1. On inspecte les extrémités : chaque arête relie deux sommets différents. Il n'y a donc aucune boucle.
2. On compare les quatre paires A–B, A–C, B–C et C–D. Aucune paire n'est répétée, donc il n'y a pas d'arête multiple.
3. Le graphe respecte les deux conditions : il est simple.
4. Pour quatre sommets, la borne vaut 4 × 3 ÷ 2 = 6 arêtes. Les quatre arêtes présentes ne la dépassent pas.
Le contrôle est refaisable en énumérant les six paires possibles : A–B, A–C, A–D, B–C, B–D et C–D. Quatre sont des arêtes ; A–D et B–D ne le sont pas.
En pratique
Pour vérifier un dessin de graphe, on examine d'abord chaque trait : ses extrémités doivent être deux sommets différents. On compare ensuite les paires reliées afin de repérer une éventuelle répétition.
Lorsque deux liens distincts entre les mêmes sommets doivent être conservés, le graphe simple ne convient plus. Le multigraphe est l'alternative indiquée par cette répétition observable.
Lorsqu'un lien d'un sommet vers lui-même doit être représenté, la boucle exclut également le graphe simple. Le pseudographe est alors l'alternative qui autorise cette boucle.
À ne pas confondre
Multigraphe. Il autorise plusieurs arêtes entre deux mêmes sommets, contrairement au graphe simple. Deux arêtes reliant toutes deux A à B suffisent à trancher : l'objet est un multigraphe, pas un graphe simple.
Pseudographe. Il autorise aussi les boucles. Dès qu'une arête relie A à lui-même, le graphe n'est pas simple ; dans le vocabulaire de la source, il relève du pseudographe.
Limites et pièges
Très petits graphes. Pour un sommet, la borne n(n − 1) ÷ 2 vaut zéro : aucune arête n'est possible. Pour deux sommets, elle vaut une. Si la convention adoptée autorise le graphe à zéro sommet, sa borne vaut également zéro.
Borne et existence. Avoir moins de n(n − 1) ÷ 2 arêtes ne suffit pas à rendre un graphe simple. Une boucle ou une paire répétée viole encore la définition ; il faut contrôler la nature des arêtes, pas seulement leur nombre.
Dessin trompeur. Un croisement de traits qui n'est pas déclaré comme sommet ne crée ni sommet ni arête supplémentaire. Le bon contrôle consiste à relever les extrémités nommées de chaque arête.
Cadre non orienté. La borne n(n − 1) ÷ 2 compte des paires sans ordre. Elle ne doit pas être appliquée telle quelle à un graphe orienté, où le sens des liens fait partie des données.
Pour aller plus loin
Le Multigraphe prolonge la comparaison en détaillant le cadre où plusieurs arêtes peuvent relier une même paire de sommets.
Le Graphe complet étudie le cas où toutes les paires de sommets sont reliées et où la borne maximale est atteinte.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres