Anar al contingut

Transversal (matemàtica)

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

En teoria de hipergrafos i combinatòria, la transversal d'un hipergrafo H definit sobre un conjunt base A, és el hipergrafo τ(H) conformat pels subconjunts de A que intersecan a totes les hiperaristas de H. Formalment, donat un hipergrafo H definit sobre un conjunt base A, la transversal de H és l'operador definit com:

τ(ℋ):={Z⊆A;∀X∈ℋ,X∩Z≠∅}

Note que τ(H) és subconjunt del conjunt potencia del conjunt base, P(A).

El conjunt travesser 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 travesser és antítono.

Complexitat computacional

Del punt de vista de complexitat computacional, l'operador travesser és ineficiente, puix creix exponencialment en funció del tamany de l'entrada (siga esta H o G). En efecte, l'única forma de determinar tots els seus elements és recorrent tots els elements de P(A), i verificant la condició d'intersecció de la definició.

Referències