Hipergrafo crítico
En teoría de hipergrafos, el hipergrafo crítico o simplemente el crítico de un hipergrafo H definido sobre un conjunto base A, es el hipergrafo σ(H) conformado por los subconjuntos de A tal que cada uno de sus elementos intersecan a una hiperarista de H diferente. Formalmente, dado un hipergrafo H definido sobre un conjunto base A, el crítico de H es el operador definido como:
Note que σ(H) es subconjunto del conjunto potencia del conjunto base, P(A).
El crítico de una estructura de hipergrafos G:=(H, K) se define como:
y no σ(G):=(τ(K),τ(H)) como se podría pensar. Esto debido a que el operador crítico es antítono.
Complejidad computacional[editar]
Del punto de vista de complejidad computacional, determinar el crítico de un hipergrafo es un problema ineficiente, que crece exponencialmente en función del tamaño de la entrada (sea esta H o G). Sin embargo, determinar si una hiperarista dada pertenece o no a un hipergrafo crítico, sí es un problema resoluble en tiempo polinómico.
Referencias[editar]
- Polyméris, Andreas (2008). «Stability of two player game structures». Discrete Applied Mathematics 156 (14). ISSN 0166-218X, p. 2636-2646.