Concept

Polyarbre

En mathématiques, et notamment en théorie des graphes, un polyarbre (aussi appelé arbre dirigé, arbre orienté ou singly connected network) est graphe orienté acyclique dont le graphe non orienté sous-jacent est un arbre (théorie des graphes). En d'autres termes, si on remplace les arcs par des arêtes, on obtient un graphe non orienté qui est à la fois connexe et sans cycle. Une polyforêt (ou forêt dirigée ou forêt orientée) est un graphe orienté dont le graphe non orienté sous-jacent est une forêt. Autrement dit, si on remplace les arcs orientés par des arêtes, on obtient un graphe non orienté qui est sans cycles. La terminologie « polytree » a été introduite en 1987 par George Rebane et Judea Pearl. Toute arborescence est un polyarbre, mais la réciproque est fausse : un polyarbre n'est pas toujours une arborescence. Tout polyarbre est un multiarbre, c'est-à-dire un graphe orienté sans cycle dans lequel, pour tout sommet, le sous-graphe accessible depuis un sommet est un arbre. La relation d'accessibilité entre les sommets d'un polyarbre est un ordre partiel qui a une au plus trois. Si la dimension d'ordre est égale à 3, il existe un sous-ensemble de 7 éléments tels que pour chaque , on a ou ; ces six inégalités définissent une structure de polyarbre sur les sept éléments Un ou ensemble zigzag est un cas particulier d'un polyarbre où le graphe sous-jacent est une chaîne et les arcs le long de la chaine ont des orientations alternantes. L'ordre d’accessibilité dans un polyarbre a aussi été appelé generalized fence. Le nombre de polyarbre distincts à n sommets non étiquetés est, pour n = 1, 2, 3, ..., , la donné par la suite : 1, 1, 3, 8, 27, 91, 350, 1376, 5743, 24635, 108968, 492180, ... (c'est la ) La conjecture de Sumner, nommée ainsi d'après David Sumner, affirme que les tournois sont des graphes universels pour les polyarbres, en ce sens que tout tournoi avec sommet contient tout polyarbre avec n sommets comme sous-graphe. Cette conjecture, même si elle est encore ouverte dans le cas général, a été démontré pour toutes les valeurs suffisamment grandes de n.

À 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.

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.