En matemáticas, un hipergrama H se llama hipertárbol si admite un gráfico anfitrión T tal que T es un árbol . En otras palabras, H es un Hypertree si existe un árbol T de tal manera que cada hyperedge de H es el conjunto de vértices de un subárbol conectado de T . [1] A los hipertárboles también se les ha llamado hipergráficos arbóreos [2] o hipergráficos de árboles . [3]
Cada árbol T es en sí mismo un hiperárbol: T en sí mismo puede usarse como el gráfico de host, y cada borde de T es un subárbol de este gráfico de host. Por lo tanto, los hipertárboles pueden verse como una generalización de la noción de árbol para los hipergráficos . [4] Incluyen los hipergráficos acíclicos de Berge conectados, que también se han utilizado como una generalización (diferente) de árboles para hipergráficos.
Propiedades
Todo hiperárbol tiene la propiedad de Helly ( propiedad 2-Helly): si un subconjunto S de sus hiperrrboles tiene la propiedad de que cada dos hiperrrboles en S tienen una intersección no vacía, entonces S tiene una intersección no vacía (un vértice que pertenece a todos los hiperrboles en S ). [5]
Según los resultados de Duchet, Flament y Slater [6], los hipertárboles pueden caracterizarse de forma equivalente de las siguientes formas.
- Un hipergráfico H es un hiperárbol si y solo si tiene la propiedad de Helly y su gráfico lineal es un gráfico cordal .
- Un hipergrafo H es un hipergrafo si y solo si su hipergrafo dual H * es conforme y el grafo de 2 secciones de H * es cordal . [7]
- Un hipergrafo es un hipergrafo si y solo si su hipergrafo dual es alfa-aciclico en el sentido de Fagin. [8]
Es posible reconocer hipertárboles (como duales de hipergráficos alfa-acíclicos) en tiempo lineal . [9] El problema de la cobertura exacta (encontrar un conjunto de hipergrafias no superpuestas que cubra todos los vértices) se puede resolver en tiempo polinomial para los hipertrós, pero sigue siendo NP-completo para los hipergráficos alfa-acíclicos. [10]
Ver también
- Gráfico doblemente cordal , un gráfico cuyas camarillas máximas forman un árbol
Notas
- ^ Brandstädt y col. (1998)
- ^ Berge (1989)
- ^ McKee y McMorris (1999)
- ^ Berge (1989) ; Voloshin (2002)
- ^ Berge (1989) ; Voloshin (2002)
- ^ Ver, por ejemplo, Brandstädt, Le & Spinrad (1999) ; McKee y McMorris (1999)
- ^ Berge (1989)
- ^ Fagin (1983)
- ^ Tarjan y Yannakakis (1984) .
- ^ Brandstädt, Leitert y Rautenbach (2012)
Referencias
- Berge, Claude (1989), Hypergraphs: Combinatoria de conjuntos finitos , Biblioteca matemática de Holanda Septentrional, 45 , Amsterdam: Holanda Septentrional, ISBN 0-444-87489-5, MR 1013569.
- Brandstädt, Andreas ; Dragan, Feodor; Chepoi, Victor; Voloshin, Vitaly (1998), "Gráficos doblemente cordales" (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), "Conjuntos eficientes dominantes y dominantes de bordes para gráficos e hipergráficos", Algoritmos y computación: 23er Simposio Internacional, ISAAC 2012, Taipei, Taiwán, 19-21 de diciembre de 2012, Actas , Notas de conferencias en Ciencias de la Computación , 7676 , págs. 267–277, arXiv : 1207.0953 , doi : 10.1007 / 978-3-642-35261-4_30 , MR 3065639.
- Fagin, Ronald (1983), "Grados de aciclicidad para hipergráficos y esquemas de bases de datos relacionales", Journal of the ACM , 30 : 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 de SIAM sobre Matemáticas Discretas y Aplicaciones, Filadelfia, PA: Sociedad de Matemáticas Industriales y Aplicadas, ISBN 0-89871-430-3, MR 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 hipergrafías mixtas: teoría, algoritmos y aplicaciones , Monografías del Fields Institute, 17 , Providence, RI: American Mathematical Society, ISBN 0-8218-2812-6, Señor 1912135.