Hyperträd
Inom det matematiska området grafteorin kallas en hypergraf H ett hyperträd om den tillåter en värdgraf T så att T är ett träd . Med andra ord, H är ett hyperträd om det finns ett träd T så att varje hyperkant av H är uppsättningen av hörn av ett anslutet underträd av T . Hyperträd har också kallats trädhypergrafer eller trädhypergrafer .
Varje träd T är i sig ett hyperträd: T självt kan användas som värdgraf, och varje kant av T är ett underträd till denna värdgraf. Därför kan hyperträd ses som en generalisering av begreppet ett träd för hypergrafer . De inkluderar de sammankopplade Berge-acykliska hypergraferna, som också har använts som en (annan) generalisering av träd för hypergrafer.
Egenskaper
Varje hyperträd har Helly-egenskapen (2-Helly-egenskap): om en delmängd S av dess hyperkanter har egenskapen att varannan hyperkant i S har en icke-tom skärningspunkt , så har S själv en icke-tom skärningspunkt (en vertex som tillhör alla hyperkanter i S ).
Genom resultat av Duchet, kan Flament och Slater hyperträd karakteriseras på samma sätt på följande sätt.
- En hypergraf H är ett hyperträd om och endast om den har egenskapen Helly och dess linjediagram är en ackordsgraf .
- En hypergraf H är ett hyperträd om och endast om dess dubbla hypergraf H * är konform och 2-sektionsgrafen för H * är ackordal.
- En hypergraf är ett hyperträd om och endast om dess dubbla hypergraf är alfa-acyklisk i betydelsen Fagin.
Det är möjligt att känna igen hyperträd (som dualer av alfa-acykliska hypergrafer) i linjär tid . Det exakta täckningsproblemet (att hitta en uppsättning icke-överlappande hyperkanter som täcker alla hörn) är lösbart i polynomtid för hyperträd men förblir NP-komplett för alfaacykliska hypergrafer.
Se även
- Dual chordal graph , en graf vars maximala klicker bildar ett hyperträd
Anteckningar
- Berge, Claude (1989), Hypergraphs: Combinatorics of Finite Sets , North-Holland Mathematical Library, vol. 45, Amsterdam: North Holland, ISBN 0-444-87489-5 , MR 1013569 .
- Brandstädt, Andreas ; Dragan, Feodor; Chepoi, Victor; Voloshin, Vitaly (1998), "Dually chordal graphs" (PDF) , SIAM Journal on Discrete Mathematics , 11 : 437–455, doi : 10.1137/s0895480193253415 , MR 16281 .
- 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), "Efficient dominating and edge dominating sets for graphs and hypergraphs", Algoritmer och beräkningar: 23rd International Symposium, ISAAC 2012, Taipei, Taiwan, 19-21 december 2012, Proceedings , Lecture Notes in Computer Science , vol. 7676, s. 267–277, arXiv : 1207.0953 , doi : 10.1007/978-3-642-35261-4_30 , MR 3065639 .
- Fagin, Ronald (1983), "Degrees of acyclicity for hypergraphs and relational databas schemes", 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, Philadelphia, PA: Society for Industrial and Applied Mathematics, ISBN 0-89871-430-3 , MR 1672910 .
- Tarjan, Robert E. ; Yannakakis, Mihalis (1984), "Enkla linjärtidsalgoritmer för att testa ackordalitet hos grafer, testa acyklicitet hos hypergrafer och selektivt reducera acykliska hypergrafer" (PDF), SIAM Journal on Computing , 13 (3): 566–579, doi : 10.1137/0213035 , MR 0749707 .
- Voloshin, Vitaly (2002), Coloring Mixed Hypergraphs: Theory, Algorithms and Applications , Fields Institute Monographs, vol. 17, Providence, RI: American Mathematical Society, ISBN 0-8218-2812-6 , MR 1912135 .