Anar al contingut

Hipergrafo crític

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

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:

σ(ℋ):={Z⊆A;∀a∈Z,∃X∈ℋ con X∩Z={a}}

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