Hipergrafo minimal

En teoría de hipergrafos, el hipergrafo minimal o simplemente minimal de un hipergrafo H definido sobre un conjunto base A, es el hipergrafo μ(H) conformado por todas las hiperaristas mínimas de H, es decir, aquellas tal que ninguna otra es subconjunto de ellas. Formalmente, dado un hipergrafo H definido sobre un conjunto base A, el minimal de H es el operador definido como:

$\mu ({\mathcal {H}}):=\{X\in {\mathcal {H}};\forall X'\in {\mathcal {H}},X'\not \subset X\}$

Note que μ(H) es subconjunto de H.

El minimal de una estructura de hipergrafos G:=(H, K) se define como:

$\mu ({\mathcal {G}}):=(\mu ({\mathcal {H}}),\mu ({\mathcal {K}}))$

Complejidad computacional

Un hipergrafo minimal puede determinarse en tiempo polinómico en función del tamaño de la entrada (sea esta H o G). En efecto, basta con recorrer cada hiperarista de cada hipergrafo, e ir verificando si una es o no subconjunto de la otra.

Referencias

• Polyméris, Andreas (2008). «Stability of two player game structures». Discrete Applied Mathematics 156 (14). ISSN 0166-218X, p. 2636-2646. 

• Datos: Q5898286