Příčný

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 27. září 2018; kontroly vyžadují 10 úprav . Nezaměňovat s Triangle transversal .

Transversal ( systém různých zástupců ) je pojem z teorie množin , který je poměrně důležitý pro veškerou diskrétní matematiku . Existuje také v logice a lineární algebře .

V matematice je pro danou rodinu množin transverzál (v některé zahraniční literatuře také nazývaný průřez [1] [2] [3] ) množina obsahující právě jeden prvek z každé množiny z . Když se množiny od navzájem neprotínají, každý prvek transverzálky odpovídá právě jednomu prvku (množině, jejímž je členem). Pokud se původní množiny protínají, existují dva způsoby, jak definovat transverzál. První varianta napodobuje situaci, kdy se množiny vzájemně neprotínají, spočívá v existenci bijekce z transverzály do , takže pro každou v transverzále dostaneme, že je mapována na nějaký prvek . V tomto případě se transverzál také nazývá systém odlišných zástupců. Jiná, méně používaná varianta nevyžaduje vztah jedna ku jedné mezi prvky transversály a množinami z . V této situaci nejsou prvky reprezentativního systému nutně odlišné [4] [5] . Následují přesné definice nejběžnějších přístupů. $S$ $S$ $S$ $S$ $\varphi$ $S$ $X$ $X$ $\varphi(x)$ $S$

Definice

1) Nechť je nějaká množina. Nechť je Boolean množiny , tj. množina všech podmnožin množiny . Nechť je ukázka z . Prvky v tomto výběru se mohou opakovat. $X$ $2^{X}$ $X$ $X$ $(X_{1},X_{2},\ldots ,X_{n})$ $2^{X}$

Vektor množinových prvků se nazývá rodinný transverzál , pokud platí následující vztahy: $(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) Označme jako konečnou neprázdnou množinu a jako rodinu jejích podmnožin, tedy posloupnost neprázdných podmnožin délky . $E$ $S=(S_{1},S_{2},\ldots ,S_{m})$ $E$ $m$

Transverzál rodiny je podmnožina , pro kterou existuje bijekce a pro kterou je splněna podmínka . $S$ $T\subseteq E$ $\varphi \colon T\rightarrow \{1,2,\ldots ,m\}$ $\forall t\in T$ ${\displaystyle t\in S_{\varphi (t)))$

Jinými slovy, pro prvky transverzálu existuje takový výčet, pod kterým pro . $t_{i}\in S_{i}$ $i\in \{1,2,\ldots ,m\}$

Protože se jedná o množinu, všechny její prvky jsou různé, odtud název "systém různých zástupců". $T$

Příklady

1) Nechť je dána množina a rodina podmnožin . Příkladem transversály pro takovou rodinu je , kde . $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) V některé instituci jsou provize. Od složení každé komise se vyžaduje, aby jmenovala své předsedy tak, aby nikdo nepředsedal více než jedné komisi. Zde budou průřezy komisí skládat jejich předsedové. $m$

3) V teorii grup je pro danou podgrupu grupy pravá (respektive levá) transverzála množina obsahující právě jeden prvek z každé pravé (respektive levé) množiny . V tomto případě se "množiny" (kosety) vzájemně neprolínají, tzn. cosets tvoří oddíl skupiny. $H$ $G$ $H$

4) Jako speciální případ předchozího příkladu, vezmeme-li v úvahu přímý součin skupin , dostaneme, což je transverzál pro cosets . $G=H\times K$ $H$ $K$

5) Protože jakýkoli vztah ekvivalence na libovolné množině vede k rozdělení, výběr libovolného zástupce z každé třídy ekvivalence vede k transverzáli.

6) Další případ transverzálu založeného na dělení nastává, když uvažujeme vztah ekvivalence známý jako (teoretické) jádro funkce definované pro funkci s doménou X jako její dělení , které rozděluje doménu f do tříd ekvivalence tak, že všechny prvky ve třídě mají stejný obrázek pod mapováním f . Je-li f injektivní, existuje pouze jeden transversál . Pro volitelně injektivní f způsobí oprava příčného T in vzájemnou korespondenci mezi T a obrazem f , níže označenou jako . Proto je funkce dobře definována vlastností, že pro všechna z : , kde x je jediný prvek v T takový, že ; dále může být g rozšířeno (ne nutně jednoznačně) tak, že je definováno v celém rozsahu f výběrem libovolných hodnot pro g(z) , když je z mimo obraz f . Je jednoduchým výpočtem vidět, že takto definované g má vlastnost , což je důkaz (když definiční obor a obor f jsou stejné množiny), že úplná transformační pologrupa je regulární pologrupa. Zobrazení funguje jako (ne nutně jediný) kvazi-inverzní prvek pro f ; v teorii pologrup je to jednoduše inverzní prvek. Všimněte si však, že pro libovolné g s výše uvedenou vlastností nemusí platit „dvojitá“ rovnice, ale pokud označíme , pak f je kvazi-reverzní k h , tedy . $F$ $\operatorname {ker} f:=\left\{\,\left\{\,y\in X\mid f(x)=f(y)\,\right\}\mid x\in X \,\že jo\}$ $\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$

Existence

V praxi je častěji důležité odpovědět na otázku, zda pro konkrétní rodinu existuje transverzál. Poněkud vtipnou formulací této otázky je svatební problém:

Nechť je tam pár mladých mužů a pár dívek. Navíc každý mladý muž z prvního setu zná několik dívek z druhého. Je požadováno oženit se se všemi mladými muži, aby se každý spojil v monogamní manželství s dívkou, kterou zná.

Tento problém má řešení, pokud existuje transverzál pro rodinu sestav tvořenou z dívek, které znají konkrétního chlapce.

Rigorózním řešením problému existence transverzály je Hallova věta pro transverzály a také její zobecnění, Radova věta.

Hallova věta pro transverzály

Nechť být neprázdná konečná množina a být rodinou ne nutně různých jejích neprázdných podmnožin. V tomto případě má transversál právě tehdy, když pro libovolné podmnožiny jejich sjednocení obsahuje alespoň různé prvky [6] . $E$ ${\displaystyle S=\left\{S_{1},S_{2},...,S_{m}\right\))$ $S$ $k$ ${\displaystyle S_{i))$ $k$ $(k=1,2,...,m)$

Částečná příčná

Pokud je injekce , pak se transverzál nazývá částečný . Částečné transverzály rodiny jsou transverzály jejích podrodin. Jakákoli podmnožina transverzálu je částečnou transverzálou. $\varphi$ $S$

Nezávislé transverzály

Nechť je na množině dán nějaký matroid Nechť je rodina podmnožin množiny . Nezávislá transverzál pro je transverzál, který je nezávislou množinou ve smyslu zadaného matroidu. Konkrétně, pokud je matroid diskrétní, pak je jakýkoli transverzál nezávislý. Následující věta dává kritérium pro existenci nezávislé transverzály. $E$ $S=(S_{1},S_{2},...,S_{m})$ $E$ $S$

R. Radova věta

Buď matroidem . _ Posloupnost neprázdných podmnožin množiny má nezávislou transverzál tehdy a jen tehdy, když sjednocení jakýchkoli podmnožin z této posloupnosti obsahuje nezávislou množinu s alespoň prvky, kde libovolné přirozené číslo nepřesahuje . $M=(E,J)$ $S=(S_{1},S_{2},\ldots ,S_{m})$ $E$ $k$ $k$ $k$ $m$

Důkaz:

$\square$ Podmínku věty je vhodné formulovat pomocí konceptu hodnosti množiny (největší mohutnost nezávislé podmnožiny):

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

Potřeba. Pokud existuje nezávislá transverzála, pak její průnik s množinou má prvky, odkud . $\bigcup \limits _{i\in A}{{S}_{i}}$ $\left|A\right|$ $\rho \left(\bigcup \limits _{i\in A}{{S}_{i}}\right)\geq \left|A\right|$

Přiměřenost. Nejprve dokažme následující tvrzení:

Tvrzení. Pokud určitá množina (například ) obsahuje alespoň dva prvky, pak lze jeden prvek z této množiny odebrat, aniž by byla porušena podmínka (1). ${\displaystyle S_{1))$

$\vartriangle$ Naopak: nechť a bez ohledu na to, jaký prvek je odstraněn z , podmínka (1) nebude splněna. Vezměte dva prvky a ze sady . Pro ně existují takové sady indexů a , kde , že $\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$ a . (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$

Položme: , . Relace (2) přepíšeme ve tvaru: , odkud . (3) $X=\bigcup \limits _{i\in A}{{S}_{i}}\bigcup {\left({{S}_{1}}\zpětné lomítko \left\{x\right\ }\že jo)}$ $Y=\bigcup \limits _{i\in B}{{S}_{i}}\bigcup {\left({{S}_{1}}\zpětné lomítko \left\{y\right\ }\že jo)}$ $\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|$

Pomocí podmínky (1) odhadneme zdola řady sjednocení a průniku množin a . Od , nerovnost platí . (čtyři) $X$ $Y$ $X\bigcup {Y}=\bigcup \limits _{i\in A\bigcup {B}}{{S}_{i}}\bigcup {\left({{S}_{1}} \obrácené lomítko \left\{x\right\}\right)}\bigcup {\left({{S}_{1}}\obrácené lomítko \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$

Vzhledem k tomu , že máme . (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|$

Pomocí vlastnosti semimodularity funkce pořadí [7] po sečtení (4) a (5) dostaneme: . (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$

Nerovnost (6) je v rozporu s nerovností (3). Tvrzení bylo prokázáno. $\vartriangle$

Postup z příkazu budeme aplikovat tak dlouho , dokud nám nezbydou množiny singleton . V tomto případě je hodnost jejich svazku rovna . Existuje tedy požadovaný nezávislý transverzál. $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$

Důsledek

Buď matroidem . _ Posloupnost neprázdných podmnožin množiny má nezávislou částečnou transverzál mohutnosti tehdy a jen tehdy, když sjednocení jakýchkoli podmnožin z této posloupnosti obsahuje nezávislou podmnožinu mohutnosti alespoň , tj. [osm] $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.$

Obecné transverzály

Kritérium existence nezávislé transverzály umožňuje získat nezbytné a dostatečné podmínky pro existenci společné transverzály pro dva různé systémy podmnožin téže množiny.

Věta

Dvě rodiny a neprázdné podmnožiny konečné množiny mají společný transversál právě tehdy, když pro libovolné podmnožiny a množiny platí nerovnost [8] . $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.$

Věta o počtu odlišných transverzálů rodiny podmnožin

Dovolit být rodina podmnožin nějakého souboru . Nechť je matice známá . $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 }}\že jo.$

Potom je počet různých transversálů rodiny roven permanentu matice . [9] $S$ $A$

Odkazy na další sekce a aplikace

V teorii optimalizace a teorii grafů lze nalezení společného transverzálu redukovat na nalezení maximálního toku v síti [8] .

V informatice se výpočet transversálů používá v několika aplikačních oblastech a vstupní rodina množin je často popisována jako hypergraf .

Prvky ležící na hlavní diagonále libovolné čtvercové matice jsou také transverzálem rodiny řádků (sloupců). Výběr takového transversálu se používá při dokazování řady výsledků v teorii pravděpodobnosti a algebře .

Použití transversál a překrytí z nich je základem Euler-Parkerovy metody hledání ortogonálních latinských čtverců k danému latinskému čtverci.

Generalizace

Pojem transverzál lze zobecnit.

Nechť existuje posloupnost kladných celých čísel . Potom -transversal rodiny bude rodina podmnožin množiny, pro kterou jsou splněny následující podmínky: $(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))$ pro ; $i\in \{1,2,\ldots ,m\}$
$|P_{i}|=k_{i}$ ;
$P_{i}\cap P_{j}=\varnothing ,i\neq j$ .

Poznámky

↑ John Mackintosh HowieZáklady teorie semigrup . - Oxford University Press , 1995. - S. 63. - ISBN 978-0-19-851194-6 .
↑ Clive Reis. Abstraktní algebra : Úvod do grup, okruhů a polí . - World Scientific , 2011. - S. 57. - ISBN 978-981-4335-64-5 .
↑ Bruno Courcelle; Joost Engelfriet. Struktura grafu a monadická logika druhého řádu: jazykově teoretický přístup . - Cambridge University Press , 2012. - S. 95. - ISBN 978-1-139-64400-6 .
↑ Roberts, Tesman, 2009 , str. 692.
↑ Brualdi, 2010 , str. 322.
↑ Kapitonova Yu. V., Krivoy S. L., Letichevsky A. A. Přednášky o diskrétní matematice. - Petrohrad, BHV-Petersburg, 2004. - isbn 5-94157-546-7. - c. 529
↑ Pořadová funkce, semimodularita . ITMO Wiki Abstrakty . Datum přístupu: 6. prosince 2019. Archivováno z originálu 6. prosince 2019. (neurčitý)
↑ 1 2 3 Celá vyšší matematika: Učebnice. T.7., 2006
↑ V. N. Sachkov, 1982

Literatura

M.L. Krasnov, A.I. Kiselev, G.I. Makarenko, E.V. Shikin, V.I. Zalyapin, A.Yu. Evnin. Celá vyšší matematika: Učebnice. - M. : KomKniga, 2006. - T. 7. - 208 s. — ISBN 5-484-00521-3 .

M. Hall. Kapitola č. 5 "Systémy různých zástupců" // Kombinatorika = kombinatorická teorie / přel. z angličtiny. S. A. Široková; vyd. A. O. Gelfond a V. E. Tarakanov. - M .: Mir, 1970. - S. 65 -78. — 424 s.
V.N. Sachkov. Úvod do kombinatorických metod diskrétní matematiky. - M .: Věda. Ch. vyd. Fyzikální matematika lit., 1982. - 384 s.

M. Svámí, K. Thulasiraman. Kapitola č. 8.6 "Párování v bipartitních grafech" // Grafy, sítě a algoritmy = Grafy, sítě a algoritmy / přel. z angličtiny. M. V. Gorbatova, V. L. Torkhova, S. A. Frolov, V. N. Chetverikov; vyd. V. A. Gorbatov. - M .: Mir, 1984. - S. 165-166. — 455 str. — 11 000 výtisků.
V. A. Emeličev, O. I. Melnikov, V. I. Sarvanov, R. I. Tyškevič. Přednášky z teorie grafů. - M .: Nauka , 1990. - S. 87-92. — 384 s. — ISBN 5-02-013992-0 .
N. I. Kosťuková. Grafy a jejich aplikace . — Přednáška č. 16: Teorie transverzál. Staženo: 29. července 2009. (neurčitý)
Alexander Schrijver. Kapitola 22 "Transversals", kapitola 23 "Common transversals" // Kombinatorická optimalizace . - Springer, 2003. - S. 378-409. — 1800 str. — ISBN 978-3540443896 .
Roberts F., Tesman B. Aplikovaná kombinatorika. - Boca Raton: CRC Press, 2009. - ISBN 978-1-4200-9982-9 .
Brualdi R. Úvodní kombinatorika. - Upper Saddle River, NJ: Prentice Hall, 2010. - ISBN 0-13-602040-2 .