Graphe enraciné
From Wikipedia, the free encyclopedia
Cet article ne cite pas suffisamment ses sources ().
Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».
En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?
Cet article est orphelin. Moins de trois articles lui sont liés ().
[[Graphe enraciné]] dans les articles relatifs au sujet.En mathématiques, et en particulier en théorie des graphes, un graphe enraciné est un graphe dans lequel un sommet est désigné comme racine. Les versions orientées et non orientées des graphes enracinés ont été étudiées, et il existe également des variantes autorisant plusieurs racines.
Les graphes enracinés sont également appelés (selon leur application) graphes pointés ou graphes de flux. Dans certains cas, il est nécessaire que l'ensemble du graphe soit accessible depuis le sommet racine.
En théorie topologique des graphes, la notion de graphe enraciné peut être étendue pour considérer plusieurs sommets ou plusieurs arêtes comme racines. On les appelle donc parfois graphes à racines multiples par sommets, pour pouvoir les distinguer des graphes à racines multiples par arêtes. Les graphes comportant plusieurs nœuds distingués comme racines présentent également de l'intérêt en combinatoire, dans le domaine des graphes aléatoires. Ces graphes sont aussi appelés graphes à racines multiples.
Les définitions des termes « graphe orienté enraciné » ou « digraphe enraciné » varient. Généralement, on appelle digraphe enraciné un digraphe dans lequel on a identifié un nœud particulier comme racine. Cependant, en informatique, ces termes renvoient globalement à une notion plus restrictive : un graphe orienté enraciné est un digraphe possédant un nœud distinct r, tel qu'il existe un chemin orienté de r vers n'importe quel nœud autre que r. Les auteurs qui adoptent la définition la plus générale peuvent désigner les graphes répondant à cette définition restrictive comme des digraphes enracinés connexes ou des graphes enracinés accessibles (voir § théorie des ensembles).
L'ouvrage *The Art of Computer Programming* définit les digraphes enracinés de manière un peu plus large : un graphe orienté est dit enraciné s'il possède au moins un nœud qui peut atteindre tous les autres nœuds. Knuth souigne que cette notion est une sorte de compromis entre les notions de digraphe fortement connexe et de digraphe connexe.
Applications
Diagrammes de flux
En informatique, les graphes enracinés dans lesquels le sommet racine peut atteindre tous les autres sommets sont appelés graphes de flux. Parfois, une contrainte supplémentaire est ajoutée, spécifiant qu'un graphe de flux doit avoir un seul sommet de sortie (puits).
Les graphes de flux peuvent être vus comme des abstractions des organigrammes, dont les éléments non structurels (contenu et types des nœuds) ont été supprimés. La sous-classe la plus connue des graphes de flux est sans doute celle des graphes de contrôle, utilisés dans les compilateurs et l'analyse de programmes. Un graphe de flux quelconque peut être converti en graphe de contrôle en contractant chaque arête qui est la seule arête sortante de sa source, et la seule arête entrant dans sa cible. Un autre type de graphe de flux couramment utilisé est le graphe d'appels, dans lequel les nœuds correspondent à des sous-routines entières.
La notion générale de graphe de flux est parfois appelée graphe de programme, mais ce même terme peut également être utilisé pour désigner uniquement les graphes de contrôle. Les graphes de flux sont aussi appelés diagrammes de flux non étiquetés et diagrammes de flux propres. Ces graphes sont parfois utilisés dans les tests logiciels.
Théorie des ensembles
Peter Aczel a utilisé des graphes orientés enracinés, c'est-à-dire des graphes dont chaque nœud est accessible depuis la racine (qu'il appelle graphes pointés accessibles), pour formuler l'axiome d'anti-fondation d'Aczel dans la théorie des ensembles non bien fondés. Dans ce contexte, chaque sommet d'un graphe pointé accessible modélise un ensemble (non bien fondé) au sein de la théorie des ensembles (non bien fondé) d'Aczel, et un arc reliant un sommet v à un sommet w représente l'appartenance de v à w. L'axiome d'anti-fondation d'Aczel stipule donc que tout graphe pointé accessible modélise une famille d'ensembles (non bien fondés).
Tout jeu combinatoire peut être modélisé par un graphe orienté enraciné dont les sommets représentent les positions du jeu, les arêtes les coups possibles et la racine la position initiale. Ce graphe est très utile pour l'étude de la complexité des jeux, où la complexité en espace d'états correspond au nombre de sommets du graphe.
