Hypertree

For other uses, see Hypertree (disambiguation).
A hypertree (blue vertices and yellow hyperedges) and its host tree (red)

In the mathematical field of graph theory, a hypergraph H is called a hypertree if it admits a host graph T such that T is a tree. In other words, H is a hypertree if there exists a tree T such that every hyperedge of H is the set of vertices of a connected subtree of T.[1] Hypertrees have also been called arboreal hypergraphs[2] or tree hypergraphs.[3]

Every tree T is itself a hypertree: T itself can be used as the host graph, and every edge of T is a subtree of this host graph. Therefore, hypertrees may be seen as a generalization of the notion of a tree for hypergraphs.[4] They include the connected Berge-acyclic hypergraphs, which have also been used as a (different) generalization of trees for hypergraphs.

Properties

Every hypertree has the Helly property (2-Helly property): if a subset S of its hyperedges has the property that every two hyperedges in S have a nonempty intersection, then S itself has a nonempty intersection (a vertex that belongs to all hyperedges in S).[5]

By results of Duchet, Flament and Slater[6] hypertrees may be equivalently characterized in the following ways.

It is possible to recognize hypertrees (as duals of alpha-acyclic hypergraphs) in linear time.[9] The exact cover problem (finding a set of non-overlapping hyperedges that covers all the vertices) is solvable in polynomial time for hypertrees but remains NP-complete for alpha-acyclic hypergraphs.[10]

See also

Notes

  1. ^ Brandstädt et al. (1998)
  2. ^ Berge (1989)
  3. ^ McKee & McMorris (1999)
  4. ^ Berge (1989); Voloshin (2002)
  5. ^ Berge (1989); Voloshin (2002)
  6. ^ See, e.g., Brandstädt, Le & Spinrad (1999); McKee & McMorris (1999)
  7. ^ Berge (1989)
  8. ^ Fagin (1983)
  9. ^ Tarjan & Yannakakis (1984).
  10. ^ Brandstädt, Leitert & Rautenbach (2012)

References

  • 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 (3): 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 dominating and edge dominating sets for graphs and hypergraphs", Algorithms and Computation: 23rd International Symposium, ISAAC 2012, Taipei, Taiwan, December 19-21, 2012, Proceedings, Lecture Notes in Computer Science, vol. 7676, pp. 267–277, arXiv:1207.0953, doi:10.1007/978-3-642-35261-4_30, ISBN 978-3-642-35260-7, MR 3065639.
  • Fagin, Ronald (1983), "Degrees of acyclicity for hypergraphs and relational database schemes", Journal of the ACM, 30 (3): 514–550, doi:10.1145/2402.322390, MR 0709831.
  • McKee, T.A.; McMorris, F.R. (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), "Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs" (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.

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.