Hiperárbol

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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[editar]

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[editar]

  1. a b c V. I. Voloshin (2002) Coloring Mixed Hypergraphs, ISBN 0821828126 , p. 23