Hypertree

Hypertree

A hypergraph "H" is called a hypertree, if it has a host graph "T" such that "T" is a tree and every hyperedge of "H" induces a subtree in "T". V. I. Voloshin (2002) "Coloring Mixed Hypergraphs", ISBN 0821828126 , [http://books.google.com/books?id=RYM_Qi5HR68C&pg=PA26&dq=hypertree+hypergraph&ei=TX7vSJiuOZHEMaT4pA4&sig=ACfU3U12X-utDYS4BRfgYOOvlCAUCFV-gQ#PPA23,M1 p. 23] ]

Since a tree is a hypertree, hypertrees may be seen as a generalization of the notion of a tree for hypergraphs. Any hypertree is isomorphic to some family of subtrees of a tree.

Properties

A hypertree has the Helly property (2-Helly property), i.e., if any two hyperedges from a subset of its hyperedges have a common vertex, then all hyperedges of the subset have a common vertex.

The line graph of a hypertree is a chordal graph.

A hypergraph is a hypertree if and only if its dual hypergraph is conformal and chordal.

References


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Hypertree (disambiguation) — Hypertree may refer to one of the following:*Hypertree, a special kind of hypergraph, e.g, a hypergraph without cycles *Hypertree network, a type of computer/communication network topology *Hyperbolic tree, a visualization method for hierarchical …   Wikipedia

  • Hypertree network — A hypertree network is a network topology that shares some traits with the binary tree network. Parallel Programming in C with MPI and OpenMP , by Michael J. Quinn, [http://books.google.com/books?id=tDxNyGSXg5IC pg=PA31 dq=%22hypertree+network%22 …   Wikipedia

  • Decomposition method (constraint satisfaction) — In constraint satisfaction, a decomposition method translates a constraint satisfaction problem into another constraint satisfaction problem that is binary and acyclic. Decomposition methods work by grouping variables into sets, and solving a… …   Wikipedia

  • ERROL — (an acronym for Entity Relationship Role Oriented Language) is a declarative database query and manipulation language for the Entity relationship model (ERM). It is applicable to any data model on which ERM can be mapped, virtually any general… …   Wikipedia

  • Conjunctive query — In database theory, a conjunctive query is a restricted form of first order queries. A large part of queries issued on relational databases can be written as conjunctive queries, and large parts of other first order queries can be written as… …   Wikipedia

  • Hyperbolic tree — In Web development jargon and information visualization, a hyperbolic tree (often shortened as hypertree) defines a visualization method for a graph inspired by hyperbolic geometry.Displaying hierarchical data as a tree suffers from visual… …   Wikipedia

  • Georg Gottlob — Infobox Scientist name = Georg Gottlob image width = caption = birth date = Birth date and age|1956|6|30|mf=y birth place = Vienna, Austria death date = death place = residence = Oxford, United Kingdom citizenship = nationality = Austrian… …   Wikipedia

  • Star network — Star networks are one of the most common computer network topologies. In its simplest form, a star network consists of one central switch, hub or computer, which acts as a conduit to transmit messages. Thus, the hub and leaf nodes, and the… …   Wikipedia

  • Fat tree — The fat tree network, invented by Charles E. Leiserson of MIT, is a universal network for provably efficient communication. Unlike an ordinary computer scientist s notion of a tree, which has skinny links all over, the links in a fat tree become… …   Wikipedia

  • List of network theory topics — Network theory is an area of applied mathematics. This page is a list of network theory topics. See also List of graph theory topics. Contents 1 Network theorems 2 Network properties 3 Network theory applications …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”