Tvärgående

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 27 september 2018; kontroller kräver 10 redigeringar . Ej att förväxla med Triangle transversal .

Transversal ( system av olika representanter ) är ett begrepp från mängdläran , vilket är ganska viktigt för all diskret matematik . Det finns också i logik och linjär algebra .

I matematik , för en given familj av uppsättningar , är en transversal (även kallad ett tvärsnitt i viss utländsk litteratur [1] [2] [3] ) en uppsättning som innehåller exakt ett element från varje uppsättning från . När uppsättningar från inte korsar varandra, motsvarar varje element i transversalen exakt ett element (uppsättningen som den är medlem av). Om originaluppsättningarna skär varandra, finns det två sätt att definiera transversalen. Den första varianten imiterar situationen när mängderna inte skär varandra, den består i förekomsten av en bijektion från transversalen till , så att för varje i transversalen får vi att den är mappad till något element . I det här fallet kallas transversalen också ett system av distinkta representanter. En annan, mindre använd variant kräver inte ett en-till-en-förhållande mellan elementen i transversalen och uppsättningarna från . I denna situation är elementen i det representativa systemet inte nödvändigtvis distinkta [4] [5] . Följande är strikta definitioner av de vanligaste tillvägagångssätten. $S$ $S$ $S$ $S$ $\varphi$ $S$ $x$ $x$ $\varphi(x)$ $S$

Definitioner

1) Låt vara lite ställd. Låt vara uppsättningens booleska , dvs. uppsättningen av alla delmängder av uppsättningen . Låt vara några exempel från . Elementen i detta urval kan upprepas. $X$ $2^{X}$ $X$ $X$ $(X_{1},X_{2},\ldots,X_{n})$ $2^{X}$

En vektor av mängdelement kallas en familjetransversal om följande relationer gäller: $(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) Beteckna som en finit icke-tom mängd , och som en familj av dess delmängder, det vill säga en sekvens av icke-tomma delmängder av längd . $E$ $S=(S_{1},S_{2},\ldots ,S_{m})$ $E$ $m$

En transversal av en familj är en delmängd för vilken det finns en bijektion och för vilken villkoret är uppfyllt . $S$ $T\subseteq E$ $\varphi \colon T\rightarrow \{1,2,\ldots ,m\}$ $\forall t\in T$ ${\displaystyle t\in S_{\varphi (t)))$

Med andra ord, för elementen i transversalen finns det en sådan uppräkning under vilken för . $t_{i}\in S_{i}$ $i\in \{1,2,\ldots ,m\}$

Eftersom det är en uppsättning är alla dess element olika, därav namnet "system av olika representanter". $T$

Exempel

1) Låt en uppsättning och en familj av delmängder ges . Ett exempel på en transversal för en sådan familj är , där . $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\in S_{2},2\in S_{4},3\in S_{3},4\in S_{1))$

2) I någon institution finns provisioner. Det krävs från sammansättningen av varje kommission att utse sina ordförande så att ingen person leder mer än en kommission. Här kommer de tvärgående kommissionerna att sammansättas av deras ordförande. $m$

3) I gruppteorin, för en given undergrupp av en grupp, är en höger (respektive vänster) transversal en mängd som innehåller exakt ett element från varje höger (respektive vänster) coset . I det här fallet skär "uppsättningarna" (cosets) inte varandra, d.v.s. cosets bildar en uppdelning av gruppen. $H$ $G$ $H$

4) Som ett specialfall av det föregående exemplet, med hänsyn till den direkta produkten av grupper , får vi som är en tvärgående för cosets . $G=H\ gånger K$ $H$ $K$

5) Eftersom varje ekvivalensrelation på en godtycklig mängd leder till en partition, leder valet av valfri representant från varje ekvivalensklass till en transversal.

6) Ett annat fall av partitionsbaserad transversal uppstår när man betraktar ekvivalensrelationen känd som den (mängd-teoretiska) kärnan för en funktion definierad för en funktion med domän X som dess partition som delar upp domänen f i ekvivalensklasser så att alla element i klassen har samma bild under mappningen f . Om f är injektiv, finns det bara en transversal . För ett valfritt injektivt f orsakar korrigering av det tvärgående T in en en-till-en-överensstämmelse mellan T och bilden av f , nedan betecknad som . Därför är funktionen väl definierad av egenskapen att för alla z : , där x är det enda elementet i T så att ; dessutom kan g utökas (inte nödvändigtvis unikt) så att det definieras över hela området f genom att välja godtyckliga värden för g(z) när z är utanför bilden f . Det är en enkel beräkning att se att g definierad på detta sätt har egenskapen , vilket är ett bevis (när domänen och intervallet för f är samma mängd) att en komplett transformationssemigrupp är en vanlig semigrupp. Mappningen fungerar som ett (inte nödvändigtvis det enda) kvasi-inverst element för f ; i semigruppteorin är detta helt enkelt det omvända elementet. Observera dock att för ett godtyckligt g med ovanstående egenskap kanske den "dubbla" ekvationen inte håller, men om vi betecknar , så är f kvasi-omvändningen av h , det vill säga . $f$ $\operatörsnamn {ker} f:=\left\{\,\left\{\,y\in X\mid f(x)=f(y)\,\right\}\mid x\in X \,\höger\}$ $\operatörsnamn {ker} f$ $\operatörsnamn {ker} f$ $\operatorname {Im} f$ $g:(\operatörsnamn {Im} f)\to T$ $\operatörsnamn {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$

Existens

I praktiken är det oftare viktigt att svara på frågan om det finns en transversal för en viss familj. En något humoristisk formulering av denna fråga är bröllopsproblemet:

Låt det finnas någon uppsättning unga män och någon uppsättning flickor. Dessutom är varje ung man från den första uppsättningen bekant med flera tjejer från den andra. Det krävs att gifta sig med alla unga män så att var och en kombineras i ett monogamt äktenskap med en tjej han känner.

Detta problem har en lösning om det finns en transversal för en familj av uppsättningar bildade av flickor som känner en viss pojke.

En rigorös lösning på problemet med existensen av en transversal är Halls teorem för transversaler, liksom dess generalisering, Rados teorem.

Halls teorem för transversaler

Låt vara en icke-tom finit mängd och vara en familj av inte nödvändigtvis olika icke-tomma delmängder av den. I det här fallet har den en tvärgående om och endast om, för godtyckliga delmängder , deras förening innehåller åtminstone olika element [6] . $E$ $S=\left\{S_{1},S_{2},...,S_{m}\right\}$ $S$ $k$ ${\displaystyle S_{i))$ $k$ $(k=1,2,...,m)$

Partiell transversal

Om det är en injektion kallas transversalen partiell . Partiella transversaler av en familj är transversaler av dess underfamiljer. Varje delmängd av en transversal är en partiell transversal. $\varphi$ $S$

Oberoende transversaler

Låt någon matroid ges på uppsättningen Låt vara en familj av delmängder av uppsättningen . En oberoende transversal för är en transversal som är en oberoende uppsättning i betydelsen av den angivna matroiden. I synnerhet, om en matroid är diskret, är varje transversal oberoende. Följande sats ger ett kriterium för existensen av en oberoende transversal. $E$ $S=(S_{1},S_{2},...,S_{m})$ $E$ $S$

R. Rados teorem

Låt vara en matroid . En sekvens av icke-tomma delmängder av en mängd har en oberoende transversal om och endast om föreningen av några delmängder från denna sekvens innehåller en oberoende mängd med åtminstone element, där ett godtyckligt naturligt tal inte överstiger . $M=(E,J)$ $S=(S_{1},S_{2},\ldots ,S_{m})$ $E$ $k$ $k$ $k$ $m$

Bevis:

$\square$ Det är bekvämt att formulera villkoret för satsen med hjälp av begreppet rang av en mängd (den största kardinalitet av en oberoende delmängd):

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

Behöver. Om det finns en oberoende transversal, har dess skärning med mängden element , varifrån . $\bigcup \limits _{i\in A}{{S}_{i}}$ $\left|A\right|$ $\rho \left(\bigcup \limits _{i\in A}{{S}_{i}}\right)\geq \left|A\right|$

Lämplighet. Låt oss först bevisa följande påstående:

Påstående. Om en viss uppsättning (till exempel ) innehåller minst två element, kan ett element tas bort från denna uppsättning utan att bryta mot villkor (1). ${\displaystyle S_{1))$

$\vartriangle$ Tvärtom: låt och, oavsett vilket element som tas bort från , kommer villkor (1) inte att vara uppfyllt. Ta två element och från uppsättningen . För dem finns det sådana uppsättningar av index och , där , det $\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$ och . (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$

Låt oss säga: , . Vi kommer att skriva om relationer (2) i formen: , varifrån . (3) $X=\bigcup \limits _{i\in A}{{S}_{i}}\bigcup {\left({{S}_{1}}\backslash \left\{x\right\ }\höger)}$ $Y=\bigcup \limits _{i\in B}{{S}_{i}}\bigcup {\left({{S}_{1}}\backslash \left\{y\right\ }\höger)}$ $\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|$

Med hjälp av villkor (1) uppskattar vi underifrån raden av fackföreningen och skärningspunkten mellan uppsättningarna och . Sedan håller ojämlikheten . (fyra) $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 av det faktum att 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|$

Genom att använda egenskapen för semimodularitet hos rangfunktionen [7] får vi: . (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$

Ojämlikhet (6) motsäger ojämlikhet (3). Påståendet har bevisats. $\vartriangle$

Vi kommer att tillämpa proceduren från uttalandet tills vi har singleton set kvar . I det här fallet är rangen för deras fackförening lika med . Följaktligen finns den önskade oberoende 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

Låt vara en matroid . En sekvens av icke-tomma delmängder av en uppsättning har en oberoende partiell tvärgående kardinalitet om och endast om föreningen av några delmängder från denna sekvens innehåller en oberoende delmängd av kardinalitet åtminstone , dvs. [åtta] $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.$

Allmänna transversaler

Kriteriet för förekomsten av en oberoende transversal gör det möjligt att erhålla nödvändiga och tillräckliga förutsättningar för existensen av en gemensam transversal för två olika system av delmängder av samma uppsättning.

Sats

Två familjer och icke-tomma delmängder av en finit mängd har en gemensam transversal om och endast om olikheten [8] gäller för några delmängder och mängder . $S=(S_{1},S_{2},...,S_{m})$ $R=(R_{1},R_{2},...,R_{m})$ $E$ $A$ $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.$

Ett teorem om antalet distinkta transversaler av en familj av delmängder

Låt vara en familj av delmängder av någon uppsättning . Låt matrisen vara känd . $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 }}\höger.$

Då är antalet olika transversaler av familjen lika med matrisens permanenta . [9] $S$ $A$

Länkar till andra avsnitt och program

Inom optimeringsteori och grafteori kan hitta en gemensam transversal reduceras till att hitta det maximala flödet i nätverket [8] .

Inom datavetenskap används beräkningen av transversaler i flera tillämpningsområden, och ingångsfamiljen av uppsättningar beskrivs ofta som en hypergraf .

Elementen som ligger på huvuddiagonalen av en godtycklig kvadratisk matris är också en transversal av en familj av rader (kolumner). Valet av en sådan transversal används för att bevisa ett antal resultat inom sannolikhetsteori och algebra .

Användningen av transversaler och beläggningar från dem ligger till grund för Euler-Parker-metoden att söka efter ortogonala latinska kvadrater till en given latinsk kvadrat.

Generalisering

Begreppet transversal kan generaliseras.

Låt det finnas en sekvens av positiva heltal . Då -transversal av familjen kommer att vara familjen av delmängder av uppsättningen för vilka följande villkor är uppfyllda: $(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))$ för ; $i\in \{1,2,\ldots ,m\}$
$|P_{i}|=k_{i}$ ;
$P_{i}\cap P_{j}=\varnothing ,i\neq j$ .

Anteckningar

↑ John Mackintosh HowieFundamentals of Semigroup Theory . - Oxford University Press , 1995. - P. 63. - ISBN 978-0-19-851194-6 .
↑ Clive Reis. Abstrakt Algebra : En introduktion till grupper, ringar och fält . - World Scientific , 2011. - P. 57. - ISBN 978-981-4335-64-5 .
↑ Bruno Courcelle; Joost Engelfriet. Grafstruktur och monadisk andra ordningens logik: ett språkteoretiskt tillvägagångssätt . - Cambridge University Press , 2012. - S. 95. - ISBN 978-1-139-64400-6 .
↑ Roberts, Tesman, 2009 , sid. 692.
↑ Brualdi, 2010 , sid. 322.
↑ Kapitonova Yu. V., Krivoy S. L., Letichevsky A. A. Föreläsningar om diskret matematik. - St. Petersburg, BHV-Petersburg, 2004. - isbn 5-94157-546-7. - c. 529
↑ Rangfunktion, semimodularitet . ITMO Wiki Abstracts . Datum för åtkomst: 6 december 2019. Arkiverad från originalet 6 december 2019. (obestämd)
↑ 1 2 3 All högre matematik: Lärobok. 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. All högre matematik: lärobok. - M . : KomKniga, 2006. - T. 7. - 208 sid. — ISBN 5-484-00521-3 .

M. Hall. Kapitel nr 5 "System av olika representanter" // Combinatorics = Combinatorial Theory / transl. från engelska. S. A. Shirokova; ed. A.O. Gelfond och V.E. Tarakanov. - M . : Mir, 1970. - S. 65 -78. — 424 sid.
V.N. Sachkov. Introduktion till kombinatoriska metoder för diskret matematik. - M . : Vetenskap. Ch. ed. Phys.-Matte. lit., 1982. - 384 sid.

M. Swami, K. Thulasiraman. Kapitel nr 8.6 "Matchning i tvådelade grafer" // Grafer, nätverk och algoritmer = Grafer, nätverk och algoritmer / transl. från engelska. M.V. Gorbatova, V.L. Torkhova, S.A. Frolov, V.N. Chetverikov; ed. V. A. Gorbatova. - M .: Mir, 1984. - S. 165-166. — 455 sid. — 11 000 exemplar.
V. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, R. I. Tyshkevich. Föreläsningar om grafteori. - M . : Nauka , 1990. - S. 87-92. — 384 sid. — ISBN 5-02-013992-0 .
N. I. Kostyukova. Grafer och deras tillämpningar . — Föreläsning nr 16: Theory of transversals. Hämtad: 29 juli 2009. (obestämd)
Alexander Schrijver. Kapitel 22 "Transversals", kapitel 23 "Common transversals" // Kombinatorisk optimering . - Springer, 2003. - S. 378-409. — 1800 sid. — ISBN 978-3540443896 .
Roberts F., Tesman B. Applied Combinatorics. - Boca Raton: CRC Press, 2009. - ISBN 978-1-4200-9982-9 .
Brualdi R. Inledande kombinatorik. - Upper Saddle River, NJ: Prentice Hall, 2010. - ISBN 0-13-602040-2 .