Transversal (matemática)

En teoría de hipergrafos y combinatoria, la transversal de un hipergrafo H definido sobre un conjunto base A, es el hipergrafo τ(H) conformado por los subconjuntos de A que intersecan a todas las hiperaristas de H. Formalmente, dado un hipergrafo H definido sobre un conjunto base A, la transversal de H es el operador definido como:

$\tau(\mathcal{H}):=\{Z\subseteq A; \forall X\in\mathcal{H}, X\cap Z\neq\emptyset\}$

Note que τ(H) es subconjunto del conjunto potencia del conjunto base, P(A).

El conjunto transversal de una estructura de hipergrafos G:=(H,K) se define como:

$\tau(\mathcal{G}):=(\tau(\mathcal{K}),\tau(\mathcal{H}))$

y no τ(G):=(τ(K),τ(H)) como se podría pensar. Esto debido a que el operador transversal es antítono.

Complejidad computacional

Del punto de vista de complejidad computacional, el operador transversal es ineficiente, pues crece exponencialmente en función del tamaño de la entrada (sea esta H o G). En efecto, la única forma de determinar todos sus elementos es recorriendo todos los elementos de P(A), y verificando la condición de intersección de la definición.

Referencias

• Polyméris, Andreas (2008). «Stability of two player game structures». Discrete Applied Mathematics 156 (14). ISSN 0166-218X, p. 2636-2646.