Generalización de gráficos de árboles a hipergrafos
Un hiperárbol (vértices azules y aristas amarillas) y su árbol anfitrión (rojo)
En el campo matemático de la teoría de grafos , un hipergrafo H se denomina hiperárbol si admite un grafo anfitrión T tal que T es un árbol . En otras palabras, H es un hiperárbol si existe un árbol T tal que cada hiperarista de H es el conjunto de vértices de un subárbol conexo de T. [ 1] Los hiperárboles también se han denominado hipergrafos arbóreos [2] o hipergrafos arbóreos . [3]
Cada árbol T es en sí mismo un hiperárbol: T en sí mismo puede utilizarse como grafo anfitrión, y cada arista de T es un subárbol de este grafo anfitrión. Por lo tanto, los hiperárboles pueden considerarse como una generalización de la noción de árbol para hipergrafos . [4] Entre ellos se incluyen los hipergrafos acíclicos de Berge conectados, que también se han utilizado como una generalización (diferente) de árboles para hipergrafos.
Propiedades
Todo hiperárbol tiene la propiedad de Helly (propiedad 2-Helly): si un subconjunto S de sus hiperaristas tiene la propiedad de que cada dos hiperaristas en S tienen una intersección no vacía , entonces S mismo tiene una intersección no vacía (un vértice que pertenece a todas las hiperaristas en S ). [5]
Según los resultados de Duchet, Flament y Slater [6], los hiperárboles pueden caracterizarse de manera equivalente de las siguientes maneras.
Un hipergrafo H es un hiperárbol si y sólo si su hipergrafo dual H * es conforme y el gráfico de 2 secciones de H * es cordal. [7]
Un hipergrafo es un hiperárbol si y sólo si su hipergrafo dual es alfa-acíclico en el sentido de Fagin. [8]
Es posible reconocer hiperárboles (como duales de hipergrafos alfa-acíclicos) en tiempo lineal . [9]
El problema de cobertura exacta (encontrar un conjunto de hiperaristas no superpuestas que cubra todos los vértices) se puede resolver en tiempo polinomial para hiperárboles, pero sigue siendo NP-completo para hipergrafos alfa-acíclicos. [10]
Brandstädt, Andreas ; Le, Van Bang; Spinrad, Jeremy (1999), Clases de grafos: un estudio , Monografías SIAM sobre matemáticas discretas y aplicaciones, ISBN 0-89871-432-X, Sr. 1686154.
Brandstädt, Andreas ; Leitert, Arne; Rautenbach, Dieter (2012), "Conjuntos dominantes y dominantes de aristas eficientes para grafos e hipergrafos", Algorithms and Computation: 23rd International Symposium, ISAAC 2012, Taipei, Taiwán, 19-21 de diciembre de 2012, Actas , Lecture Notes in Computer Science , vol. 7676, págs. 267–277, arXiv : 1207.0953 , doi :10.1007/978-3-642-35261-4_30, ISBN 978-3-642-35260-7, Sr. 3065639.
Fagin, Ronald (1983), "Grados de aciclicidad para hipergrafos y esquemas de bases de datos relacionales", Journal of the ACM , 30 (3): 514–550, doi : 10.1145/2402.322390 , MR 0709831.
McKee, TA; McMorris, FR (1999), Temas de teoría de grafos de intersección , Monografías SIAM sobre matemáticas discretas y aplicaciones, Filadelfia, PA: Sociedad de Matemáticas Industriales y Aplicadas, ISBN 0-89871-430-3, Sr. 1672910.
Tarjan, Robert E. ; Yannakakis, Mihalis (1984), "Algoritmos simples de tiempo lineal para probar la cordalidad de los gráficos, probar la aciclicidad de los hipergráficos y reducir selectivamente los hipergráficos acíclicos" (PDF) , SIAM Journal on Computing , 13 (3): 566–579, doi :10.1137/0213035, MR 0749707.
Voloshin, Vitaly (2002), Coloración de hipergrafos mixtos: teoría, algoritmos y aplicaciones , Fields Institute Monographs, vol. 17, Providence, RI: American Mathematical Society, ISBN 0-8218-2812-6, Sr. 1912135.
