Transversal (matemàtica)
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:
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
- Este artícul conté una traducció derivada de «Transversal (matemática)» 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.