Transzverzális

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2018. szeptember 27-én felülvizsgált verziótól ; az ellenőrzésekhez 10 szerkesztés szükséges . Nem tévesztendő össze a keresztirányú háromszöggel .

A transzverzális ( különböző reprezentánsok rendszere ) egy halmazelméleti fogalom , amely nagyon fontos minden diszkrét matematika számára . Létezik a logikában és a lineáris algebrában is .

A matematikában egy adott halmazcsalád esetében a transzverzális ( egyes külföldi szakirodalomban keresztmetszetnek is nevezik [1] [2] [3] ) olyan halmaz , amely a -ból származó minden halmazból pontosan egy elemet tartalmaz . Ha a halmazok nem metszik egymást, a transzverzális minden eleme pontosan egy elemnek felel meg (annak a halmaznak, amelynek tagja). Ha az eredeti halmazok metszik egymást, kétféleképpen határozhatjuk meg a transzverzálist. Az első változat azt a helyzetet imitálja, amikor a halmazok nem metszik egymást, ez abból áll, hogy létezik egy bijekció a transzverzálistól a -ig , így a transzverzálisban mindegyikre azt kapjuk, hogy valamilyen elemre van leképezve . Ebben az esetben a transzverzálist különálló képviselők rendszerének is nevezik. Egy másik, kevésbé használt változat nem igényli a transzverzális elemei és a -ból származó halmazok egy-egy kapcsolatát . Ebben a helyzetben a reprezentatív rendszer elemei nem feltétlenül különböznek egymástól [4] [5] . Az alábbiakban a leggyakoribb megközelítések szigorú meghatározásai találhatók. $S$ $S$ $S$ $S$ $\varphi$ $S$ $x$ $x$ $\varphi(x)$ $S$

Definíciók

1) Legyen néhány halmaz. Legyen a halmaz logikai értéke , azaz. a halmaz összes részhalmazának halmaza . Legyen néhány minta a -ból . A kijelölésben szereplő elemek megismétlődhetnek. $x$ $2^{X}$ $x$ $x$ $(X_{1},X_{2},\ldots ,X_{n})$ $2^{X}$

A halmazelemek vektorát családtranszverzálisnak nevezzük, ha a következő összefüggések teljesülnek: $(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) Jelölje véges, nem üres halmazként és részhalmazainak családjaként, azaz , hosszúságú nem üres részhalmazok sorozataként . $E$ $S=(S_{1},S_{2},\ldots ,S_{m})$ $E$ $m$

A család transzverzálisa olyan részhalmaz , amelyre bijekció van, és amelyre a feltétel teljesül . $S$ $T\subseteq E$ $\varphi \colon T\rightarrow \{1,2,\ldots ,m\}$ $\forall t\in T$ ${\displaystyle t\in S_{\varphi (t)))$

Más szóval, a transzverzális elemeihez van egy olyan felsorolás, amely alatt a . $t_{i}\in S_{i}$ $i\in \{1,2,\ldots ,m\}$

Mivel halmaz, ezért minden eleme különböző, innen ered a " különböző képviselők rendszere" elnevezés. $T$

Példák

1) Legyen adott egy halmaz és egy részhalmazcsalád . Egy ilyen családra vonatkozó transzverzális példa az , ahol . $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) Egyes intézményekben vannak jutalékok. Az egyes bizottságok összetétele köteles kijelölni elnökeiket úgy, hogy senki ne elnököljön egynél több bizottságban. Itt a bizottságok transzverzálisát az elnökök állítják össze. $m$

3) A csoportelméletben egy csoport adott részcsoportjára a jobb (illetve, bal) transzverzális egy olyan halmaz, amely pontosan egy elemet tartalmaz minden jobb (illetve, bal) kosettből . Ebben az esetben a "halmazok" (cosets) nem metszik egymást, azaz. a cosets egy partíciót alkot a csoportban. $H$ $G$ $H$

4) Az előző példa speciális eseteként, figyelembe véve a csoportok közvetlen szorzatát , azt kapjuk, amely a cosets transzverzálisa . $G=H\times K$ $H$ $K$

5) Mivel egy tetszőleges halmazon lévő bármely ekvivalencia reláció partícióhoz vezet, az egyes ekvivalenciaosztályok bármely képviselőjének kiválasztása transzverzálishoz vezet.

6) A partíció alapú transzverzális egy másik esete akkor merül fel, ha az X tartományú függvényhez definiált függvény (halmazelméleti) magjaként ismert ekvivalenciarelációt tekintjük partícióként , amely az f tartományt ekvivalenciaosztályokba particionálja úgy, hogy minden elem osztályban ugyanaz a kép legyen az f leképezés alatt . Ha f injektív, akkor csak egy keresztirányú . Opcionálisan injektív f esetén a transzverzális T in korrekciója egy az egyhez egyezést eredményez T és f képe között , amelyet alább jelölünk . Ezért a függvényt jól definiálja az a tulajdonság, hogy minden z esetén : , ahol x az egyetlen olyan elem T -ben , amelyre ; továbbá g kiterjeszthető (nem feltétlenül egyedileg) úgy, hogy az f teljes tartományára definiálva legyen g(z) tetszőleges értékeinek kiválasztásával, amikor z kívül esik az f képen . Egyszerű számítással belátható, hogy az így definiált g tulajdonsággal rendelkezik , ami bizonyítja (ha a tartomány és az f tartománya megegyezik), hogy egy teljes transzformációs félcsoport szabályos félcsoport. A leképezés f -nek (nem feltétlenül az egyetlen) kvázi-inverz elemeként működik ; a félcsoportelméletben ez egyszerűen az inverz elem. Figyeljük meg azonban, hogy a fenti tulajdonsággal rendelkező tetszőleges g-re a "duális" egyenlet nem biztos, hogy teljesül, de ha jelöljük , akkor f a h kvázi fordítottja , azaz . $f$ $\operatorname {ker} f:=\left\{\,\left\{\,y\in X\mid f(x)=f(y)\,\right\}\mid x\in X \,\jobb\}$ $\operatorname {ker} f$ $\operatorname {ker} f$ $\operatorname {Im} f$ $g:(\operátornév {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$

Létezés

A gyakorlatban gyakrabban fontos megválaszolni azt a kérdést, hogy létezik-e transzverzális egy adott család esetében. Ennek a kérdésnek egy kissé humoros megfogalmazása az esküvői probléma:

Legyen néhány fiatal férfi és néhány lány. Sőt, az első sorozatból minden fiatalember több lányt ismer a másodikból. Az összes fiatal férfit feleségül kell venni, hogy mindegyikük monogám házasságot kössön egy általa ismert lánnyal.

Erre a problémára akkor van megoldás, ha létezik egy keresztirányú halmazcsalád olyan lányokból, akik ismernek egy fiút.

A transzverzális létezésének problémájának szigorú megoldása a Hall-tétel a transzverzálisokra, valamint annak általánosítása, a Rado-tétel.

Hall-tétel a transzverzálisokra

Legyen egy nem üres véges halmaz, és annak nem feltétlenül különböző nem üres részhalmazainak családja. Ebben az esetben akkor és csak akkor van transzverzálisa, ha tetszőleges részhalmazok uniója legalább különböző elemeket tartalmaz [6] . $E$ $S=\left\{S_{1},S_{2},...,S_{m}\right\}$ $S$ $k$ ${\displaystyle S_{i))$ $k$ ${\megjelenítési stílus (k=1,2,...,m)}$

Részleges keresztirányú

Ha injekcióról van szó , akkor a transzverzálist részlegesnek nevezzük . Egy család részleges transzverzálisai az alcsaládjainak transzverzálisai. A transzverzális bármely részhalmaza részleges transzverzális. $\varphi$ $S$

Független transzverzálisok

Legyen adott a halmazon valamilyen matroid Legyen a halmaz részhalmazainak családja . A for független transzverzálisa egy olyan transzverzális, amely független halmaz a megadott matroid értelmében. Különösen, ha egy matroid diszkrét, akkor minden transzverzális független. A következő tétel egy független transzverzális létezésének kritériumát adja meg. $E$ $S=(S_{1},S_{2},...,S_{m})$ $E$ $S$

R. Rado tétele

Legyen matroid . _ Egy halmaz nem üres részhalmazainak sorozata akkor és csak akkor rendelkezik független transzverzálissal, ha a sorozat bármely részhalmazának uniója tartalmaz egy független halmazt legalább elemekkel, ahol egy tetszőleges természetes szám nem haladja meg a . $M=(E,J)$ $S=(S_{1},S_{2},\ldots ,S_{m})$ $E$ $k$ $k$ $k$ $m$

Bizonyíték:

${\megjelenítési stílus \négyzet }$ A tétel feltételét célszerű egy halmaz rangja (egy független részhalmaz legnagyobb számossága) fogalmával megfogalmazni:

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

Szükség. Ha van független transzverzális, akkor a halmazzal való metszéspontjában vannak elemek , ahonnan . $\bigcup \limits _{i\in A}{{S}_{i}}$ $\left|A\right|$ $\rho \left(\bigcup \limits _{i\in A}{{S}_{i}}\right)\geq \left|A\right|$

Megfelelőség. Először bizonyítsuk be a következő állítást:

Nyilatkozat. Ha egy adott halmaz (például ) legalább két elemet tartalmaz, akkor ebből a halmazból egy elem eltávolítható az (1) feltétel megsértése nélkül. ${\displaystyle S_{1))$

$\vartriangle$ Éppen ellenkezőleg: legyen és, függetlenül attól, hogy melyik elemet távolítjuk el , az (1) feltétel nem teljesül. Vegyünk két elemet és a halmazból . Számukra léteznek ilyen indexkészletek és , ahol , az $\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$ és . (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$

Tegyük fel: , . A (2) relációkat a következő alakban írjuk át: , honnan . (3) $X=\bigcup \limits _{i\in A}{{S}_{i}}\bigcup {\left({{S}_{1}}\backslash \left\{x\right\ }\jobb)}$ $Y=\bigcup \limits _{i\in B}{{S}_{i}}\bigcup {\left({{S}_{1}}\backslash \left\{y\right\ }\jobb)}$ $\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|$

Az (1) feltétel segítségével alulról becsüljük meg a és a halmazok uniójának és metszetének rangsorait . Mivel az egyenlőtlenség fennáll . (négy) $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$

Annak a ténynek köszönhetően , hogy nálunk . (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|$

A [7] rangfüggvény félmodularitási tulajdonságát felhasználva (4) és (5) összeadása után a következőt kapjuk: . (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$

Az egyenlőtlenség (6) ellentmond a (3) egyenlőtlenségnek. Az állítás bebizonyosodott. $\vartriangle$

Az eljárást az utasítástól kezdve addig alkalmazzuk, amíg nincs szingli halmazunk . Ebben az esetben a szakszervezetük rangja egyenlő . Ezért van a kívánt független keresztirányú. $m$ $\left\{{{t}_{1}}\right\},\ \left\{{{t}_{2}}\right\}\ \ldots ,\ \left\{{{ t}_{m}}\jobbra\}$ $T=\left\{{{t}_{1}},\ {{t}_{2}},\ \ldots ,\ {{t}_{m}}\right\}$ $m$ $T$ ${\megjelenítési stílus \négyzet }$

Következmény

Legyen matroid . _ Egy halmaz nem üres részhalmazainak sorozatának akkor és csakis akkor van független részhalmaza a kardinalitásnak , ha az ebből a sorozatból származó részhalmazok uniója tartalmazza a számosság független részhalmazát, legalább , azaz. [nyolc] $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.$

Általános transzverzálisok

A független transzverzális létezésének kritériuma lehetővé teszi, hogy egyazon halmaz két különböző részhalmazának két különböző rendszerére a közös transzverzális létezéséhez szükséges és elégséges feltételeket kapjunk.

Tétel

Egy véges halmaz két családjának és nem üres részhalmazainak akkor és csak akkor van közös transzverzálisa, ha a [8] egyenlőtlenség bármely részhalmazra és halmazra érvényes . $S=(S_{1},S_{2},...,S_{m})$ $R=(R_{1},R_{2},...,R_{m})$ $E$ $A$ $B$ ${\megjelenítési stílus {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.$

Egy tétel a részhalmazok családjának különálló transzverzálisainak számáról

Legyen valamely halmaz részhalmazainak családja . Legyen ismert a mátrix . $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{igazított }}\jobb.$

Ekkor a család különböző transzverzálisainak száma megegyezik a mátrix állandójával . [9] $S$ $A$

Hivatkozások más szakaszokhoz és alkalmazásokhoz

Az optimalizálás elméletben és a gráfelméletben a közös transzverzális megtalálása a maximális áramlás megtalálására redukálható a hálózatban [8] .

A számítástechnikában a transzverzálisok számítását számos alkalmazási területen használják, és a halmazok bemeneti családját gyakran hipergráfként írják le .

Egy tetszőleges négyzetmátrix főátlóján fekvő elemek egyben egy sor (oszlop) család átlói is. Az ilyen transzverzális kiválasztását számos valószínűségszámítási és algebrai eredmény bizonyítására használják .

A transzverzálisok és a belőlük készült burkolatok használata az Euler-Parker módszer alapja , amely egy adott latin négyzetre merőleges latin négyzeteket keres .

Általánosítás

A transzverzális fogalma általánosítható.

Legyen pozitív egész számok sorozata . Ekkor a család -transzverzálisa a halmaz azon részhalmazainak családja lesz , amelyekre a következő feltételek teljesülnek: $(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))$ számára ; $i\in \{1,2,\ldots ,m\}$
$|P_{i}|=k_{i}$ ;
$P_{i}\cap P_{j}=\varnothing ,i\neq j$ .

Jegyzetek

↑ John Mackintosh HowieA félcsoportelmélet alapjai . - Oxford University Press , 1995. - P. 63. - ISBN 978-0-19-851194-6 .
↑ Clive Reis. Absztrakt algebra : Bevezetés a csoportokba, gyűrűkbe és mezőkbe . - World Scientific , 2011. - P. 57. - ISBN 978-981-4335-64-5 .
↑ Bruno Courcelle; Joost Engelfriet. Gráfstruktúra és monádikus másodrendű logika: nyelvelméleti megközelítés . - 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. Előadások a diszkrét matematikáról. - St. Petersburg, BHV-Petersburg, 2004. - isbn 5-94157-546-7. - c. 529
↑ Rangfüggvény, félmodularitás . ITMO Wiki Abstracts . Hozzáférés dátuma: 2019. december 6. Az eredetiből archiválva : 2019. december 6. (határozatlan)
↑ 1 2 3 Összes felsőoktatási matematika: Tankönyv. 2006. T.7
↑ V. N. Sachkov, 1982

Irodalom

M.L. Krasznov, A.I. Kiselev, G.I. Makarenko, E.V. Shikin, V.I. Zalyapin, A.Yu. Evnin. Összes felsőfokú matematika: Tankönyv. - M . : KomKniga, 2006. - T. 7. - 208 p. — ISBN 5-484-00521-3 .

M. Hall. 5. fejezet "Különböző képviselők rendszerei" // Kombinatorika = Kombinatorial Theory / ford. angolról. S. A. Shirokova; szerk. A. O. Gelfond és V. E. Tarakanov. - M . : Mir, 1970. - S. 65-78 . — 424 p.
V. N. Szacskov. Bevezetés a diszkrét matematika kombinatorikus módszereibe. - M . : Tudomány. Ch. szerk. Fiz.-Matek. lit., 1982. - 384 p.

M. Swami, K. Thulasiraman. 8.6. fejezet "Egyezés kétoldalú gráfokban" // Grafikonok, hálózatok és algoritmusok = Graphs, Networks, and Algorithms / fordítás. angolról. M. V. Gorbatova, V. L. Torkhova, S. A. Frolov, V. N. Csetverikov; szerk. V. A. Gorbatova. - M . : Mir, 1984. - S. 165-166. — 455 p. — 11.000 példány.
V. A. Emelicsev, O. I. Melnyikov, V. I. Sarvanov, R. I. Tyskevich. Előadások a gráfelméletről. - M . : Nauka , 1990. - S. 87-92. — 384 p. — ISBN 5-02-013992-0 .
N. I. Kostyukova. Grafikonok és alkalmazásaik . — 16. sz. előadás: A transzverzálisok elmélete. Letöltve: 2009. július 29. (határozatlan)
Alexander Schrijver. 22. fejezet "Transzverzálisok", 23. fejezet "Közös transzverzálisok" // Kombinatorikus optimalizálás . - Springer, 2003. - P. 378-409. — 1800 p. — ISBN 978-3540443896 .
Roberts F., Tesman B. Alkalmazott kombinatorika. - Boca Raton: CRC Press, 2009. - ISBN 978-1-4200-9982-9 .
Brualdi R. Bevezető kombinatorika. - Upper Saddle River, NJ: Prentice Hall, 2010. - ISBN 0-13-602040-2 .