Hipergrafo crític
En teoria de hipergrafos, el hipergrafo crític o simplement el crític d'un hipergrafo H definit sobre un conjunt base A, és el hipergrafo σ(H) conformat pels subconjunts de A tal que cada u dels seus elements intersecan a una hiperarista de H diferent. Formalment, donat un hipergrafo H definit sobre un conjunt base A, el crític de H és l'operador definit com:
Note que σ(H) és subconjunt del conjunt potencia del conjunt base, P(A).
El crític d'una estructura de hipergrafos G:=(H, K) es definix com:
i no σ(G):=(τ(K),τ(H)) com es podria pensar. Açò degut a que l'operador crític és antítono.
Complexitat computacional
Del punt de vista de complexitat computacional, determinar el crític d'un hipergrafo és un problema ineficiente, que creix exponencialment en funció del tamany de l'entrada (siga esta H o G). No obstant, determinar si una hiperarista donada pertany o no a un hipergrafo crític, sí és un problema resoluble en temps polinòmic.
Referències
- Este artícul conté una traducció derivada de «Hipergrafo crítico» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.