En teoria de hipergrafos, el hipergrafo minimal o simplement minimal d'un hipergrafo H definit sobre un conjunt base A, és el hipergrafo μ(H) conformat per totes les hiperaristas mínimes de H, és dir, aquelles tal que cap atra és subconjunt d'elles. Formalment, donat un hipergrafo H definit sobre un conjunt base A, el minimal de H és l'operador definit com:

μ(ℋ):={X∈ℋ;∀X′∈ℋ,X′⊄X}

Note que μ(H) és subconjunt de H.

El minimal d'una estructura de hipergrafos G:=(H, K) es definix com:

μ(𝒢):=(μ(ℋ),μ(𝒦))

Complexitat computacional

Un hipergrafo minimal pot determinar-se en temps polinòmic en funció del tamany de l'entrada (siga esta H o G). En efecte, n'hi ha prou en recórrer cada hiperarista de cada hipergrafo, i anar verificant si una és o no subconjunt de l'atra.

Referències