ArithmétiqueObjet mathématique · Glossaire
arête d'un graphe
Dans la théorie des graphes, une arête est un lien reliant deux sommets dans un graphe non orienté. Contrairement aux arcs des graphes orientés (digraphes), une arête n'a pas de direction : elle relie deux sommets de manière symétrique. Un graphe non orienté est ainsi entièrement défini par son ensemble de sommets et son ensemble d'arêtes.
Sommaire
Ce que vous allez apprendre
- Définir une arête comme une paire non ordonnée de sommets dans un graphe simple non orienté.
- Lire quatre arêtes et contrôler les degrés de leurs extrémités.
- Distinguer une arête d'un arc orienté et d'un chemin.
- Reconnaître les conventions relatives aux boucles et aux arêtes parallèles.
En clair
Imaginez quatre points nommés A, B, C et D. Chaque trait qui joint deux points indique que ces deux points sont directement reliés. Ce trait est une arête.
Une arête se parcourt indifféremment dans les deux sens : relier A à B revient à relier B à A. Elle ne décrit donc ni départ ni arrivée. Pour savoir quelles relations composent le graphe, il suffit de relever les paires de sommets jointes par un trait.
Définition
Un graphe non orienté comporte un ensemble de sommets et un ensemble d'arêtes. Dans un graphe simple, une arête est une paire non ordonnée de deux sommets distincts. L'arête reliant les sommets A et B se note {A, B}. Comme l'ordre ne compte pas, {A, B} et {B, A} désignent la même arête. Deux sommets reliés par une arête sont dits adjacents.
Le dessin ne définit pas à lui seul une arête : sa longueur, sa courbure et la position des sommets sur la page peuvent changer sans modifier le graphe. Seule compte l'incidence, c'est-à-dire le fait que l'arête ait tels sommets pour extrémités.
Selon la convention adoptée, un graphe plus général peut autoriser une boucle, dont les deux extrémités coïncident, ou plusieurs arêtes parallèles entre les mêmes sommets. Il faut alors préciser ce cadre, car la représentation d'une arête par une simple paire de sommets ne distingue pas les arêtes parallèles.
De quoi c'est fait
Une arête possède deux extrémités, qui sont des sommets du graphe. Elle appartient à l'ensemble des arêtes, tandis que ses extrémités appartiennent à l'ensemble des sommets. La relation d'incidence associe l'arête à ses extrémités ; la relation d'adjacence relie alors ces deux sommets entre eux.
Dans le graphe à quatre sommets A, B, C et D, les arêtes sont {A, B}, {A, C}, {B, C} et {C, D}. Cette liste suffit à reconstruire les connexions et à compter le degré de chaque sommet. Le schéma associé rend visibles ces quatre liens sans leur attribuer de direction. La position, la couleur ou la forme des traits n'ajoute aucune arête.
Un exemple, pas à pas
On considère les sommets A, B, C et D et les quatre arêtes {A, B}, {A, C}, {B, C} et {C, D}. Le but est de vérifier les connexions et de compter les arêtes incidentes à chaque sommet.
1. A est extrémité de {A, B} et {A, C} : son degré vaut 2.
2. B est extrémité de {A, B} et {B, C} : son degré vaut 2.
3. C est extrémité de {A, C}, {B, C} et {C, D} : son degré vaut 3.
4. D est extrémité de {C, D} : son degré vaut 1.
2. B est extrémité de {A, B} et {B, C} : son degré vaut 2.
3. C est extrémité de {A, C}, {B, C} et {C, D} : son degré vaut 3.
4. D est extrémité de {C, D} : son degré vaut 1.
Le graphe possède donc 4 arêtes et les degrés sont 2, 2, 3 et 1. Un contrôle consiste à additionner ces degrés : 2 + 2 + 3 + 1 = 8. Chaque arête ayant été comptée une fois à chacune de ses deux extrémités, ce total est bien le double de 4.
En pratique
Pour modéliser une relation réciproque, on place une arête entre deux sommets dès que la relation vaut dans les deux sens. Si le sens modifie la relation, il faut préférer des arcs orientés.
Pour connaître les voisins immédiats d'un sommet, on relève toutes les arêtes qui y aboutissent. Leur nombre donne son degré. Une liste d'arêtes est plus fiable qu'un dessin chargé lorsque des traits se croisent.
Pour chercher une chaîne de connexions, on passe d'un sommet à un sommet adjacent en suivant des arêtes successives. Une seule arête suffit uniquement lorsque les deux sommets sont directement adjacents.
À ne pas confondre
Une arête et un arc. Une arête n'a pas de sens de parcours, alors qu'un arc possède une origine et une destination. Entre A et B, une arête représente une relation symétrique ; l'arc allant de A vers B ne donne pas automatiquement un arc de B vers A.
Une arête et un chemin. Une arête relie directement deux sommets. Un chemin peut enchaîner plusieurs arêtes et traverser des sommets intermédiaires. Dans l'exemple, {A, B} est une arête, tandis que la succession A–C–D forme un chemin de deux arêtes.
Limites et pièges
Croisement trompeur. Deux traits qui se croisent sur un dessin ne créent pas un sommet. Il faut chercher un sommet explicitement placé au croisement ou consulter la liste des arêtes.
Boucle. Certains graphes autorisent une arête dont les deux extrémités sont le même sommet. Cette boucle contribue deux fois au degré de ce sommet, car elle y possède deux extrémités. Dans un graphe simple, elle est interdite.
Arêtes parallèles. Un multigraphe peut comporter au moins deux arêtes distinctes avec les mêmes extrémités. La notation par la seule paire {A, B} devient alors insuffisante : chaque arête doit recevoir une identité propre.
Pour aller plus loin
Le degré d'un sommet d'un graphe prolonge naturellement l'étude : il compte les arêtes incidentes et permet de comparer la place des sommets dans une structure.
L'article Balades dans le graphe divisoriel montre comment des arêtes organisent des parcours dans un graphe construit à partir d'une relation arithmétique.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres