Transversal

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 27 septembrie 2018; verificările necesită 10 modificări . A nu se confunda cu Triunghiul transversal .

Transversal ( sistem de reprezentanți diferiți ) este un concept din teoria mulțimilor , care este destul de important pentru toate matematicile discrete . Există, de asemenea, în logică și algebra liniară .

În matematică , pentru o familie dată de mulțimi , o transversală (numită și secțiune transversală în unele literaturi străine [1] [2] [3] ) este o mulțime care conține exact un element din fiecare mulțime din . Când mulțimile de la nu se intersectează, fiecărui element al transversalei îi corespunde exact un element (mulțimea din care face parte). Dacă mulțimile originale se intersectează, există două moduri de a defini transversala. Prima variantă imită situația în care mulțimile nu se intersectează reciproc, constă în existența unei bijecții de la transversală la , astfel încât pentru fiecare din transversală obținem că este mapată la un element . În acest caz, transversala se mai numește și sistem de reprezentanți distincti. O altă variantă, mai puțin folosită, nu necesită o relație unu-la-unu între elementele transversalei și mulțimile din . În această situație, elementele sistemului reprezentativ nu sunt neapărat distincte [4] [5] . Următoarele sunt definiții stricte ale celor mai comune abordări. $S$ $S$ $S$ $S$ $\varphi$ $S$ $X$ $X$ $\varphi(x)$ $S$

Definiții

1) Să fie un set. Fie booleanul multimii , i.e. multimea tuturor submultimii multimii . Să fie o mostră din . Elementele din această selecție pot fi repetate. $X$ $2^{X}$ $X$ $X$ $(X_{1},X_{2},\ldots, X_{n})$ $2^{X}$

Un vector de elemente de mulțime se numește transversal de familie dacă sunt valabile următoarele relații: $(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) Se notează ca o mulțime finită nevide și ca o familie a submulțimii sale, adică o succesiune de submulțimi nevide de lungime . $E$ $S=(S_{1},S_{2},\ldots,S_{m})$ $E$ $m$

O transversală a unei familii este o submulțime pentru care există o bijecție și pentru care condiția este îndeplinită . $S$ $T\subseteq E$ $\varphi \colon T\rightarrow \{1,2,\ldots ,m\}$ $\forall t\in T$ $t\in S_{\varphi (t))$

Cu alte cuvinte, pentru elementele transversalei există o astfel de enumerare sub care pentru . $t_{i}\in S_{i}$ $i\in \{1,2,\ldots ,m\}$

Deoarece este un set, atunci toate elementele sale sunt diferite, de unde și numele „sistem de reprezentanți diferiți ”. $T$

Exemple

1) Să fie date o mulțime și o familie de submulțimi . Un exemplu de transversală pentru o astfel de familie este , unde . $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\in S_{2},2\in S_{4},3\in S_{3},4\in S_{1)$

2) În unele instituții există comisioane. Din componența fiecărei comisii se cere să-și numească președinții, astfel încât nicio persoană să nu prezide mai mult de o comisie. Aici transversala comisiilor va fi compusă din președinții acestora. $m$

3) În teoria grupurilor, pentru un subgrup dat al unui grup, o transversală la dreapta (respectiv, la stânga) este o mulțime care conține exact un element din fiecare grupă din dreapta (respectiv, stânga) . În acest caz, „mulțile” (coseturile) nu se intersectează reciproc, adică. clasele formează o partiție a grupului. $H$ $G$ $H$

4) Ca caz special al exemplului anterior, ținând cont de produsul direct al grupelor , obținem care este o transversală pentru clase . $G=H\time K$ $H$ $K$

5) Deoarece orice relație de echivalență pe o mulțime arbitrară duce la o partiție, alegerea oricărui reprezentant din fiecare clasă de echivalență duce la o transversală.

6) Un alt caz de transversală bazată pe partiții apare atunci când se ia în considerare relația de echivalență cunoscută sub numele de nucleul (teoretic multime) al unei funcții definite pentru o funcție cu domeniul X ca partiție , care împarte domeniul f în clase de echivalență astfel încât toate elementele în clasă au aceeași imagine sub maparea f . Dacă f este injectiv, există o singură transversală . Pentru un f injectiv opțional , corectarea transversalei T in determină o corespondență unu-la-unu între T și imaginea lui f , notată mai jos ca . Prin urmare, funcția este bine definită de proprietatea că pentru tot z : , unde x este singurul element din T astfel încât ; în plus, g poate fi extins (nu neapărat în mod unic) astfel încât să fie definit pe întreaga gamă a lui f prin alegerea unor valori arbitrare pentru g(z) atunci când z este în afara imaginii f . Este un calcul simplu să vedem că g astfel definit are proprietatea , care este o dovadă (când domeniul și domeniul lui f sunt aceeași mulțime) că un semigrup complet de transformare este un semigrup obișnuit. Maparea acționează ca un (nu neapărat singurul) element cvasi-invers pentru f ; în teoria semigrupurilor, acesta este pur și simplu elementul invers. Totuși, rețineți că pentru un g arbitrar cu proprietatea de mai sus, ecuația „duală” poate să nu fie valabilă, dar dacă notăm , atunci f este cvasi-inversul lui h , adică . $f$ $\operatorname {ker} f:=\left\{\,\left\{\,y\in X\mid f(x)=f(y)\,\right\}\mid x\in X \,\dreapta\}$ $\operatorname {ker} f$ $\operatorname {ker} f$ $\operatorname {Im} f$ $g:(\operatorname {Im} f)\to T$ $\operatorname {Im} f,g(z)=x$ $f(x)=z$ $f\circ g\circ f=f$ $g$ $g\circ f\circ g=g$ $h=g\circ f\circ g$ $h\circ f\circ h=h$

Existenta

În practică, este mai des important să răspundem la întrebarea dacă există o transversală pentru o anumită familie. O formulare oarecum plină de umor a acestei întrebări este problema nunții:

Să fie niște bărbați tineri și niște fete. Mai mult, fiecare tânăr din primul set este familiarizat cu mai multe fete din al doilea. Se cere să se căsătorească cu toți tinerii, astfel încât fiecare să fie combinat într- o căsătorie monogamă cu o fată pe care o cunoaște.

Această problemă are o soluție dacă există o transversală pentru o familie de seturi formate din fete care cunosc un anumit băiat.

O soluție riguroasă a problemei existenței unei transversale este teorema lui Hall pentru transversale, precum și generalizarea acesteia, teorema lui Rado.

Teorema lui Hall pentru transversale

Fie o mulțime finită nevidă și o familie de submulțimi nevide nu neapărat diferite ale acesteia. În acest caz, are o transversală dacă și numai dacă, pentru submulțimile arbitrare , unirea lor include cel puțin elemente diferite [6] . $E$ $S=\left\{S_{1},S_{2},...,S_{m}\right\}$ $S$ $k$ $S_{i)$ $k$ $(k=1,2,...,m)$

Parțial transversal

Dacă este o injecție , atunci transversala se numește parțială . Transversale parțiale ale unei familii sunt transversale ale subfamiliilor sale. Orice submulțime a unei transversale este o transversală parțială. $\varphi$ $S$

Transversale independente

Să fie dat un matroid pe mulțime Fie o familie de submulțimi ale mulțimii . O transversală independentă pentru este o transversală care este o mulțime independentă în sensul matroidei specificate. În special, dacă un matroid este discret, atunci orice transversală este independentă. Următoarea teoremă oferă un criteriu pentru existența unei transversale independente. $E$ $S=(S_{1},S_{2},...,S_{m})$ $E$ $S$

Teorema lui R. Rado

Să fie un matroid . O secvență de submulțimi nevide ale unei mulțimi are o transversală independentă dacă și numai dacă uniunea oricăror submulțimi din această secvență conține o mulțime independentă cu cel puțin elemente, unde este un număr natural arbitrar care nu depășește . $M=(E,J)$ $S=(S_{1},S_{2},\ldots,S_{m})$ $E$ $k$ $k$ $k$ $m$

Dovada:

$\square$ Este convenabil să formulați condiția teoremei folosind conceptul de rang al unei mulțimi (cea mai mare cardinalitate a unei submulțimi independente):

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

Nevoie. Dacă există o transversală independentă, atunci intersecția ei cu mulțimea are elemente, de unde . $\bigcup \limits _{i\in A}{{S}_{i}}$ $\left|A\right|$ $\rho \left(\bigcup \limits _{i\in A}{{S}_{i}}\right)\geq \left|A\right|$

Adecvarea. Să demonstrăm mai întâi următoarea afirmație:

Afirmație. Dacă un anumit set (de exemplu, ) conține cel puțin două elemente, atunci un element poate fi eliminat din acest set fără a încălca condiția (1). $S_{1)$

$\vartriangle$ Dimpotrivă: lasă și, indiferent de ce element este eliminat din , condiția (1) nu va fi îndeplinită. Luați două elemente și din set . Pentru ei, există astfel de seturi de indici și , unde , că $\left|{{S}_{1}}\right|\geq 2$ $S_{1}$ $X$ $y$ $S_{1)$ ${A}'=\left\{1\right\}\bigcup A$ ${B}'=\left\{1\right\}\bigcup B$ $A,\B\subset \left\{2,\3,\\ldots ,\m\right\)$

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

Să punem: , . Vom rescrie relaţiile (2) sub forma: , de unde . (3) $X=\bigcup \limits _{i\in A}{{S}_{i}}\bigcup {\left({{S}_{1}}\backslash \left\{x\right\ }\dreapta)}$ $Y=\bigcup \limits _{i\in B}{{S}_{i}}\bigcup {\left({{S}_{1}}\backslash \left\{y\right\ }\dreapta)}$ $\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|$

Folosind condiția (1), estimăm de jos rangurile unirii și intersecției mulțimilor și . Deoarece , inegalitatea este valabilă . (patru) $X$ $Y$ $X\bigcup {Y}=\bigcup \limits _{i\in A\bigcup {B}}{{S}_{i}}\bigcup {\left({{S}_{1}} \backslash \left\{x\right\}\right)}\bigcup {\left({{S}_{1}}\backslash \left\{y\right\}\right)=\bigcup \limits _ {i\în A\bigcup {B}}{{S}_{i}}\bigcup {{S}_{1}}}$ $\rho \left(X\bigcup {Y}\right)\geq \left|A\bigcup {B}\right|+1$

Datorită faptului că avem . (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|$

Folosind proprietatea de semimodularitate a funcției de rang [7] , după adăugarea (4) și (5) obținem: . (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$

Inegalitatea (6) contrazice inegalitatea (3). Afirmația a fost dovedită. $\vartriangle$

Vom aplica procedura de la instrucțiune până când avem seturi singleton rămase . În acest caz, rangul uniunii lor este egal cu . Prin urmare, există transversala independentă dorită. $m$ $\left\{{{t}_{1}}\right\},\\left\{{{t}_{2}}\right\}\\ldots ,\\left\{{{ t}_{m}}\dreapta\}$ $T=\left\{{{t}_{1}},\ {{t}_{2}},\\ldots ,\{{t}_{m}}\right\}$ $m$ $T$ $\square$

Consecință

Să fie un matroid . O secvență de submulțimi nevide ale unei mulțimi are o transversală parțială independentă de cardinalitate dacă și numai dacă uniunea oricăror submulțimi din această secvență conține o submulțime independentă de cardinalitate cel puțin , i.e. [opt] $M=(E,J)$ $S=(S_{1},S_{2},\ldots,S_{m})$ $E$ $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.$

transversale generale

Criteriul de existență a unei transversale independente face posibilă obținerea condițiilor necesare și suficiente pentru existența unei transversale comune pentru două sisteme diferite de submulțimi ale aceleiași mulțimi.

Teorema

Două familii și submulțimi nevide ale unei mulțimi finite au o transversală comună dacă și numai dacă inegalitatea [8] este valabilă pentru orice submulțimi și mulțimi . $S=(S_{1},S_{2},...,S_{m})$ $R=(R_{1},R_{2},...,R_{m})$ $E$ $A$ $B$ ${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.$

O teoremă asupra numărului de transversale distincte ale unei familii de submulțimi

Fie o familie de submulțimi ale unei mulțimi . Fie cunoscută matricea . $S=(S_{1},S_{2},...,S_{m})$ $E$ $A={{\left({{a}_{ij}}\right)}_{n\x\,n}}=\left\{{\begin{aligned}&0,\ \ {{ x}_{j}}\notin {{S}_{i}}\\&1,\ \ {{x}_{j}}\in {{S}_{i}}\\\end{aliniat }}\dreapta.$

Atunci numărul diferitelor transversale ale familiei este egal cu permanentul matricei . [9] $S$ $A$

Link-uri către alte secțiuni și aplicație

În teoria optimizării și teoria grafurilor, găsirea unei transversale comune poate fi redusă la găsirea debitului maxim în rețea [8] .

În informatică , calculul transversalelor este utilizat în mai multe domenii de aplicare, iar familia de setări de intrare este adesea descrisă ca un hipergraf .

Elementele aflate pe diagonala principală a unei matrice pătrate arbitrare sunt, de asemenea, o transversală a unei familii de rânduri (coloane). Selectarea unei astfel de transversale este folosită pentru a demonstra un număr de rezultate în teoria probabilităților și algebră .

Utilizarea transversalelor și a acoperirilor din acestea stă la baza metodei Euler-Parker de căutare a pătratelor latine ortogonale la un pătrat latin dat.

Generalizare

Noţiunea de transversală poate fi generalizată.

Să existe o succesiune de numere întregi pozitive . Apoi -transversala familiei va fi familia de submulțimi ale mulțimii pentru care sunt îndeplinite următoarele condiții: $(k_{1},k_{2},\ldots,k_{m})$ $(k_{1},k_{2},\ldots,k_{m})$ $S$ $P=(P_{1},P_{2},\ldots,P_{m})$ $E$

$P_{i}\subseteq S_{i)$ pentru ; $i\in \{1,2,\ldots ,m\}$
$|P_{i}|=k_{i}$ ;
$P_{i}\cap P_{j}=\varnothing, i\neq j$ .

Note

↑ John Mackintosh HowieFundamentele teoriei semigrupurilor . - Oxford University Press , 1995. - P. 63. - ISBN 978-0-19-851194-6 .
↑ Clive Reis. Algebră abstractă : o introducere în grupuri, inele și câmpuri . - World Scientific , 2011. - P. 57. - ISBN 978-981-4335-64-5 .
↑ Bruno Courcelle; Joost Engelfriet. Structura graficului și logica monadică de ordinul doi: o abordare teoretică a limbajului . - Cambridge University Press , 2012. - P. 95. - ISBN 978-1-139-64400-6 .
↑ Roberts, Tesman, 2009 , p. 692.
↑ Brualdi, 2010 , p. 322.
↑ Kapitonova Yu. V., Krivoy S. L., Letichevsky A. A. Prelegeri despre matematică discretă. - Sankt Petersburg, BHV-Petersburg, 2004. - isbn 5-94157-546-7. - c. 529
↑ Funcția de rang, semimodularitate . Rezumate Wiki ITMO . Data accesului: 6 decembrie 2019. Arhivat din original pe 6 decembrie 2019. (nedefinit)
↑ 1 2 3 Toate Matematica Superioară: Manual. T.7., 2006
↑ V.N. Sachkov, 1982

Literatură

M.L. Krasnov, A.I. Kiselev, G.I. Makarenko, E.V. Shikin, V.I. Zalyapin, A.Yu. Evnin. Toate Matematica Superioară: Manual. - M . : KomKniga, 2006. - T. 7. - 208 p. — ISBN 5-484-00521-3 .

M. Hall. Capitolul nr.5 „Sisteme ale diverșilor reprezentanți” // Combinatorică = Teoria combinatorie / trad. din engleza. S. A. Shirokova; ed. A. O. Gelfond și V. E. Tarakanov. - M . : Mir, 1970. - S. 65 -78. — 424 p.
V.N. Sachkov. Introducere în metodele combinatorii ale matematicii discrete. - M .: Știință. Ch. ed. Fiz.-Matematică. lit., 1982. - 384 p.

M. Swami, K. Thulasiraman. Capitolul Nr. 8.6 „Potrivirea în grafice bipartite” // Grafice, rețele și algoritmi = Grafice, rețele și algoritmi / transl. din engleza. M. V. Gorbatova, V. L. Torkhova, S. A. Frolov, V. N. Chetverikov; ed. V. A. Gorbatov. - M . : Mir, 1984. - S. 165-166. — 455 p. — 11.000 de exemplare.
V. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, R. I. Tyshkevich. Prelegeri despre teoria grafurilor. - M . : Nauka , 1990. - S. 87-92. — 384 p. — ISBN 5-02-013992-0 .
N. I. Kostyukova. Grafice și aplicațiile lor . — Curs nr. 16: Teoria transversalelor. Preluat: 29 iulie 2009. (nedefinit)
Alexander Schrijver. Capitolul 22 „Transversale”, capitolul 23 „Transversale comune” // Optimizare combinatorie . - Springer, 2003. - P. 378-409. — 1800 p. — ISBN 978-3540443896 .
Roberts F., Tesman B. Combinatorică aplicată. - Boca Raton: CRC Press, 2009. - ISBN 978-1-4200-9982-9 .
Brualdi R. Combinatorică introductivă. - Upper Saddle River, NJ: Prentice Hall, 2010. - ISBN 0-13-602040-2 .