Arbre SPQR
De Wikipedia, l'encyclopédie encyclopedia
Ne doit pas être confondu avec SPQR ou Senatus populusque romanus.
En théorie des graphes, un arbre SPQR est une structure de données arborescente utilisée en informatique, et plus spécifiquement en algorithmique de graphes, pour représenter les composantes triconnexes d'un graphe. L'arbre SPQR d'un graphe peut être construit en temps linéaire[1],[2] ; plusieurs applications dans les algorithmes de graphes dynamiques et dans le tracé de graphes utilisent cette structure de données.
Les structures de base sous-jacentes à unarbre SPQR, sont les composantes triconnexes d'un graphe et la relation entre cette décomposition et les plongements planaires d'un graphe planaire; ces relations ont d'abord été étudiés par Saunders Mac Lane[3] ; ces structures ont été utilisées dans des algorithmes efficaces par plusieurs autres chercheurs[4] avant leur formalisation en termes d'arbre SPQR par Di Battista et Tamassia[5],[6],[7].