Transversal

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 27 de septiembre de 2018; las comprobaciones requieren 10 ediciones . No debe confundirse con Triángulo transversal .

Transversal ( sistema de diferentes representantes ) es un concepto de la teoría de conjuntos , que es bastante importante para todas las matemáticas discretas . También existe en lógica y álgebra lineal .

En matemáticas , para una familia dada de conjuntos , una transversal (también llamada sección transversal en alguna literatura extranjera [1] [2] [3] ) es un conjunto que contiene exactamente un elemento de cada conjunto de . Cuando los conjuntos de no se cortan entre sí, cada elemento de la transversal corresponde exactamente a un elemento (el conjunto del cual es miembro). Si los conjuntos originales se intersecan, hay dos formas de definir la transversal. La primera variante imita la situación cuando los conjuntos no se intersecan entre sí, consiste en la existencia de una biyección de la transversal a , de manera que para cada uno en la transversal obtenemos que está mapeado a algún elemento . En este caso, la transversal también se denomina sistema de representantes distintos. Otra variante menos utilizada no requiere una relación biunívoca entre los elementos de la transversal y los conjuntos de . En esta situación, los elementos del sistema representativo no son necesariamente distintos [4] [5] . Las siguientes son definiciones estrictas de los enfoques más comunes. $S$ $S$ $S$ $S$ $\varphi$ $S$ $X$ $X$ $\varfi(x)$ $S$

Definiciones

1) Sea algún conjunto. Sea el booleano del conjunto , es decir el conjunto de todos los subconjuntos del conjunto . Sea una muestra de . Los elementos de esta selección pueden repetirse. $X$ $2^{X}$ $X$ $X$ $(X_{1},X_{2},\ldots,X_{n})$ $2^{X}$

Un vector de conjunto de elementos se llama familia transversal si se cumplen las siguientes relaciones: $(x_{1},x_{2},\ldots,x_{n})$ $X$ $(X_{1},X_{2},\ldots,X_{n})$

a) . $x_{i}\in X_{i},\forall i\in {\overline {1,n))$

b) $x_{i}\neq x_{j},\forall i,j\in {\overline {1,n))$

2) Denota como un conjunto no vacío finito y como una familia de sus subconjuntos, es decir, una secuencia de subconjuntos no vacíos de longitud . $mi$ $S=(S_{1},S_{2},\ldots,S_{m})$ $mi$ $metro$

Una transversal de una familia es un subconjunto para el que existe una biyección y para el que se cumple la condición . $S$ $T\subseteq E$ $\varphi \colon T\rightarrow \{1,2,\ldots,m\}$ ${\ estilo de visualización \ para todos los t \ en T}$ ${\displaystyle t\in S_{\varphi (t)))$

En otras palabras, para los elementos de la transversal existe tal enumeración bajo la cual para . ${\ estilo de visualización t_ {i} \ en S_ {i}}$ $i\in \{1,2,\ldots,m\}$

Dado que es un conjunto, entonces todos sus elementos son diferentes, de ahí el nombre de "sistema de diferentes representantes". $T$

Ejemplos

1) Sean dados un conjunto y una familia de subconjuntos . Un ejemplo de transversal para tal familia es , donde . $E=\{1,2,3,4,5\}$ $S=(S_{1}=\{1,4,5\},S_{2}=\{1\},S_{3}=\{2,3,4\},S_{4 }=\{2,4\})$ $T=\{1,2,3,4\}$ $1\en S_{2},2\en S_{4},3\en S_{3},4\en S_{1}$

2) En alguna institución hay comisiones. Se requiere de la composición de cada comisión nombrar a sus presidentes de modo que ninguna persona presida más de una comisión. Aquí la transversal de las comisiones estará compuesta por sus presidentes. $metro$

3) En la teoría de grupos, para un subgrupo dado de un grupo, una transversal derecha (respectivamente, izquierda) es un conjunto que contiene exactamente un elemento de cada clase lateral derecha (respectivamente, izquierda) . En este caso, los "conjuntos" (cosets) no se cruzan entre sí, es decir, las clases laterales forman una partición del grupo. $H$ $GRAMO$ $H$

4) Como caso especial del ejemplo anterior, teniendo en cuenta el producto directo de grupos , obtenemos que es una transversal por clases laterales . ${\ estilo de visualización G = H \ veces K}$ $H$ $k$

5) Dado que cualquier relación de equivalencia sobre un conjunto arbitrario conduce a una partición, la elección de cualquier representante de cada clase de equivalencia conduce a una transversal.

6) Otro caso de transversal basada en particiones surge cuando se considera la relación de equivalencia conocida como núcleo (teórico de conjuntos) de una función definida para una función con dominio X como su partición que divide el dominio f en clases de equivalencia tales que todos los elementos en la clase tienen la misma imagen bajo el mapeo f . Si f es inyectiva, solo hay una transversal . Para una f opcionalmente inyectiva , la corrección de la transversal T provoca una correspondencia biunívoca entre T y la imagen de f , denotada a continuación como . Por lo tanto, la función está bien definida por la propiedad de que para todo z : , donde x es el único elemento en T tal que ; además, g se puede extender (no necesariamente de forma única) para que se defina en todo el rango de f eligiendo valores arbitrarios para g(z) cuando z está fuera de la imagen f . Es un cálculo simple ver que g así definido tiene la propiedad , que es una prueba (cuando el dominio y el rango de f son el mismo conjunto) de que un semigrupo de transformación completa es un semigrupo regular. El mapeo actúa como un (no necesariamente el único) elemento cuasi-inverso para f ; en la teoría de semigrupos, esto es simplemente el elemento inverso. Sin embargo, tenga en cuenta que para una g arbitraria con la propiedad anterior, la ecuación "dual" puede no ser válida, pero si denotamos , entonces f es casi la inversa de h , es decir, . $F$ $\operatorname {ker} f:=\left\{\,\left\{\,y\in X\mid f(x)=f(y)\,\right\}\mid x\in X \,\Correcto\}$ ${\ estilo de visualización \ nombre del operador {ker} f}$ ${\ estilo de visualización \ nombre del operador {ker} f}$ ${\ estilo de visualización \ nombre del operador {Im} f}$ $g:(\operatorname {Im} f)\to T$ ${\ estilo de visualización \ nombre del operador {Im} f, g (z) = x}$ ${\ estilo de visualización f (x) = z}$ $f\circ g\circ f=f$ $gramo$ $g\circ f\circ g=g$ $h=g\circ f\circ g$ $h\circ f\circ h=h$

Existencia

En la práctica, es más importante responder a la pregunta de si existe una transversal para una familia en particular. Una formulación algo humorística de esta pregunta es el problema de la boda:

Que haya un grupo de hombres jóvenes y un grupo de niñas. Además, cada joven del primer grupo está familiarizado con varias chicas del segundo. Se requiere casar a todos los jóvenes para que cada uno se combine en un matrimonio monógamo con una chica que conozca.

Este problema tiene solución si existe una transversal para una familia de conjuntos formados por chicas que conocen a un chico en particular.

Una solución rigurosa al problema de la existencia de una transversal es el teorema de Hall para las transversales, así como su generalización, el teorema de Rado.

Teorema de Hall para transversales

Sea un conjunto finito no vacío y sea una familia de subconjuntos no vacíos no necesariamente diferentes del mismo. En este caso, tiene una transversal si y sólo si, para subconjuntos arbitrarios , su unión incluye al menos elementos diferentes [6] . $mi$ $S=\izquierda\{S_{1},S_{2},...,S_{m}\derecha\}$ $S$ $k$ ${\ Displaystyle S_ {yo}}$ $k$ ${\ estilo de visualización (k = 1,2, ..., m)}$

Transversal parcial

Si es una inyección , entonces la transversal se llama parcial . Las transversales parciales de una familia son transversales de sus subfamilias. Cualquier subconjunto de una transversal es una transversal parcial. $\varphi$ $S$

Transversales independientes

Sea alguna matroide sobre el conjunto Sea una familia de subconjuntos del conjunto . Una transversal independiente para es una transversal que es un conjunto independiente en el sentido de la matroide especificada. En particular, si una matroide es discreta, entonces cualquier transversal es independiente. El siguiente teorema da un criterio para la existencia de una transversal independiente. $mi$ $S=(S_{1},S_{2},...,S_{m})$ $mi$ $S$

Teorema de R. Rado

Sea un matroide . Una secuencia de subconjuntos no vacíos de un conjunto tiene una transversal independiente si y solo si la unión de cualquier subconjunto de esta secuencia contiene un conjunto independiente con al menos elementos, donde es un número natural arbitrario que no excede . ${\ estilo de visualización M = (E, J)}$ $S=(S_{1},S_{2},\ldots,S_{m})$ $mi$ $k$ $k$ $k$ $metro$

Prueba:

${\ estilo de visualización \ cuadrado}$ Es conveniente formular la condición del teorema utilizando el concepto de rango de un conjunto (la mayor cardinalidad de un subconjunto independiente):

$\forall A\subset \left\{1,2,\ldots,m\right\}\ \ \ \rho \left(\bigcup \limits _{i\in A}{{S}_{i }}\derecha)\geq \izquierda|A\derecha|$ (una)

Necesitar. Si hay una transversal independiente, entonces su intersección con el conjunto tiene elementos, de donde . $\bigcup \limits _{i\in A}{{S}_{i}}$ ${\ estilo de visualización \ izquierda | A \ derecha |}$ $\rho \left(\bigcup \limits _{i\in A}{{S}_{i}}\right)\geq \left|A\right|$

Adecuación. Probemos primero la siguiente afirmación:

Declaración. Si un determinado conjunto (por ejemplo, ) contiene al menos dos elementos, entonces se puede eliminar un elemento de este conjunto sin violar la condición (1). ${\ Displaystyle S_ {1}}$

${\ estilo de visualización \ vartriangle}$ Por el contrario: sea y, no importa qué elemento se elimine de , la condición (1) no se cumplirá. Tome dos elementos y del conjunto . Para ellos, existen tales conjuntos de índices y , donde , que ${\ estilo de visualización \ izquierda | {{S}_{1}} \ derecha | \ geq 2}$ $S_{1}$ $X$ $y$ ${\ Displaystyle S_ {1}}$ ${A}'=\left\{1\right\}\bigcup A$ ${B}'=\left\{1\right\}\bigcup B$ ${\displaystyle A,\B\subset \left\{2,\ 3,\ \ldots,\ m\right\))$

$\rho \left(\bigcup \limits _{i\in A}{{S}_{i}}\left(\bigcup {{{S}_{1}}\barra invertida \left\{x \right\}}\right)\right)<\left|{{A}'}\right|=\left|A\right|+1$ y . (2) $\rho \left(\bigcup \limits _{i\in B}{{S}_{i}}\left(\bigcup {{{S}_{1}}\barra invertida \left\{y \right\}}\right)\right)<\left|{{B}'}\right|=\left|B\right|+1$

Pongamos: , . Reescribiremos las relaciones (2) en la forma: , de donde . (3) $X=\bigcup \limits _{i\in A}{{S}_{i}}\bigcup {\left({{S}_{1}}\barra invertida \left\{x\right\ }\Correcto)}$ $Y=\bigcup \limits _{i\in B}{{S}_{i}}\bigcup {\left({{S}_{1}}\barra invertida \left\{y\right\ }\Correcto)}$ $\rho \left(X\right)\leq \left|A\right|;\ \rho \left(Y\right)\leq \left|B\right|$ $\rho \left(X\right)+\ \rho \left(Y\right)\leq \left|A\right|+\left|B\right|$

Usando la condición (1), estimamos desde abajo los rangos de la unión y la intersección de los conjuntos y . Como , la desigualdad se cumple . (cuatro) $X$ $Y$ $X\bigcup {Y}=\bigcup \limits _{i\in A\bigcup {B}}{{S}_{i}}\bigcup {\left({{S}_{1}} \barra invertida \left\{x\right\}\right)}\bigcup {\left({{S}_{1}}\barra invertida \left\{y\right\}\right)=\bigcup \limits _ {i\en A\bigcup {B}}{{S}_{i}}\bigcup {{S}_{1}}}$ $\rho \left(X\bigcup {Y}\right)\geq \left|A\bigcup {B}\right|+1$

Debido al hecho de que , tenemos . (5) $X\bigcap {Y}\supset \bigcup \limits _{i\in A\bigcap {B}}{{S}_{i}}$ $\rho \left(X\bigcap {Y}\right)\geq \left|A\bigcap {B}\right|$

Usando la propiedad de semimodularidad de la función de rango [7] , luego de sumar (4) y (5) obtenemos: . (6) $\rho \left(X\right)+\rho \left(Y\right)\geq \rho \left(X\bigcup {Y}\right)+\rho \left(X\bigcap {Y} \right)\geq \left|A\bigcup {B}\right|+\left|A\bigcap {B}\right|+1=\left|A\right|+\left|B\right|+1$

La desigualdad (6) contradice la desigualdad (3). La afirmación ha sido probada. ${\ estilo de visualización \ vartriangle}$

Aplicaremos el procedimiento desde el enunciado hasta que nos queden conjuntos singleton . En este caso, el rango de su sindicato es igual a . Por lo tanto, existe la transversal independiente deseada. $metro$ $\left\{{{t}_{1}}\right\},\ \left\{{{t}_{2}}\right\}\ \ldots,\ \left\{{{ t}_{m}}\derecho\}$ $T=\left\{{{t}_{1}},\ {{t}_{2}},\ \ldots,\ {{t}_{m}}\right\}$ $metro$ $T$ ${\ estilo de visualización \ cuadrado}$

Consecuencia

Sea un matroide . Una secuencia de subconjuntos no vacíos de un conjunto tiene una transversal parcial independiente de cardinalidad si y solo si la unión de cualquier subconjunto de esta secuencia contiene un subconjunto independiente de cardinalidad al menos , es decir [ocho] ${\ estilo de visualización M = (E, J)}$ $S=(S_{1},S_{2},\ldots,S_{m})$ $mi$ $t$ $k$ $k+tm$ $\forall A\subset \left\{1,\ 2,\ \ldots,\ m\right\}\ \ \ \rho \left(\bigcup \limits _{i\in A}{S{} _ {i}}\right)\geq \left|A\right|+tm.$

Transversales generales

El criterio de la existencia de una transversal independiente permite obtener condiciones necesarias y suficientes para la existencia de una transversal común para dos sistemas diferentes de subconjuntos de un mismo conjunto.

Teorema

Dos familias y subconjuntos no vacíos de un conjunto finito tienen una transversal común si y solo si la desigualdad [8] se cumple para cualquier subconjunto y conjunto . $S=(S_{1},S_{2},...,S_{m})$ $R=(R_{1},R_{2},...,R_{m})$ $mi$ $A$ $B$ ${\ estilo de visualización {1,2,...,m))$ $\left|\left(\bigcup \limits _{i\in A}{{S}_{i}}\right)\bigcap {\left(\bigcup \limits _{i\in B}{ {R}_{i}}\right)}\right|\geq \left|A\right|+\left|B\right|-m.$

Un teorema sobre el número de transversales distintas de una familia de subconjuntos

Sea una familia de subconjuntos de algún conjunto . Sea conocida la matriz . $S=(S_{1},S_{2},...,S_{m})$ $mi$ $A={{\left({{a}_{ij}}\right)}_{n\ x\,n}}=\left\{{\begin{alineado}&0,\ \ {{ x}_{j}}\notin {{S}_{i}}\\&1,\ \ {{x}_{j}}\in {{S}_{i}}\\\end{alineado }}\Correcto.$

Entonces el número de diferentes transversales de la familia es igual al permanente de la matriz . [9] $S$ $A$

Enlaces a otras secciones y aplicación

En teoría de optimización y teoría de grafos, encontrar una transversal común puede reducirse a encontrar el flujo máximo en la red [8] .

En informática , el cálculo de transversales se utiliza en varias áreas de aplicación, y la familia de conjuntos de entrada a menudo se describe como una hipergrafía .

Los elementos que se encuentran en la diagonal principal de una matriz cuadrada arbitraria también son una transversal de una familia de filas (columnas). La selección de tal transversal se utiliza para probar una serie de resultados en la teoría de la probabilidad y el álgebra .

El uso de transversales y coberturas a partir de ellas subyace en el método de Euler-Parker de búsqueda de cuadrados latinos ortogonales a un cuadrado latino dado.

Generalización

La noción de transversal puede generalizarse.

Sea una sucesión de enteros positivos . Entonces la -transversal de la familia será la familia de subconjuntos del conjunto para los que se cumplen las siguientes condiciones: $(k_{1},k_{2},\ldots,k_{m})$ $(k_{1},k_{2},\ldots,k_{m})$ $S$ $P=(P_{1},P_{2},\ldots,P_{m})$ $mi$

${\displaystyle P_{i}\subseteq S_{i))$ para ; $i\in \{1,2,\ldots,m\}$
${\ estilo de visualización | P_ {i} | = k_ {i}}$ ;
$P_{i}\cap P_{j}=\varnada,i\neq j$ .

Notas

↑ John Mackintosh HowieFundamentos de la Teoríade Semigrupos . - Oxford University Press , 1995. - Pág. 63. - ISBN 978-0-19-851194-6 .
↑ Clive Reis. Álgebra abstracta : una introducción a los grupos, anillos y campos . - World Scientific , 2011. - Pág. 57. - ISBN 978-981-4335-64-5 .
↑ Bruno Courcelle; Joost Engelfriet. Estructura gráfica y lógica monádica de segundo orden: un enfoque teórico del lenguaje . - Cambridge University Press , 2012. - Pág. 95. - ISBN 978-1-139-64400-6 .
↑ Roberts, Tesman, 2009 , pág. 692.
↑ Brualdi, 2010 , pág. 322.
↑ Kapitonova Yu. V., Krivoy S. L., Letichevsky A. A. Conferencias sobre matemáticas discretas. - San Petersburgo, BHV-Petersburg, 2004. - isbn 5-94157-546-7. - C. 529
↑ Función de rango, semimodularidad . Resúmenes de la wiki de la ITMO . Fecha de acceso: 6 de diciembre de 2019. Archivado desde el original el 6 de diciembre de 2019. (indefinido)
↑ 1 2 3 Todas las matemáticas superiores: libro de texto. T.7., 2006
↑ VN Sachkov, 1982

Literatura

ML Krasnov, A. I. Kiselev, G. I. Makarenko, E. V. Shikin, VI. Zaliapin, A.Yu. Evnin. Todas las matemáticas superiores: libro de texto. - M. : KomKniga, 2006. - T. 7. - 208 p. — ISBN 5-484-00521-3 .

Salón M. Capítulo No. 5 "Sistemas de varios representantes" // Combinatoria = Teoría Combinatoria / trad. De inglés. S. A. Shirokova; edición A. O. Gelfond y V. E. Tarakanov. - M. : Mir, 1970. - S. 65 -78. — 424 págs.
V. N. Sachkov. Introducción a los métodos combinatorios de las matemáticas discretas. - M. : Ciencia. cap. edición Phys.-Math. lit., 1982. - 384 p.

M. Swami, K. Thulasiraman. Capítulo No. 8.6 "Emparejamiento en grafos bipartitos" // Grafos, redes y algoritmos = Grafos, Redes y Algoritmos / trad. De inglés. M. V. Gorbatova, V. L. Torkhova, S. A. Frolov, V. N. Chetverikov; edición V. A. Gorbatova. - M. : Mir, 1984. - S. 165-166. — 455 págs. — 11.000 copias.
V. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, R. I. Tyshkevich. Clases de teoría de grafos. - M. : Nauka , 1990. - S. 87-92. — 384 pág. — ISBN 5-02-013992-0 .
N. I. Kostiukova. Gráficos y sus aplicaciones . — Lección nº 16: Teoría de las transversales. Consultado: 29 de julio de 2009. (indefinido)
Alejandro Schrijver. Capítulo 22 "Transversales", capítulo 23 "Transversales comunes" // Optimización combinatoria . - Springer, 2003. - Pág. 378-409. — 1800 pág. — ISBN 978-3540443896 .
Roberts F., Tesman B. Combinatoria aplicada. - Boca Ratón: CRC Press, 2009. - ISBN 978-1-4200-9982-9 .
Brualdi R. Combinatoria introductoria. - Upper Saddle River, Nueva Jersey: Prentice Hall, 2010. - ISBN 0-13-602040-2 .