Poikittainen

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 27. syyskuuta 2018 tarkistetusta versiosta . tarkastukset vaativat 10 muokkausta . Ei pidä sekoittaa kolmioon poikittainen .

Transversaali ( eri edustajien järjestelmä ) on joukkoteorian käsite , joka on varsin tärkeä kaikelle diskreetille matematiikalle . Se on olemassa myös logiikassa ja lineaarisessa algebrassa .

Matematiikassa tietylle joukkoperheelle transversaali ( joissakin ulkomaisissa kirjallisuuksissa myös poikkileikkaukseksi [1] [2] [3] ) on joukko , joka sisältää täsmälleen yhden alkion jokaisesta joukosta . Kun joukot kohteesta eivät leikkaa toisiaan, jokainen transversaalin elementti vastaa täsmälleen yhtä elementtiä (joukkoa, jonka jäsen se on). Jos alkuperäiset joukot leikkaavat, on kaksi tapaa määritellä poikittaissuunta. Ensimmäinen variantti jäljittelee tilannetta, jossa joukot eivät leikkaa toisiaan, se koostuu bijektiosta poikittaispisteestä kohtaan , jolloin jokaiselle transversaalissa saadaan, että se on kartoitettu johonkin elementtiin . Tässä tapauksessa poikittaista kutsutaan myös erillisten edustajien järjestelmäksi. Toinen, vähemmän käytetty muunnos ei vaadi yksi-yhteen-suhdetta poikittaiselementtien ja joukosta alkaen . Tässä tilanteessa edustavan järjestelmän elementit eivät välttämättä eroa toisistaan [4] [5] . Seuraavassa on tiukat määritelmät yleisimmistä lähestymistavoista. $S$ $S$ $S$ $S$ $\varphi$ $S$ $x$ $x$ $\varphi(x)$ $S$

Määritelmät

1) Olkoon joukko. Olkoon joukon Boolen arvo , ts. joukon kaikkien osajoukkojen joukko . Olkoon jokin näyte . Tämän valinnan elementit voidaan toistaa. $X$ $2^{X}$ $X$ $X$ $(X_{1},X_{2},\ldots ,X_{n})$ $2^{X}$

Joukkoelementtien vektoria kutsutaan perhetransversaaliksi , jos seuraavat suhteet pätevät: $(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) Merkitään äärellisenä ei-tyhjänä joukkona ja sen osajoukkojen perheenä, eli ei-tyhjien pituisten osajoukkojen sarjana . $E$ $S=(S_{1},S_{2},\ldots ,S_{m})$ $E$ $m$

Perheen poikittainen on osajoukko , jolle on olemassa bijektio ja jonka ehto täyttyy . $S$ $T\subseteq E$ $\varphi \colon T\rightarrow \{1,2,\ldots ,m\}$ $\forall t\in T$ ${\displaystyle t\in S_{\varphi (t)))$

Toisin sanoen poikittaisen elementtien osalta on olemassa sellainen luettelo, jonka mukaan . $t_{i}\in S_{i}$ $i\in \{1,2,\ldots ,m\}$

Koska on joukko, niin kaikki sen elementit ovat erilaisia, tästä syystä nimi " eri edustajien järjestelmä". $T$

Esimerkkejä

1) Olkoon joukko ja osajoukkojen perhe annettu . Esimerkki tällaisen perheen poikittaissuunnasta on , jossa . $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) Joissakin laitoksissa on palkkioita. Kunkin toimikunnan kokoonpanon on nimettävä puheenjohtajansa, jotta kukaan ei johda useampaa kuin yhtä valiokuntaa. Tässä valiokuntien poikittaiset kokoonpanot koostuvat niiden puheenjohtajista. $m$

3) Ryhmäteoriassa tietylle ryhmän alaryhmälle oikea (vastaavasti vasen) transversaali on joukko, joka sisältää täsmälleen yhden elementin jokaisesta oikeasta (vastaavasti vasemmasta) kosetista . Tässä tapauksessa "joukot" (cosetit) eivät leikkaa keskenään, ts. cosetit muodostavat osion ryhmästä. $H$ $G$ $H$

4) Edellisen esimerkin erikoistapauksena, kun otetaan huomioon ryhmien suora tulo , saadaan mikä on poikittaisarvo koseteille . $G=H\times K$ $H$ $K$

5) Koska mikä tahansa ekvivalenssirelaatio mielivaltaisessa joukossa johtaa osioon, minkä tahansa edustajan valinta kustakin ekvivalenssiluokasta johtaa transversaaliin.

6) Toinen osiopohjaisen transversaalin tapaus syntyy, kun tarkastellaan funktion (joukkoteoreettisena) ytimenä tunnettua ekvivalenssisuhdetta, joka on määritelty funktiolle , jonka toimialue X on sen osio , joka jakaa toimialueen f ekvivalenssiluokkiin siten, että kaikki elementit luokassa on sama kuva kartoituksen f alla . Jos f on injektiivinen, on olemassa vain yksi poikittainen . Valinnaisesti injektiiviselle f :lle poikittaisen T in :n korjaaminen aiheuttaa yksi-yhteen vastaavuuden T :n ja f : n kuvan välillä , joka on merkitty alla . Siksi funktion määrittää hyvin se ominaisuus, että kaikille z : , missä x on T :n ainoa alkio , joka ; Lisäksi g : tä voidaan laajentaa (ei välttämättä yksiselitteisesti) niin, että se määritellään koko f :n alueelle valitsemalla mielivaltaiset arvot g(z) :lle, kun z on kuvan f ulkopuolella . On yksinkertainen laskelma nähdä, että näin määritellyllä g :llä on ominaisuus , joka on todiste (kun toimialue ja f :n alue ovat sama joukko), että täydellinen muunnospuoliryhmä on säännöllinen puoliryhmä. Kuvaus toimii (ei välttämättä ainoana) kvasi-inversioelementtinä f :lle ; puoliryhmäteoriassa tämä on yksinkertaisesti käänteiselementti. Huomaa kuitenkin, että mielivaltaiselle g:lle, jolla on yllä oleva ominaisuus, "kaksois"-yhtälö ei välttämättä päde, mutta jos merkitsemme , niin f on h :n kvasikäänteinen , eli . $f$ $\operaattorin nimi {ker} f:=\left\{\,\left\{\,y\in X\mid f(x)=f(y)\,\right\}\mid x\in X \,\oikea\}$ $\operaattorin nimi {ker} f$ $\operaattorin nimi {ker} f$ $\operaattorinimi {Im} f$ $g:(\operaattorin nimi {Im} f)\to T$ $\operaattorinimi {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$

Olemassaolo

Käytännössä on useammin tärkeää vastata kysymykseen, onko tietylle perheelle poikittainen olemassa. Hieman humoristinen muotoilu tälle kysymykselle on hääongelma:

Olkoon joukko nuoria miehiä ja joitakin tyttöjä. Lisäksi jokainen ensimmäisen sarjan nuori mies tuntee useita tyttöjä toisesta sarjasta. Kaikki nuoret miehet on mentävä naimisiin niin, että jokainen yhdistyy yksiavioiseen avioliittoon tuntemansa tytön kanssa.

Tähän ongelmaan on ratkaisu, jos tietyn pojan tuntevista tytöistä muodostetulle sarjaperheelle on olemassa poikittaissuunta.

Tiukka ratkaisu transversaalin olemassaolon ongelmaan on Hallin lause transversaaleille sekä sen yleistys, Radon lause.

Hallin lause transversaaleille

Antaa olla ei-tyhjä äärellinen joukko ja olla perhe ei välttämättä erilaisia ei-tyhjiä osajoukkoja. Tässä tapauksessa sillä on transversaali silloin ja vain, jos mielivaltaisten osajoukkojen liitto sisältää ainakin eri elementtejä [6] . $E$ ${\displaystyle S=\left\{S_{1},S_{2},...,S_{m}\oikea\))$ $S$ $k$ ${\displaystyle S_{i))$ $k$ ${\näyttötyyli (k=1,2,...,m)}$

Osittainen poikkisuuntainen

Jos on injektio , niin poikittaista kutsutaan osittaiseksi . Suvun osittaiset poikittaissuuntaukset ovat sen alaperheiden poikittaissuuntauksia. Mikä tahansa transversaalin osajoukko on osittainen poikkisuuntainen. $\varphi$ $S$

Itsenäiset transversaalit

Olkoon joukossa jokin matroidi , joka on joukon osajoukkojen perhe . Itsenäinen transversaali for on transversaali, joka on riippumaton joukko määritetyn matroidin merkityksessä. Erityisesti, jos matroidi on diskreetti, mikä tahansa transversaali on riippumaton. Seuraava lause antaa kriteerin itsenäisen transversaalin olemassaololle. $E$ $S=(S_{1},S_{2},...,S_{m})$ $E$ $S$

R. Radon lause

Olkoon matroidi . _ Joukon ei-tyhjien osajoukkojen sekvenssillä on itsenäinen poikittaisluku silloin ja vain, jos minkä tahansa tämän sekvenssin osajoukkojen liitto sisältää itsenäisen joukon, jossa on vähintään alkioita, missä on mielivaltainen luonnollinen luku, joka ei ylitä . $M=(E,J)$ $S=(S_{1},S_{2},\ldots ,S_{m})$ $E$ $k$ $k$ $k$ $m$

Todiste:

${\näyttötyyli \neliö }$ Lauseen ehto on kätevää muotoilla käyttämällä joukon asteen käsitettä (riippumattoman osajoukon suurin kardinaliteetti):

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

Tarve. Jos on itsenäinen poikittainen, niin sen leikkauspisteessä joukon kanssa on elementtejä, joista . $\bigcup \limits _{i\in A}{{S}_{i}}$ $\left|A\right|$ $\rho \left(\bigcup \limits _{i\in A}{{S}_{i}}\right)\geq \left|A\right|$

Riittävyys. Todistakaamme ensin seuraava väite:

lausunto. Jos tietty joukko (esimerkiksi ) sisältää vähintään kaksi elementtiä, yksi elementti voidaan poistaa tästä joukosta rikkomatta ehtoa (1). ${\displaystyle S_{1))$

$\vartriangle$ Päinvastoin: anna ja, riippumatta siitä, mikä elementti poistetaan , ehto (1) ei täyty. Ota kaksi elementtiä ja joukosta . Heille on olemassa sellaisia indeksijoukkoja ja , missä , että $\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$ ja . (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$

Laitetaan: , . Kirjoitetaan suhteet (2) uudelleen muotoon: , mistä . (3) $X=\bigcup \limits _{i\in A}{{S}_{i}}\bigcup {\left({{S}_{1}}\backslash \left\{x\right\ }\oikea)}$ $Y=\bigcup \limits _{i\in B}{{S}_{i}}\bigcup {\left({{S}_{1}}\backslash \left\{y\right\ }\oikea)}$ $\rho \left(X\right)\leq \left|A\right|;\ \rho \left(Y\right)\leq \left|B\oikea|$ $\rho \left(X\right)+\ \rho \left(Y\right)\leq \left|A\right|+\left|B\right|$

Käyttämällä ehtoa (1), arvioimme alhaalta riveissä unionin ja leikkauspisteen asettaa ja . Koska , epätasa -arvo pätee . (neljä) $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$

Johtuen siitä, että meillä on . (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|$

Käyttämällä rank-funktion [7] puolimodulaarisuuden ominaisuutta , kun on lisätty (4) ja (5), saadaan: . (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$

Epätasa-arvo (6) on ristiriidassa eriarvoisuuden (3) kanssa. Väite on todistettu. $\vartriangle$

Käytämme menettelyä lauseesta, kunnes meillä on jäljellä singleton joukkoja . Tässä tapauksessa heidän ammattiliittonsa arvo on yhtä suuri kuin . Siten on haluttu itsenäinen poikittaissuunta. $m$ $\left\{{{t}_{1}}\right\},\ \left\{{{t}_{2}}\right\}\ \ldots ,\ \left\{{{ t}_{m}}\oikea\}$ $T=\left\{{{t}_{1}},\ {{t}_{2}},\ \ldots ,\ {{t}_{m}}\right\}$ $m$ $T$ ${\näyttötyyli \neliö }$

Seuraus

Olkoon matroidi . _ Joukon ei-tyhjien osajoukkojen sekvenssillä on itsenäinen kardinaalisuuden osittainen poikittaissuunta, jos ja vain, jos minkä tahansa tämän sekvenssin osajoukkojen liitto sisältää riippumattoman kardinaalisuuden osajoukon , ts. [kahdeksan] $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.$

Yleiset transversaalit

Itsenäisen transversaalin olemassaolon kriteeri mahdollistaa välttämättömät ja riittävät edellytykset yhteisen transversaalin olemassaololle saman joukon kahdelle eri järjestelmälle.

Lause

Kahdella perheellä ja äärellisen joukon ei-tyhjillä osajoukoilla on yhteinen transversaali silloin ja vain, jos epäyhtälö [8] pätee mille tahansa osajoukolle ja joukolle . $S=(S_{1},S_{2},...,S_{m})$ $R=(R_{1},R_{2},...,R_{m})$ $E$ $A$ $B$ ${\näyttötyyli {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.$

Lause alajoukkojen perheen erillisten poikkisuuntausten lukumäärästä

Antaa olla perheen osajoukkoja joidenkin asetettu . Olkoon matriisi tiedossa . $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{tasattu }}\oikea.$

Tällöin perheen eri transversaalien lukumäärä on yhtä suuri kuin matriisin pysyvä . [9] $S$ $A$

Linkit muihin osiin ja sovelluksiin

Optimointiteoriassa ja graafiteoriassa yhteisen transversaalin löytäminen voidaan pelkistää verkon maksimivirtauksen löytämiseen [8] .

Tietojenkäsittelytieteessä transversaalien laskentaa käytetään useilla sovellusalueilla ja joukkojen syöteperhettä kuvataan usein hypergraafina .

Satunnaisen neliömatriisin päälävistäjällä sijaitsevat elementit ovat myös rivien (sarakkeiden) perheen poikkisuuntaisia elementtejä. Tällaisen transversaalin valintaa käytetään useiden tulosten todistamiseen todennäköisyysteoriassa ja algebrassa .

Transversaalien ja niiden peitteiden käyttö perustuu Euler-Parkerin menetelmään etsiä kohtisuoraa latinalaista neliötä tiettyyn latinalliseen neliöön.

Yleistys

Poikittainen käsite voidaan yleistää.

Olkoon positiivisten kokonaislukujen sarja . Tällöin perheen -transversaali on joukon alajoukkojen perhe, jolle seuraavat ehdot täyttyvät: $(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))$ varten ; $i\in \{1,2,\ldots ,m\}$
$|P_{i}|=k_{i}$ ;
$P_{i}\cap P_{j}=\varnothing ,i\neq j$ .

Muistiinpanot

↑ John Mackintosh HowiePuoliryhmäteorian perusteet . - Oxford University Press , 1995. - s. 63. - ISBN 978-0-19-851194-6 .
↑ Clive Reis. Abstrakti algebra : Johdatus ryhmiin, renkaisiin ja kenttiin . - World Scientific , 2011. - S. 57. - ISBN 978-981-4335-64-5 .
↑ Bruno Courcelle; Joost Engelfriet. Graafirakenne ja monadinen toisen asteen logiikka: kieliteoreettinen lähestymistapa . - 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. Diskreetin matematiikan luentoja. - Pietari, BHV-Petersburg, 2004. - isbn 5-94157-546-7. - c. 529
↑ Rank-funktio, semimodulaarisuus . ITMO Wiki Abstracts . Käyttöpäivä: 6. joulukuuta 2019. Arkistoitu alkuperäisestä 6. joulukuuta 2019. (määrätön)
↑ 1 2 3 Kaikki korkeampi matematiikka: Oppikirja. T.7., 2006
↑ V. N. Sachkov, 1982

Kirjallisuus

M.L. Krasnov, A.I. Kiselev, G.I. Makarenko, E.V. Shikin, V.I. Zalyapin, A. Yu. Evnin. Kaikki korkeampi matematiikka: Oppikirja. - M . : KomKniga, 2006. - T. 7. - 208 s. — ISBN 5-484-00521-3 .

M. Hall. Luku nro 5 "Eri edustajien järjestelmät" // Kombinatoriikka = Combinatorial Theory / käännös. englannista. S. A. Shirokova; toim. A. O. Gelfond ja V. E. Tarakanov. - M .: Mir, 1970. - S. 65-78 . — 424 s.
V. N. Sachkov. Johdatus diskreetin matematiikan kombinatorisiin menetelmiin. - M . : Tiede. Ch. toim. Fys.-Math. lit., 1982. - 384 s.

M. Swami, K. Thulasiraman. Luku nro 8.6 "Sovitus bipartite graphs" // Grafit, verkot ja algoritmit = Graphs, Networks ja Algorithms / käännös. englannista. M. V. Gorbatova, V. L. Torkhova, S. A. Frolov, V. N. Chetverikov; toim. V. A. Gorbatov. - M .: Mir, 1984. - S. 165-166. — 455 s. – 11 000 kappaletta.
V. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, R. I. Tyshkevich. Graafiteorian luentoja. - M .: Nauka , 1990. - S. 87-92. — 384 s. — ISBN 5-02-013992-0 .
N. I. Kostyukova. Kaaviot ja niiden sovellukset . — Luento nro 16: Transversaalien teoria. Haettu: 29. heinäkuuta 2009. (määrätön)
Alexander Schrijver. Luku 22 "Transversaalit", luku 23 "Yleiset transversaalit" // Kombinatorinen optimointi . - Springer, 2003. - S. 378-409. - 1800 s. — ISBN 978-3540443896 .
Roberts F., Tesman B. Applied Combinatoriics. - Boca Raton: CRC Press, 2009. - ISBN 978-1-4200-9982-9 .
Brualdi R. Introductory Combinatoriics. - Upper Saddle River, NJ: Prentice Hall, 2010. - ISBN 0-13-602040-2 .