Anar al contingut

Hiperárbol

De L'Enciclopèdia, la wikipedia en valencià
Hiperárbol

En ciències de la computació, un hipergrafo H és un hiperárbol, si existix un arbre T tal que cada hiperarista de H induïx un subárbol en T.[1]

Ya que els arbres són a la seua volta hiperárboles, estos últims poden ser vists com una generalisació de la noció d'arbre per a hipergrafos. Qualsevol hiperárbol és isomorfo a alguna família de subárboles d'un arbre.[1]

Propietats

Un hiperárbol posseïx la propietat de 2-Helly, que indica lo següent: si dos hiperaristas d'un subconjunt dels seus hiperaristas té un vèrtiç en comú, llavors totes les hiperaristas del subconjunt tenen un vèrtiç comú.[1]

Referències

  1. ↑ 1,0 1,1 1,2 V. I. Voloshin (2002) Coloring Mixed Hypergraphs, ISBN 0821828126 , p. 23


Referències