Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Arbre SPQR
Résumé
vignette|360x360px| Un graphe et son arbre SPQR. Les lignes noires pointillés sont des arêtes virtuelles, représentées en noir; les arêtes restantes sont colorées d'après la composant triconnexe à laquelle elles appartiennent.
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 ; 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 ; ces structures ont été utilisées dans des algorithmes efficaces par plusieurs autres chercheurs avant leur formalisation en termes d'arbre SPQR par Di Battista et Tamassia.
Un arbre SPQR se présente sous la forme d'un arbre non enraciné dans lequel à chaque nœud x est associé un graphe ou multigraphe non orienté G x, une composante du graphe donné. Les nœuds sont reliés par des arêtes « virtuelles » qui relient les graphes associés, eux aussi dotés d'arêtes virtuelles.
Un nœud, et le graphe qui lui est associé, peut être de l'un des quatre types suivants, correspondant aux initiales SPQR:
Dans un nœud de type S, le graphe associé est un graphe cycle avec au moins trois sommets et arêtes. Ce cas est analogue à la composition en série dans les graphes série-parallèle ; la lettre « S » signifie « série ».
Dans un nœud de type P, le graphe associé est un graphe dipolaire, un multigraphe avec deux sommets et au moins trois arêtes ; c'est le dual planaire d'un graphe cyclique. Ce cas est analogue à la composition parallèle dans graphes série-parallèle ; la lettre « P » signifie « parallèle.
Dans un nœud de type Q, le graphe associé a une seule arête réelle.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.