Polyarbre

Un polyarbre.

En mathématiques, et notamment en théorie des graphes, un polyarbre[1] (aussi appelé arbre dirigé[2], arbre orienté[3],[4] ou singly connected network[5]) 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[6].

Structures voisines

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 dimension d'ordre (en) 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[7]

Un fence (en) 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[8].

Dénombrement

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 suite A000238 de l'OEIS)

Conjecture de Sumner

Un tournois à 6 sommets contenant un exemplaire de tout polyarbre à 4 sommets.

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[9].

Applications

Les polyarbres ont été utilisés comme modèle graphique en raisonnement probabiliste[1]. Si un réseau bayésien a une structure de polyarbre, la propagation des convictions peut être utilisée pour effectuer une inférence efficacement [5],[6].

L'arbre de contour (en) (aussi appel le graphe de Reeb) d'une fonction à valeur réelles sur une espace vectoriel est un polyarbre qui décrit les lignes de niveau de la fonction. Les nœuds de l'arbre de contour sont les lignes de niveau qui passent par un point critique de la fonction, et les arcs décrivent des ensembles contigus d'ensembles de niveaux sans point critique. L'orientation d'un arc est déterminée par la comparaison des valeurs des fonctions sur les deux ensembles de niveaux correspondants[10].

Notes et références

Notes

  1. ↑ a et b Dasgupta 1999.
  2. ↑ Deo 1974, p. 206.
  3. ↑ Harary et Sumner (1980).
  4. ↑ Simion 1991.
  5. ↑ a et b Kim et Pearl 1983.
  6. ↑ a et b Rebane et Pearl 1987.
  7. ↑ Trotter et Moore (1977).
  8. ↑ Frank Ruskey, « Transposition generation of alternating permutations », Order, vol. 6, no 3,‎ , p. 227–233 (DOI 10.1007/BF00563523, MR 1048093)
  9. ↑ Kühn, Mycroft et Osthus (2011).
  10. ↑ Carr, Snoeyink et Axen (2000).

Références

  • Hamish Carr, Jack Snoeyink et Ulrike Axen, « Computing contour trees in all dimensions », Proc. 11th ACM-SIAM Symposium on Discrete Algorithms (SODA 2000),‎ , p. 918–926 (lire en ligne)
  • Sanjoy Dasgupta, « Learning polytrees », Proc. 15th Conference on Uncertainty in Artificial Intelligence (UAI 1999), Stockholm, Sweden, July-August 1999,‎ , p. 134–141 (lire en ligne).
  • Narsingh Deo, Graph Theory with Applications to Engineering and Computer Science, Englewood, New Jersey, Prentice-Hall, (ISBN 0-13-363473-6, lire en ligne).
  • Frank Harary et David Sumner, « The dichromatic number of an oriented tree », Journal of Combinatorics, Information & System Sciences, vol. 5, no 3,‎ , p. 184–187 (MR 603363).
  • Jin H. Kim et Judea Pearl, « A computational model for causal and diagnostic reasoning in inference engines », Proc. 8th International Joint Conference on Artificial Intelligence (IJCAI 1983), Karlsruhe, Germany, August 1983,‎ , p. 190–193 (lire en ligne).
  • Daniela Kühn, Richard Mycroft et Deryk Osthus, « A proof of Sumner's universal tournament conjecture for large tournaments », Proceedings of the London Mathematical Society (Third Series), vol. 102, no 4,‎ , p. 731–766 (DOI 10.1112/plms/pdq035, MR 2793448, arXiv 1010.4430).
  • George Rebane et Judea Pearl, « The recovery of causal poly-trees from statistical data », Proc. 3rd Annual Conference on Uncertainty in Artificial Intelligence (UAI 1987), Seattle, WA, USA, July 1987,‎ , p. 222–228
  • Rodica Simion, « Trees with 1-factors and oriented trees », Discrete Mathematics, vol. 88, no 1,‎ , p. 93–104 (DOI 10.1016/0012-365X(91)90061-6, MR 1099270).
  • William T., Jr. Trotter et John I., Jr. Moore, « The dimension of planar posets », Journal of Combinatorial Theory, Series B, vol. 22, no 1,‎ , p. 54–67 (DOI 10.1016/0095-8956(77)90048-X).

Article lié