Transversal (combinatoria)
En matemáticas , particularmente en combinatoria , dada una familia de conjuntos , aquí llamada colección C , una transversal (también llamada sección transversal [1] [2] [3] ) es un conjunto que contiene exactamente un elemento de cada miembro de la colección. Cuando los conjuntos de la colección son mutuamente disjuntos, cada elemento de la transversal corresponde exactamente a un miembro de C (el conjunto del que es miembro). Si los conjuntos originales no son disjuntos, existen dos posibilidades para la definición de una transversal:
En informática , la computación transversal es útil en varios dominios de aplicación, y la familia de conjuntos de entrada a menudo se describe como un hipergráfico .
Una cuestión fundamental en el estudio de los DEG es si existe o no. El teorema del matrimonio de Hall da las condiciones necesarias y suficientes para que una colección finita de conjuntos, algunos posiblemente superpuestos, tenga una transversal. La condición es que, para cada entero k , cada colección de k conjuntos debe contener en común al menos k elementos diferentes. [4] : 29
Teorema . Sea S 1 , S 2 , ..., S m una colección de conjuntos tales que contenga al menos k elementos para k = 1,2, ..., my para todas las k -combinaciones { } de los enteros 1, 2, ..., my suponga que cada uno de estos conjuntos contiene al menos t elementos. Si t ≤ m , entonces la colección tiene al menos t ! SDR, y si t > m , entonces la colección tiene al menos t ! / ( t -m )! DEG.
Se puede construir un gráfico bipartito en el que los vértices de un lado son los conjuntos, los vértices del otro lado son los elementos y los bordes conectan un conjunto con los elementos que contiene. Entonces, una transversal (definida como un sistema de representantes distintos ) es equivalente a una coincidencia perfecta en este gráfico.
Se puede construir un hipergráfico en el que los vértices son los elementos y los hipergrafos son los conjuntos. Entonces, una transversal (definida como un sistema de representantes no necesariamente distintos ) es una cubierta de vértice en un hipergráfico .