Transversal (matemática)

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. 

Wikimedia foundation. 2010.

Игры ⚽ Нужна курсовая?

Mira otros diccionarios:

  • Transversal — hace referencia a varios artículos en Wikipedia: Contenido 1 Matemática y geometría 2 Epidemiología 3 Política 4 Educación …   Wikipedia Español

  • Volumen (matemática) — En matemáticas el volumen es una medida que se define como los demás conceptos métricos a partir de una distancia o tensor métrico. En los dominios de tres dimensiones, el volumen se calcula mediante la integral triple extendida a dicho dominio,… …   Wikipedia Español

  • Wikipedia:Café (todos) — Atajos WP:CWP:C …   Wikipedia Español

  • Geodesia — Modelo digital del terreno del Cantón del Valais. El término Geodesia, del griego γη ( tierra ) y δαιζω ( dividir ) fue usado inicialmente por Aristóteles (384 322 a. C.) y puede significar, tanto divisiones geográficas de la tierra ,… …   Wikipedia Español

  • Onda (física) — Para otros usos de este término, véase Onda (desambiguación). Ondas propagadas en agua …   Wikipedia Español

  • Onda plana — El frente de onda de una onda plana viajando en el espacio …   Wikipedia Español

  • Órbita — Para otros usos de este término, véase Órbita (desambiguación). Animación de dos objetos orbitando alrededor de un centro de masas común. En física, una órbita es la trayectoria que describe un objeto alrededor de otro mientras está bajo la… …   Wikipedia Español

  • Estadística — Saltar a navegación, búsqueda Para análisis, datos y gráficas sobre Wikipedia, véase Wikipedia:Estadísticas. La estadística es una ciencia con base matemática referente a la recolección, análisis e interpretación de datos, que busca explicar… …   Wikipedia Español

  • Imperio inca — Saltar a navegación, búsqueda Para otros usos de este término, véase Inca (desambiguación). Tawantinsuyu Imperio inca …   Wikipedia Español

  • Competencia (aprendizaje) — Este artículo o sección necesita referencias que aparezcan en una publicación acreditada, como revistas especializadas, monografías, prensa diaria o páginas de Internet fidedignas. Puedes añadirlas así o avisar …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”