- Hiperárbol
-
En ciencias de la computación, un hipergrafo H es un hiperárbol, si existe un árbol T tal que cada hiperarista de H induce un subárbol en T.[1]
Dado que los árboles son a su vez hiperárboles, estos últimos pueden ser vistos como una generalización de la noción de árbol para hipergrafos. Cualquier hiperárbol es isomorfo a alguna familia de subárboles de un árbol.[1]
Propiedades
Un hiperárbol posee la propiedad de 2-Helly, que indica lo siguiente: si dos hiperaristas de un subconjunto de sus hiperaristas tiene un vértice en común, entonces todas las hiperaristas del subconjunto tienen un vértice común.[1]
Referencias
- ↑ a b c V. I. Voloshin (2002) Coloring Mixed Hypergraphs, ISBN 0821828126 , p. 23
Categorías:- Teoría de hipergrafos
- Árboles (estructura)
Wikimedia foundation. 2010.