Blocker

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:

τ ( H ) := { Z ⊆ A ; ∀ X ∈ H , X ∩ Z ≠ ∅ } {\displaystyle \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:

τ ( G ) := ( τ ( K ) , τ ( H ) ) {\displaystyle \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[editar]

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[editar]

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

Control de autoridades|

* Proyectos Wikimedia
* Datos: Q2208651

|

* Datos: Q2208651