| 词条 | Hypertree |
| 释义 |
In mathematics, 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. PropertiesEvery 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.{{sfnp|Tarjan|Yannakakis|1984}} 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.[9] See also
Notes1. ^{{harvtxt|Brandstädt|Dragan|Chepoi|Voloshin|1998}} 2. ^{{harvtxt|Berge|1989}} 3. ^{{harvtxt|McKee|McMorris|1999}} 4. ^{{harvtxt|Berge|1989}}; {{harvtxt|Voloshin|2002}} 5. ^{{harvtxt|Berge|1989}}; {{harvtxt|Voloshin|2002}} 6. ^See, e.g., {{harvtxt|Brandstädt|Le|Spinrad|1999}}; {{harvtxt|McKee|McMorris|1999}} 7. ^{{harvtxt|Berge|1989}} 8. ^{{harvtxt|Fagin|1983}} 9. ^{{harvtxt|Brandstädt|Leitert|Rautenbach|2012}} References{{refbegin|30em}}
| last = Berge | first = Claude | authorlink = Claude Berge | title = Hypergraphs: Combinatorics of Finite Sets | publisher = North Holland | location = Amsterdam | isbn = 0-444-87489-5 | series = North-Holland Mathematical Library | volume = 45 | mr = 1013569 | year = 1989}}.
| last1 = Brandstädt | first1 = Andreas | author1-link = Andreas Brandstädt | last2 = Dragan | first2 = Feodor | last3 = Chepoi | first3 = Victor | last4 = Voloshin | first4 = Vitaly | title = Dually chordal graphs | journal = SIAM Journal on Discrete Mathematics | volume = 11 | pages = 437–455 | mr = 1628114 | url = http://pageperso.lif.univ-mrs.fr/~victor.chepoi/DualChGr.pdf | year = 1998 | doi=10.1137/s0895480193253415}}.
| last1 = Brandstädt | first1 = Andreas | author1-link = Andreas Brandstädt | last2 = Le | first2 = Van Bang | last3 = Spinrad | first3 = Jeremy | title = Graph Classes: A Survey | publisher = SIAM Monographs on Discrete Mathematics and Applications | year = 1999 | mr = 1686154 | isbn = 0-89871-432-X}}.
| last1 = Brandstädt | first1 = Andreas | author1-link = Andreas Brandstädt | last2 = Leitert | first2 = Arne | last3 = Rautenbach | first3 = Dieter | contribution = Efficient dominating and edge dominating sets for graphs and hypergraphs | series = Lecture Notes in Computer Science | title = Algorithms and Computation: 23rd International Symposium, ISAAC 2012, Taipei, Taiwan, December 19-21, 2012, Proceedings | volume = 7676 | pages = 267–277 | year = 2012 | doi = 10.1007/978-3-642-35261-4_30 | mr = 3065639 | arxiv = 1207.0953}}.
| last = Fagin | first = Ronald | author-link = Ronald Fagin | title = Degrees of acyclicity for hypergraphs and relational database schemes | mr = 0709831 | doi = 10.1145/2402.322390 | journal = Journal of the ACM | volume = 30 | pages = 514–550 | year = 1983}}.
| last1 = McKee | first = T.A. | last2 = McMorris | first2 = F.R. | series = SIAM Monographs on Discrete Mathematics and Applications | title = Topics in Intersection Graph Theory | year = 1999 | isbn = 0-89871-430-3 | publisher = Society for Industrial and Applied Mathematics | location = Philadelphia, PA | mr = 1672910}}.
| last1 = Tarjan | first1 = Robert E. | author1-link = Robert Tarjan | last2 = Yannakakis | first2 = Mihalis | author2-link = Mihalis Yannakakis | doi = 10.1137/0213035 | issue = 3 | journal = SIAM Journal on Computing | mr = 749707 | pages = 566–579 | title = Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs | volume = 13 | year = 1984}}.
| last = Voloshin | first = Vitaly | series = Fields Institute Monographs | volume = 17 | title = Coloring Mixed Hypergraphs: Theory, Algorithms and Applications | publisher = American Mathematical Society | location = Providence, RI | year = 2002 | isbn = 0-8218-2812-6 | mr = 1912135}}.{{refend}} 2 : Hypergraphs|Trees (graph theory) |
| 随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。