Haven (graph theory)

Haven (graph theory)

In graph theory, if G is a graph, and k ge 0 is an integer, a haven of order k in G is a function assigning to every set X subseteq V(G) with ig|Xig| < k a vertex set of a component of G igackslash X, etaig(Xig), such that if X subseteq Y subseteq V(G) and ig|Yig| < k, then eta(Y) subseteq eta(X).

The Min-max theorem for tree-width states that a graph has a haven of order k if and only if it has tree width at least k - 1.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Haven — is a harbor or anchorage protected from the sea, or, by extension, a place of safety; a refuge or sanctuary.Haven may also refer to:Books and comics* Haven (Artemis Fowl), a place in the Artemis Fowl series * Haven (X Men), a villain in the X Men …   Wikipedia

  • Strategy (game theory) — In game theory, a player s strategy in a game is a complete plan of action for whatever situation might arise; this fully determines the player s behaviour. A player s strategy will determine the action the player will take at any stage of the… …   Wikipedia

  • Neo-Riemannian theory — refers to a loose collection of ideas present in the writings of music theorists such as David Lewin, Brian Hyer, Richard Cohn, and Henry Klumpenhouwer. Drawing on the work of Hugo Riemann (1849 1919), these theorists grouped together… …   Wikipedia

  • List of mathematics articles (H) — NOTOC H H cobordism H derivative H index H infinity methods in control theory H relation H space H theorem H tree Haag s theorem Haagerup property Haaland equation Haar measure Haar wavelet Haboush s theorem Hackenbush Hadamard code Hadamard… …   Wikipedia

  • Parity of zero — Zero objects, divided into two equal groups Zero is an even number. In other words, its parity the quality of an integer being even or odd is even. Zero fits the definition of even number : it is an integer multiple of 2, namely 0 × 2. As a… …   Wikipedia

  • Tree decomposition — A graph with eight vertices, and a tree decomposition of it onto a tree with six nodes. Each graph edge connects two vertices that are listed together at some tree node, and each graph vertex is listed at the nodes of a contiguous subtree of the… …   Wikipedia

  • Evenness of zero — The number 0 is even. There are several ways to determine whether an integer is even or odd, all of which indicate that 0 is an even number: it is a multiple of 2, it is evenly divisible by 2, it is surrounded on both sides by odd integers, and… …   Wikipedia

  • Voting system — For other uses, see Voting system (disambiguation). Part of the Politics series Electoral methods …   Wikipedia

  • Parité de zéro — Zéro objets, divisés en deux groupes égaux. Zéro est un nombre pair, étant donné qu il remplit la définition d un nombre pair : être un multiple de deux. Par conséquent, zéro partage toutes les propriétés qui découlent de cette… …   Wikipédia en Français

  • Clandestine cell system — Sleeper cell redirects here. For other uses, see Sleeper cell (disambiguation). Terrorism Definitions · Counter terrorism Internation …   Wikipedia

Share the article and excerpts

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