Tværgående

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 27. september 2018; checks kræver 10 redigeringer . Ikke at forveksle med Triangle transversal .

Transversal ( system af forskellige repræsentanter ) er et begreb fra mængdeteori , som er ret vigtigt for al diskret matematik . Det findes også i logik og lineær algebra .

I matematik er for en given familie af mængder et tværsnit (også kaldet et tværsnit i noget udenlandsk litteratur [1] [2] [3] ) et sæt , der indeholder præcis et element fra hvert sæt fra . Når sæt fra ikke skærer hinanden, svarer hvert element i transversalen til præcis ét element (det sæt, som det er medlem af). Hvis de originale sæt skærer hinanden, er der to måder at definere tværgående. Den første variant efterligner situationen, når mængderne ikke skærer hinanden, den består i eksistensen af en bijektion fra tværgående til , så vi for hver i tværgående får, at den er afbildet til et eller andet element . I dette tilfælde kaldes det tværgående også et system af distinkte repræsentanter. En anden, mindre brugt variant kræver ikke et en-til-en forhold mellem elementerne i transversalen og sættene fra . I denne situation er elementerne i det repræsentative system ikke nødvendigvis adskilte [4] [5] . Følgende er strenge definitioner af de mest almindelige tilgange. $S$ $S$ $S$ $S$ $\varphi$ $S$ $x$ $x$ $\varphi(x)$ $S$

Definitioner

1) Lad være nogle sæt. Lad være sættets Boolean , dvs. sættet af alle undersæt af sættet . Lad være med et eksempel fra . Elementerne i dette udvalg kan gentages. $x$ $2^{X}$ $x$ $x$ $(X_{1},X_{2},\ldots,X_{n})$ $2^{X}$

En vektor af mængdeelementer kaldes en familietværgående, hvis følgende relationer gælder: $(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) Betegn som et endeligt ikke-tomt sæt , og som en familie af dets delmængder, det vil sige en sekvens af ikke-tomme delmængder af længde . $E$ $S=(S_{1},S_{2},\ldots ,S_{m})$ $E$ $m$

En tværgående af en familie er en delmængde , for hvilken der er en bijektion , og for hvilken betingelsen er opfyldt . $S$ $T\subseteq E$ $\varphi \colon T\rightarrow \{1,2,\ldots ,m\}$ $\forall t\in T$ ${\displaystyle t\in S_{\varphi (t)))$

Med andre ord er der for elementerne i det tværgående en sådan opregning, hvorunder for . $t_{i}\in S_{i}$ $i\in \{1,2,\ldots ,m\}$

Da det er et sæt, er alle dets elementer forskellige, deraf navnet "system af forskellige repræsentanter". $T$

Eksempler

1) Lad et sæt og en familie af delmængder være givet . Et eksempel på en tværgående for sådan en familie er , hvor . $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\}$ ${\displaystyle 1\i S_{2},2\i S_{4},3\i S_{3},4\i S_{1))$

2) I nogle institutioner er der kommissioner. Det kræves af sammensætningen af hver kommission at udpege deres formænd, således at ingen person leder mere end én kommission. Her vil den tværgående af kommissionerne blive sammensat af deres formænd. $m$

3) I gruppeteori, for en given undergruppe af en gruppe, er en højre (henholdsvis venstre) transversal et sæt, der indeholder nøjagtigt et element fra hver højre (henholdsvis venstre) coset . I dette tilfælde skærer "sættene" (cosets) ikke hinanden, dvs. cosets danner en opdeling af gruppen. $H$ $G$ $H$

4) Som et særligt tilfælde af det foregående eksempel, under hensyntagen til det direkte produkt af grupper , får vi, som er en tværgående for cosets . $G=H\ gange K$ $H$ $K$

5) Da enhver ækvivalensrelation på et vilkårligt sæt fører til en partition, fører valget af enhver repræsentant fra hver ækvivalensklasse til en tværgående.

6) Et andet tilfælde af partitionsbaseret transversal opstår, når man betragter ækvivalensrelationen kendt som den (mængdeteoretiske) kerne af en funktion defineret for en funktion med domæne X som dens partition , som opdeler domænet f i ækvivalensklasser, således at alle elementer i klassen har samme billede under mappingen f . Hvis f er injektiv, er der kun en transversal . For et eventuelt injektivt f forårsager korrigering af det tværgående T i en en-til-en overensstemmelse mellem T og billedet af f , angivet nedenfor som . Derfor er funktionen veldefineret af egenskaben, at for alle z : , hvor x er det eneste element i T , således at ; desuden kan g udvides (ikke nødvendigvis entydigt), så den defineres over hele området f ved at vælge vilkårlige værdier for g(z), når z er uden for billedet f . Det er en simpel beregning at se, at g således defineret har egenskaben , som er et bevis (når domænet og området for f er det samme sæt), at en komplet transformationssemigruppe er en regulær semigruppe. Kortlægningen fungerer som et (ikke nødvendigvis det eneste) kvasi-inverse element for f ; i semigruppeteori er dette simpelthen det omvendte element. Bemærk dog, at for en vilkårlig g med ovenstående egenskab, holder den "dobbelte" ligning muligvis ikke, men hvis vi angiver , så er f kvasi-omvendt af h , det vil sige . $f$ $\operatørnavn {ker} f:=\venstre\{\,\venstre\{\,y\in X\mid f(x)=f(y)\,\right\}\mid x\in X \,\ret\}$ $\operatørnavn {ker} f$ $\operatørnavn {ker} f$ $\operatørnavn {Im} f$ $g:(\operatørnavn {Im} f)\to T$ $\operatørnavn {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$

Eksistens

I praksis er det oftere vigtigt at besvare spørgsmålet, om der findes en tværgående for en bestemt familie. En noget humoristisk formulering af dette spørgsmål er bryllupsproblemet:

Lad der være et sæt unge mænd og et sæt piger. Desuden er hver ung mand fra det første sæt bekendt med flere piger fra det andet. Det er påkrævet at gifte sig med alle de unge mænd, så de hver især bliver kombineret i et monogamt ægteskab med en pige, han kender.

Dette problem har en løsning, hvis der eksisterer en tværgående for en familie af sæt dannet af piger, der kender en bestemt dreng.

En stringent løsning på problemet med eksistensen af en transversal er Halls teorem for transversaler, såvel som dens generalisering, Rados teorem.

Halls teorem for transversaler

Lad være en ikke-tom endelig mængde og være en familie af ikke nødvendigvis forskellige ikke-tomme delmængder af det. I dette tilfælde har den en tværgående, hvis og kun hvis, for vilkårlige delmængder , deres forening indeholder mindst forskellige elementer [6] . $E$ $S=\left\{S_{1},S_{2},...,S_{m}\right\}$ $S$ $k$ ${\displaystyle S_{i))$ $k$ $(k=1,2,...,m)$

Delvis tværgående

Hvis det er en indsprøjtning , så kaldes den transversale partial . Delvis tværgående af en familie er tværgående af dens underfamilier. Enhver delmængde af en transversal er en delvis transversal. $\varphi$ $S$

Uafhængige transversaler

Lad nogle matroid blive givet på sættet . Lad være en familie af delmængder af sættet . En uafhængig transversal for er en transversal, der er et selvstændigt sæt i betydningen af den angivne matroide. Især hvis en matroide er diskret, så er enhver transversal uafhængig. Følgende sætning giver et kriterium for eksistensen af en uafhængig transversal. $E$ $S=(S_{1},S_{2},...,S_{m})$ $E$ $S$

R. Rados sætning

Lad være en matroid . En sekvens af ikke-tomme delmængder af et sæt har en uafhængig tværgående, hvis og kun hvis foreningen af nogen delmængder fra denne sekvens indeholder et uafhængigt sæt med mindst elementer, hvor et vilkårligt naturligt tal ikke overstiger . $M=(E,J)$ $S=(S_{1},S_{2},\ldots ,S_{m})$ $E$ $k$ $k$ $k$ $m$

Bevis:

$\square$ Det er praktisk at formulere betingelsen for sætningen ved hjælp af begrebet rang af et sæt (den største kardinalitet af en uafhængig delmængde):

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

Brug for. Hvis der er en uafhængig tværgående, så har dens skæring med sættet elementer, hvorfra . $\bigcup \limits _{i\in A}{{S}_{i}}$ $\left|A\right|$ $\rho \left(\bigcup \limits _{i\in A}{{S}_{i}}\right)\geq \left|A\right|$

Tilstrækkelighed. Lad os først bevise følgende påstand:

Udmelding. Hvis et bestemt sæt (f.eks. ) indeholder mindst to elementer, kan ét element fjernes fra dette sæt uden at overtræde betingelsen (1). ${\displaystyle S_{1))$

$\vartriangle$ Tværtimod: lad og, uanset hvilket element der fjernes fra , vil betingelse (1) ikke være opfyldt. Tag to elementer og fra sættet . For dem er der sådanne sæt af indekser og , hvor , at $\left|{{S}_{1}}\right|\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}}\backslash \left\{x \right\}}\right)\right)<\left|{{A}'}\right|=\left|A\right|+1$ og . (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$

Lad os sige: , . Vi vil omskrive relationer (2) i formen: , hvorfra . (3) $X=\bigcup \limits _{i\in A}{{S}_{i}}\bigcup {\left({{S}_{1}}\backslash \left\{x\right\ }\ret)}$ $Y=\bigcup \limits _{i\in B}{{S}_{i}}\bigcup {\left({{S}_{1}}\backslash \left\{y\right\ }\ret)}$ $\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|$

Ved at bruge betingelse (1) estimerer vi fra under rækken af foreningen og skæringspunktet mellem sættene og . Siden holder uligheden . (fire) $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\in A\bigcup {B}}{{S}_{i}}\bigcup {{S}_{1}}}$ $\rho \left(X\bigcup {Y}\right)\geq \left|A\bigcup {B}\right|+1$

På grund af det faktum , at vi har . (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|$

Ved at bruge egenskaben til semimodularitet af rangfunktionen [7] får vi efter tilføjelse af (4) og (5): . (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$

Ulighed (6) modsiger ulighed (3). Påstanden er blevet bevist. $\vartriangle$

Vi vil anvende proceduren fra erklæringen til vi har singleton sæt tilbage . I dette tilfælde er rangen af deres fagforening lig med . Derfor er der den ønskede uafhængige tværgående. $m$ $\left\{{{t}_{1}}\right\},\ \left\{{{t}_{2}}\right\}\ \ldots ,\ \left\{{{ t}_{m}}\right\}$ $T=\left\{{{t}_{1}},\ {{t}_{2}},\ \ldots ,\ {{t}_{m}}\right\}$ $m$ $T$ $\square$

Konsekvens

Lad være en matroid . En sekvens af ikke-tomme undermængder af et sæt har en uafhængig delvis tværgående kardinalitet , hvis og kun hvis foreningen af nogen undermængder fra denne sekvens indeholder en uafhængig undermængde af kardinalitet mindst , dvs. [otte] $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.$

Generelle transversaler

Kriteriet for eksistensen af en selvstændig tværgående gør det muligt at opnå nødvendige og tilstrækkelige betingelser for eksistensen af en fælles tværgående for to forskellige systemer af delmængder af samme sæt.

Sætning

To familier og ikke-tomme delmængder af en endelig mængde har en fælles transversal, hvis og kun hvis uligheden [8] gælder for nogen delmængder og mængder . $S=(S_{1},S_{2},...,S_{m})$ $R=(R_{1},R_{2},...,R_{m})$ $E$ $EN$ $B$ ${\displaystyle {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.$

Et teorem om antallet af distinkte transversaler af en familie af delmængder

Lad være en familie af delmængder af nogle sæt . Lad matrixen være kendt . $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{aligned }}\ret.$

Så er antallet af forskellige transversaler af familien lig med matrixens permanente . [9] $S$ $EN$

Links til andre sektioner og applikation

I optimeringsteori og grafteori kan det at finde en fælles transversal reduceres til at finde det maksimale flow i netværket [8] .

I datalogi bruges beregningen af transversaler i flere anvendelsesområder, og inputfamilien af sæt beskrives ofte som en hypergraf .

Elementerne, der ligger på hoveddiagonalen af en vilkårlig kvadratisk matrix , er også en tværgående af en familie af rækker (søjler). Udvælgelsen af en sådan transversal bruges til at bevise en række resultater i sandsynlighedsteori og algebra .

Brugen af transversaler og belægninger fra dem ligger til grund for Euler-Parker-metoden til at søge efter ortogonale latinske firkanter til en given latinsk firkant.

Generalisering

Begrebet transversal kan generaliseres.

Lad der være en sekvens af positive heltal . Så vil den tværgående af familien være familien af delmængder af sættet, for hvilke følgende betingelser er opfyldt: $(k_{1},k_{2},\ldots ,k_{m})$ $(k_{1},k_{2},\ldots ,k_{m})$ $S$ $P=(P_{1},P_{2},\ldots ,P_{m})$ $E$

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

Noter

↑ John Mackintosh HowieGrundlæggende om semigruppeteori . - Oxford University Press , 1995. - S. 63. - ISBN 978-0-19-851194-6 .
↑ Clive Reis. Abstrakt algebra : en introduktion til grupper, ringe og felter . - World Scientific , 2011. - S. 57. - ISBN 978-981-4335-64-5 .
↑ Bruno Courcelle; Joost Engelfriet. Grafstruktur og monadisk andenordenslogik: En sprogteoretisk tilgang . - Cambridge University Press , 2012. - S. 95. - ISBN 978-1-139-64400-6 .
↑ Roberts, Tesman, 2009 , s. 692.
↑ Brualdi, 2010 , s. 322.
↑ Kapitonova Yu. V., Krivoy S. L., Letichevsky A. A. Forelæsninger om diskret matematik. - St. Petersburg, BHV-Petersburg, 2004. - isbn 5-94157-546-7. - c. 529
↑ Rangfunktion, semimodularitet . ITMO Wiki Abstracts . Dato for adgang: 6. december 2019. Arkiveret fra originalen 6. december 2019. (ubestemt)
↑ 1 2 3 Al højere matematik: Lærebog. T.7., 2006
↑ V.N. Sachkov, 1982

Litteratur

M.L. Krasnov, A.I. Kiselev, G.I. Makarenko, E.V. Shikin, V.I. Zalyapin, A.Yu. Evnin. Al højere matematik: lærebog. - M . : KomKniga, 2006. - T. 7. - 208 s. — ISBN 5-484-00521-3 .

M. Hall. Kapitel nr. 5 "Systemer af forskellige repræsentanter" // Combinatorics = Combinatorial Theory / overs. fra engelsk. S. A. Shirokova; udg. A. O. Gelfond og V. E. Tarakanov. - M . : Mir, 1970. - S. 65 -78. — 424 s.
V.N. Sachkov. Introduktion til kombinatoriske metoder i diskret matematik. - M . : Videnskab. Ch. udg. Fysisk.-Matematik. lit., 1982. - 384 s.

M. Swami, K. Thulasiraman. Kapitel nr. 8.6 "Matching i todelte grafer" // Grafer, netværk og algoritmer = Grafer, netværk og algoritmer / transl. fra engelsk. M. V. Gorbatova, V. L. Torkhova, S. A. Frolov, V. N. Chetverikov; udg. V. A. Gorbatov. - M .: Mir, 1984. - S. 165-166. — 455 s. — 11.000 eksemplarer.
V. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, R. I. Tyshkevich. Forelæsninger om grafteori. - M . : Nauka , 1990. - S. 87-92. — 384 s. — ISBN 5-02-013992-0 .
N. I. Kostyukova. Grafer og deres applikationer . — Foredrag nr. 16: Theory of transversals. Hentet: 29. juli 2009. (ubestemt)
Alexander Schrijver. Kapitel 22 "Tværgående", kapitel 23 "Fælles tværgående" // Kombinatorisk optimering . - Springer, 2003. - S. 378-409. — 1800 s. — ISBN 978-3540443896 .
Roberts F., Tesman B. Applied Combinatorics. - Boca Raton: CRC Press, 2009. - ISBN 978-1-4200-9982-9 .
Brualdi R. Indledende kombinatorik. - Upper Saddle River, NJ: Prentice Hall, 2010. - ISBN 0-13-602040-2 .