ArithmétiqueNotion · Glossaire
Point d'articulation
Dans un graphe connexe, un point d'articulation (ou point de coupure) est un sommet dont la suppression déconnecte le graphe, c'est-à-dire augmente le nombre de composantes connexes. Les ponts sont les arêtes jouant un rôle analogue. L'identification des points d'articulation est importante en analyse des réseaux pour trouver les points de vulnérabilité. L'algorithme de Tarjan permet de trouver tous les points d'articulation d'un graphe en temps linéaire.
Sommaire
Ce que vous allez apprendre
- Tester un sommet en comparant le nombre de composantes avant et après sa suppression.
- Vérifier sur un graphe de cinq sommets pourquoi C et D sont les deux points d'articulation.
- Distinguer un point d'articulation d'un pont, d'un sommet de degré élevé et d'un séparateur de plusieurs sommets.
- Interpréter les critères particuliers de l'algorithme de Tarjan pour la racine et les autres sommets.
En clair
Imaginez plusieurs groupes reliés par un unique carrefour. Tant que ce carrefour fonctionne, chacun peut rejoindre les autres. Si on le retire avec toutes ses liaisons, le réseau se sépare en groupes qui ne communiquent plus. Le sommet retiré est alors un point d'articulation.
Un sommet très relié n'est pas forcément critique : ce qui compte est l'absence d'un autre chemin entre les parties du réseau.
Définition
Dans un graphe non orienté, une composante connexe est un groupe maximal de sommets reliés entre eux par des chemins. Pour un graphe G et l'un de ses sommets v, le graphe G − v s'obtient en supprimant v ainsi que toutes les arêtes qui lui sont incidentes. Le sommet v est un point d'articulation, ou point de coupure, lorsque cette suppression augmente le nombre de composantes connexes.
Si c(H) désigne le nombre de composantes connexes d'un graphe H, le critère est . Lorsque G est connexe, c(G) vaut 1 : retirer un point d'articulation produit donc au moins deux composantes. La définition s'applique aussi à un graphe initialement non connexe avec le même critère d'augmentation, mais la formulation « sa suppression déconnecte le graphe » suppose que le graphe était connexe.
Un pont, parfois appelé isthme, joue le rôle analogue pour une arête : c'est la suppression de l'arête qui augmente le nombre de composantes. Pour repérer tous les points d'articulation, l'algorithme de Tarjan parcourt le graphe en profondeur et compare l'ordre de découverte des sommets avec le plus ancien sommet encore atteignable. Son temps d'exécution est linéaire en la somme du nombre de sommets et du nombre d'arêtes.
Un exemple, pas à pas
On considère cinq sommets A, B, C, D et E. Les données sont les arêtes AB, AC, BC, CD et DE. Les trois premières forment le triangle A–B–C ; C relie ce triangle à la chaîne C–D–E.
1. Avant toute suppression, les cinq sommets appartiennent à une seule composante : le graphe est connexe.
2. On retire C et ses trois arêtes AC, BC et CD. Il reste l'arête AB d'un côté et l'arête DE de l'autre. Les composantes sont donc {A, B} et {D, E}. Leur nombre passe de 1 à 2 : C est un point d'articulation.
3. On repart du graphe initial, puis on retire D avec CD et DE. Le triangle {A, B, C} reste connexe, tandis que E devient seul. Le nombre de composantes passe encore de 1 à 2 : D est aussi un point d'articulation.
4. Pour contrôler le résultat, on retire B. L'arête AC maintient le chemin A–C–D–E : il reste une seule composante. B n'est donc pas un point d'articulation.
Le contrôle complet donne exactement deux points d'articulation, C et D.
En pratique
Dans un réseau de communication, on retire virtuellement chaque routeur avec ses connexions. Si les machines restantes se répartissent en plusieurs groupes, ce routeur signale une vulnérabilité. Lorsque la panne étudiée concerne plutôt une liaison, on recherche des ponts.
Dans un réseau de transport modélisé par des stations et des liaisons, un point d'articulation repère une station dont la fermeture coupe toute possibilité de trajet entre certaines zones. Si plusieurs stations doivent fermer ensemble pour provoquer la coupure, il faut rechercher un séparateur de sommets plutôt qu'un point isolé.
Pour renforcer un réseau, on examine les composantes obtenues après retrait du sommet critique. Ajouter une liaison entre deux de ces composantes crée un itinéraire de secours ; le sommet cesse d'être critique si aucun groupe ne reste séparé.
À ne pas confondre
Point d'articulation et pont. Le premier est un sommet ; le second est une arête. Dans le graphe de l'exemple, D est un point d'articulation, tandis que DE est un pont : les suppressions ne portent pas sur le même objet, même si elles séparent toutes deux le graphe.
Point d'articulation et sommet de degré élevé. Le degré compte les arêtes incidentes, mais ne mesure pas à lui seul la vulnérabilité. Dans le triangle A–B–C, le sommet B a deux voisins ; le retirer laisse A relié à C. À l'inverse, D n'a que deux voisins et constitue pourtant un point d'articulation.
Point d'articulation et séparateur de sommets. Un séparateur peut comporter plusieurs sommets dont le retrait simultané coupe le graphe. Un point d'articulation est le cas particulier où un seul sommet suffit.
Limites et pièges
Graphe déjà non connexe. Dire seulement que G − v est non connexe ne suffit pas. Il faut comparer les nombres de composantes avant et après la suppression : v est un point d'articulation uniquement si ce nombre augmente.
Feuille et graphe à deux sommets. Une feuille est un sommet de degré 1. La retirer d'un graphe connexe comportant au moins deux sommets ne sépare pas les sommets restants ; elle n'est donc pas un point d'articulation. Dans le graphe réduit à une seule arête, retirer une extrémité laisse un sommet et toujours une composante.
Racine du parcours de Tarjan. Dans l'arbre de parcours en profondeur, une racine est un point d'articulation si et seulement si elle possède au moins deux enfants. Pour un autre sommet v, il faut qu'un enfant w ne puisse remonter strictement au-dessus de v : . Appliquer le second critère à la racine donne de faux résultats.
Graphe orienté. La connexité peut alors signifier connexité forte ou faible. Le critère non orienté ne doit pas être transposé sans préciser la convention ; pour une coupure forte, il faut tester l'augmentation du nombre de composantes fortement connexes avec une méthode adaptée.
Pour aller plus loin
La fiche graphe connexe précise la propriété de chemin qui permet de compter les composantes avant et après une suppression.
Le prolongement naturel consiste à chercher des ensembles minimaux de sommets ou d'arêtes capables de séparer un réseau. On passe alors d'une vulnérabilité ponctuelle à une mesure de sa redondance.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres