Hypertree - Hypertree

Pro další použití viz Hypertree (disambiguation).
Hypertree (modré vrcholy a žluté hyperedge) a jeho hostitelský strom (červený)

V matematice, a hypergraf H se nazývá a vysoký strom pokud připouští a hostitelský graf T takhle T je strom. Jinými slovy, H je vysoký strom, pokud existuje strom T takové, že každý hyperedge z H je množina vrcholů připojeného podstromu T.[1] Byly také povolány hyperstromy stromové hypergrafy[2] nebo stromové hypergrafy.[3]

Každý strom T je sám o sobě vysoký strom: T sám může být použit jako hostitelský graf a každá hrana T je podstrom tohoto hostitelského grafu. Hypertele lze proto považovat za zobecnění pojmu strom pro hypergrafy.[4] Zahrnují připojené Berge-acyklické hypergrafy, které byly také použity jako (odlišné) zobecnění stromů pro hypergrafy.

Vlastnosti

Každý vysoký strom má Helly majetek (Vlastnost 2-Helly): pokud je podmnožinou S jeho hyperedges má vlastnost, ve které každé dva hyperedges S mít tedy neprázdnou křižovatku S sám má neprázdnou křižovatku (vrchol, který patří ke všem hyperedges v S).[5]

Podle výsledků Ducheta, Flamenta a Slatera[6] hypertrees lze ekvivalentně charakterizovat následujícími způsoby.

Je možné rozpoznat hyperstromy (jako duály alfa-acyklických hypergrafů) v lineární čas.[9]The přesný obal problém (nalezení sady nepřekrývajících se hyperedge, které pokrývá všechny vrcholy) je řešitelný v polynomiálním čase pro hyperrees, ale zůstává NP-kompletní pro alfa-acyklické hypergrafy.[10]

Viz také

Poznámky

  1. ^ Brandstädt a kol. (1998)
  2. ^ Berge (1989)
  3. ^ McKee & McMorris (1999)
  4. ^ Berge (1989); Voloshin (2002)
  5. ^ Berge (1989); Voloshin (2002)
  6. ^ Viz např. Brandstädt, Le & Spinrad (1999); McKee & McMorris (1999)
  7. ^ Berge (1989)
  8. ^ Fagin (1983)
  9. ^ Tarjan a Yannakakis (1984).
  10. ^ Brandstädt, Leitert & Rautenbach (2012)

Reference

  • Berge, Claude (1989), Hypergraphs: Combinatorics of Finite SetsMatematická knihovna v Severním Holandsku, 45, Amsterdam: Severní Holandsko, ISBN  0-444-87489-5, PAN  1013569.
  • Brandstädt, Andreas; Dragan, Feodor; Chepoi, Victor; Voloshin, Vitaly (1998), "Dvojitě chordální grafy" (PDF), SIAM Journal on Discrete Mathematics, 11: 437–455, doi:10.1137 / s0895480193253415, PAN  1628114.
  • Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), Třídy grafů: PrůzkumMonografie SIAM o diskrétní matematice a aplikacích, ISBN  0-89871-432-X, PAN  1686154.
  • Brandstädt, Andreas; Leitert, Arne; Rautenbach, Dieter (2012), „Efficient dominating and edge dominating sets for graphs and hypergraphs“, Algoritmy a výpočet: 23. mezinárodní sympozium, ISAAC 2012, Tchaj-pej, Tchaj-wan, 19. – 21. Prosince 2012, sborník, Přednášky z informatiky, 7676, str. 267–277, arXiv:1207.0953, doi:10.1007/978-3-642-35261-4_30, PAN  3065639.
  • Fagin, Ronald (1983), „Stupně acyklicity pro hypergrafy a schémata relačních databází“, Deník ACM, 30: 514–550, doi:10.1145/2402.322390, PAN  0709831.
  • McKee, T. A.; McMorris, F.R. (1999), Témata v teorii křižovatkových grafůMonografie SIAM o diskrétní matematice a aplikacích, Philadelphia, PA: Společnost pro průmyslovou a aplikovanou matematiku, ISBN  0-89871-430-3, PAN  1672910.
  • Tarjan, Robert E.; Yannakakis, Mihalis (1984), „Jednoduché algoritmy lineárního času pro testování chordality grafů, testování acyklicity hypergrafů a selektivní redukci acyklických hypergrafů“ (PDF), SIAM Journal on Computing, 13 (3): 566–579, doi:10.1137/0213035, PAN  0749707.
  • Voloshin, Vitaly (2002), Barevné smíšené hypergrafy: Teorie, algoritmy a aplikaceMonografie Fields Institute, 17, Providence, RI: American Mathematical Society, ISBN  0-8218-2812-6, PAN  1912135.