Hypertree
W matematycznej dziedzinie teorii grafów hipergraf H nazywany jest hiperdrzewem, jeśli dopuszcza graf macierzysty T taki, że T jest drzewem . Innymi słowy, H jest hiperdrzewem, jeśli istnieje drzewo T takie, że każda hiperkrawędź H jest zbiorem wierzchołków połączonego poddrzewa T . Hiperdrzewa były również nazywane nadrzewnymi hipergrafami lub hipergrafy drzew .
Każde drzewo T samo w sobie jest hiperdrzewem: samo T może być użyte jako graf główny, a każda krawędź T jest poddrzewem tego grafu głównego. Dlatego hiperdrzewa mogą być postrzegane jako uogólnienie pojęcia drzewa dla hipergrafów . Obejmują one połączone acykliczne hipergrafy Berge'a, które były również używane jako (inne) uogólnienie drzew dla hipergrafów.
Nieruchomości
Każde hiperdrzewo ma właściwość Helly (właściwość 2-Helly): jeśli podzbiór S jego hiperkrawędzi ma tę właściwość, że każde dwie hiperkrawędzie w S mają niepuste przecięcie , to samo S ma niepuste przecięcie (wierzchołek, który należy do wszystkich hiperkrawędzi w S. ).
Na podstawie wyników Ducheta, Flamenta i Slatera hiperdrzewa można równoważnie scharakteryzować w następujący sposób.
- Hipergraf H jest hipergrafem wtedy i tylko wtedy, gdy ma właściwość Helly, a jego graf liniowy jest grafem akordowym .
- Hipergraf H jest hipergrafem wtedy i tylko wtedy, gdy jego podwójny hipergraf H * jest konforemny , a dwusekcyjny graf H * jest akordowy.
- Hipergraf jest hiperdrzewem wtedy i tylko wtedy, gdy jego podwójny hipergraf jest alfa-acykliczny w sensie Fagina.
Możliwe jest rozpoznanie hiperdrzew (jako duali alfa-acyklicznych hipergrafów) w czasie liniowym . Dokładny pokrycia (znalezienie zestawu nienakładających się hiperkrawędzi, który obejmuje wszystkie wierzchołki) jest rozwiązywalny w czasie wielomianowym dla hiperdrzew, ale pozostaje NP-zupełny dla hipergrafów alfa-acyklicznych.
Zobacz też
- Wykres podwójnie akordowy , graf, którego maksymalne kliki tworzą hiperdrzewo
Notatki
- Berge, Claude (1989), Hipergrafy: Kombinatoryka zbiorów skończonych , North-Holland Mathematical Library, tom. 45, Amsterdam: Holandia Północna, ISBN 0-444-87489-5 , MR 1013569 .
- Brandstädt, Andreas ; Dragan, Fiodor; Chepoi, Victor; Voloshin, Vitaly (1998), „Dually 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), „Efficient dominujące and edge dominujące sets for graphs and hypergraphs”, Algorytmy i obliczenia: 23. międzynarodowe sympozjum, ISAAC 2012, Tajpej, Tajwan, 19-21 grudnia 2012 r., Proceedings , Lecture Notes in Computer Science , tom. 7676, s. 267-277, arXiv : 1207.0953 , doi : 10.1007/978-3-642-35261-4_30 , MR 3065639 .
- Fagin, Ronald (1983), „Stopnie acykliczności dla hipergrafów i schematów relacyjnych baz danych”, 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, Filadelfia, PA: Society for Industrial and Applied Mathematics, ISBN 0-89871-430-3 , MR 1672910 .
- Tarjan, Robert E .; Yannakakis, Mihalis (1984), „Proste algorytmy czasu liniowego do testowania akordów grafów, testowania acykliczności hipergrafów i selektywnej redukcji hipergrafów acyklicznych” (PDF) , SIAM Journal on Computing , 13 (3): 566–579, doi : 10.1137/0213035 , MR 0749707 .
- Wołoszyn, Witalij (2002), Kolorowanie mieszanych hipergrafów: teoria, algorytmy i zastosowania , Monografie Fields Institute, tom. 17, Providence, RI: Amerykańskie Towarzystwo Matematyczne, ISBN 0-8218-2812-6 , MR 1912135 .