Hyperarbre - Hypertree
En mathématiques, un hypergraphe H est appelé hyperarbre s'il admet un graphe hôte T tel que T soit un arbre . En d'autres termes, H est un hyperarbre s'il existe un arbre T tel que chaque hyperarête de H est l'ensemble des sommets d'un sous-arbre connexe de T . Les hyperarbres ont également été appelés hypergraphes arboricoles ou hypergraphes arborescents .
Chaque arbre T est lui-même un hyperarbre : T lui-même peut être utilisé comme graphe hôte, et chaque arête de T est un sous - arbre de ce graphe hôte. Par conséquent, les hyperarbres peuvent être considérés comme une généralisation de la notion d'arbre pour les hypergraphes . Ils comprennent les hypergraphes Berge-acycliques connectés, qui ont également été utilisés comme une généralisation (différente) des arbres pour les hypergraphes.
Propriétés
Chaque hyperarbre a la propriété Helly ( propriété 2-Helly) : si un sous-ensemble S de ses hyperarêtes a la propriété que tous les deux hyperarêtes de S ont une intersection non vide, alors S lui-même a une intersection non vide (un sommet qui appartient à tous les hyperarêtes de S ).
Par les résultats de Duchet, Flament et Slater, les hyperarbres peuvent être caractérisés de manière équivalente des manières suivantes.
- Un hypergraphe H est un hyperarbre si et seulement s'il possède la propriété Helly et que son graphe linéaire est un graphe à cordes .
- Un hypergraphe H est un hyperarbre si et seulement si son hypergraphe dual H * est conforme et que le graphe à 2 sections de H * est cordal .
- Un hypergraphe est un hyperarbre si et seulement si son hypergraphe dual est alpha-acyclique au sens de Fagin.
Il est possible de reconnaître des hyperarbres (comme des duels d'hypergraphes alpha-acycliques) en temps linéaire . Le problème de couverture exacte (trouver un ensemble d'hyperarêtes non chevauchantes qui couvre tous les sommets) est résoluble en temps polynomial pour les hyperarbres mais reste NP-complet pour les hypergraphes alpha-acycliques.
Voir également
- Graphe à double corde , un graphe dont les cliques maximales forment un hyperarbre
Remarques
Les références
- Berge, Claude (1989), Hypergraphs: Combinatorics of Finite Sets , North-Holland Mathematical Library, 45 , Amsterdam: North Holland, ISBN 0-444-87489-5, MR 1013569.
- Brandstädt, Andreas ; Dragan, Féodor ; Chepoi, Victor; Volochine, Vitaly (1998), "Dual chordal graphs" (PDF) , SIAM Journal on Discrete Mathematics , 11 : 437–455, doi : 10.1137/s0895480193253415 , MR 1628114.
- Brandstädt, Andreas ; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey , SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X, MR 1686154.
- Brandstädt, Andreas ; Leitert, Arne ; Rautenbach, Dieter (2012), "Ensembles dominants efficaces et dominants pour les graphiques et les hypergraphes", Algorithmes et calcul : 23e Symposium international, ISAAC 2012, Taipei, Taiwan, 19-21 décembre 2012, Actes , Notes de cours en informatique , 7676 , pp. 267-277, arXiv : 1207.0953 , doi : 10.1007/978-3-642-35261-4_30 , MR 3065639.
- Fagin, Ronald (1983), "Degrés d'acyclicité pour les hypergraphes et les schémas de bases de données relationnelles", Journal of the ACM , 30 : 514-550, doi : 10.1145/2402.322390 , MR 0709831.
- McKee, TA; McMorris, FR (1999), Topics in Intersection Graph Theory , SIAM Monographs on Discrete Mathematics and Applications, Philadelphie, PA: Society for Industrial and Applied Mathematics, ISBN 0-89871-430-3, MR 1672910.
- Tarjan, Robert E. ; Yannakakis, Mihalis (1984), « Algorithmes simples en temps linéaire pour tester la chordalité des graphes, tester l'acyclicité des hypergraphes et réduire sélectivement les hypergraphes acycliques » (PDF) , SIAM Journal on Computing , 13 (3) : 566-579, doi : 10.1137/0213035 , MR 0749707.
- Volochine, Vitaly (2002), Coloration des hypergraphes mixtes : théorie, algorithmes et applications , monographies du Fields Institute, 17 , Providence, RI : American Mathematical Society, ISBN 0-8218-2812-6, MR 1912135.