Příčný (kombinatorika) - Transversal (combinatorics)
v matematika, zejména v kombinatorika, vzhledem k tomu, rodina sad, zde nazývaná sbírka C, a příčný (také nazývaný a průřez[1][2][3]) je sada obsahující přesně jeden prvek od každého člena kolekce. Když jsou sady kolekce vzájemně nesouvislé, každý prvek příčného odpovídá přesně jednomu členu C (soubor, jehož je členem). Pokud původní sady nejsou disjunktní, existují dvě možnosti pro definici příčného:
- Jednou z variant je, že existuje bijekce F od příčného k C takhle X je prvek F(X) pro každého X v příčném směru. V tomto případě se příčný také nazývá a systém odlišných zástupců (SDR).[4]:29
- Druhý, méně běžně používaný, nevyžaduje vzájemný vztah mezi prvky příčného a množinami C. V této situaci členové systém zástupců nejsou nutně odlišné.[5]:692[6]:322
v počítačová věda, výpočet příčných hodnot je užitečný v několika aplikačních doménách se vstupem rodina sad často popisován jako a hypergraf.
Existence a počet
Základní otázkou při studiu SDR je, zda SDR existuje či neexistuje. Hallova věta o manželství dává nezbytné a dostatečné podmínky pro to, aby konečné sady sbírek, některé se možná překrývaly, byly příčné. Podmínkou je, že pro každé celé číslo k, každá sbírka k sady musí obsahovat alespoň společné k různé prvky.[4]:29
Následující upřesnění H. J. Ryser dává nižší meze počtu takových SDR.[7]:48
Teorém. Nechat S1, S2, ..., Sm být souborem sad takových, že obsahuje alespoň k prvky pro k = 1,2,...,m a pro všechny k-kombinace {} z celých čísel 1,2, ...,m a předpokládejme, že každá z těchto sad obsahuje alespoň t elementy. Li t ≤ m pak má sbírka minimálně t ! SDR, a pokud t > m pak má sbírka minimálně t ! / (t - m)! SDR.
Vztah k párování a krytí
Lze postavit a bipartitní graf ve kterém jsou vrcholy na jedné straně množiny, vrcholy na druhé straně jsou prvky a hrany spojují množinu s prvky, které obsahuje. Potom je příčný ekvivalentní a perfektní shoda v tomto grafu.
Lze sestrojit a hypergraf ve kterých jsou vrcholy prvky a hyper-hrany jsou množiny. Potom je příčný ekvivalentní a vrcholový kryt v hypergrafii.
Příklady
v teorie skupin, vzhledem k tomu, podskupina H skupiny G, pravý (respektive levý) příčný je a soubor obsahující přesně jeden prvek z každé pravé (respektive levé) coset z H. V tomto případě jsou „množiny“ (kosety) vzájemně nesouvislé, tj. Kosety tvoří a rozdělit skupiny.
Jako konkrétní případ předchozího příkladu, uvedený a přímý součin skupin , pak H je transverzální pro kosety z K..
Obecně, protože jakýkoli vztah ekvivalence na libovolné množině vznikne oddíl, který z každého vybírá libovolného zástupce třída ekvivalence vede k příčnému.
Další instance příčného přenosu založeného na oddílech nastane, když vezmeme v úvahu vztah ekvivalence známý jako (set-teoretické) jádro funkce, definované pro funkci s doména X jako oddíl domény . které oddíly jsou doménou F do tříd ekvivalence, takže všechny prvky ve třídě mapují pomocí F na stejnou hodnotu. Li F je injektivní, existuje pouze jeden příčný . Pro ne-nutně injektivní F, upevnění příčného T z vyvolává korespondenci jedna k jedné mezi T a obraz z F, dále označováno . V důsledku toho funkce je dobře definována vlastností, že pro všechny z v kde X je jedinečný prvek v T takhle ; dále G lze rozšířit (ne nutně jedinečným způsobem) tak, aby byla definována jako celek codomain z F výběrem libovolných hodnot pro g (z) když z je mimo obraz F. Je to jednoduchý výpočet, který to ověří G takto definovaný má vlastnost, že , což je důkaz (když doména a doména F jsou stejné sady), které plná transformační poloskupina je pravidelná poloskupina. funguje jako (nemusí být nutně jedinečný) kvazi inverzní pro F; v teorii semigroup se to jednoduše nazývá inverzní. Všimněte si však, že pro libovolné G s výše uvedenou vlastností „dvojí“ rovnice nemusí držet. Pokud však označíme , pak F je kvazi inverzní h, tj. .
Společné příčné
A společné příčné sbírek A a B (kde ) je množina, která je příčná k oběma A a B. Sbírky A a B mít společný příčný právě pro všechny ,
Zobecnění
A částečné příčné je sada obsahující nejvýše jeden prvek od každého člena kolekce, nebo (v přísnější podobě konceptu) sada s injekcí ze sady do C. Průřezy konečné kolekce C konečných množin tvoří základní množiny a matroid, příčný matroid z C. Nezávislé množiny příčného matroidu jsou částečné příčné C.[9]
An nezávislý příčný ' (také nazývaný a duhová nezávislá sada nebo nezávislý systém zástupců) je příčný, který je také nezávislá sada daného grafu. Chcete-li vysvětlit rozdíl v obrazném vyjádření, zvažte fakultu s m katedry, kde chce děkan fakulty postavit komisi m členové, jeden člen za oddělení. Takový výbor je příčný. Nyní však předpokládejme, že se někteří členové fakulty navzájem nelíbí a nesouhlasí se společným zasedáním ve výboru. V tomto případě musí být výbor nezávislým průřezem, kde základní graf popisuje vztahy „nelíbí se“.
Další zobecnění konceptu příčného by byla množina, která má neprázdnou křižovatku s každým členem C. Příkladem posledně jmenovaného by byl a Bernsteinova sada, která je definována jako sada, která má neprázdný průnik s každou sadou C, ale neobsahuje žádnou sadu C, kde C je sbírka všech perfektní sady topologické Polský prostor. Jako další příklad pojďme C skládají se ze všech řádků a projektivní rovina, pak blokovací sada v této rovině je sada bodů, která protíná každou čáru, ale neobsahuje žádnou čáru.
Teorie kategorií
V jazyce teorie kategorií, a příčný kolekce vzájemně nesouvislých sad je a sekce z kvocientová mapa vyvolané kolekcí.
Výpočetní složitost
The výpočetní složitost výpočtu všech příčných vstupů rodina sad byl studován, zejména v rámci enumerační algoritmy.
Viz také
Reference
- ^ John Mackintosh Howie (1995). Základy teorie poloskupin. Clarendon Press. p. 63. ISBN 978-0-19-851194-6.
- ^ Clive Reis (2011). Abstraktní algebra: Úvod do skupin, prstenů a polí. World Scientific. p. 57. ISBN 978-981-4335-64-5.
- ^ Bruno Courcelle; Joost Engelfriet (2012). Struktura grafu a monadická logika druhého řádu: Jazykově teoretický přístup. Cambridge University Press. p. 95. ISBN 978-1-139-64400-6.
- ^ A b Lovász, László; Plummer, M. D. (1986), Teorie shody, Annals of Discrete Mathematics, 29, Severní Holandsko, ISBN 0-444-87916-1, PAN 0859549
- ^ Roberts, Fred S .; Tesman, Barry (2009), Aplikovaná kombinatorika (2. vydání), Boca Raton: CRC Press, ISBN 978-1-4200-9982-9
- ^ Brualdi, Richard A. (2010), Úvodní kombinatorika (5. vydání), Upper Saddle River, NJ: Prentice Hall, ISBN 0-13-602040-2
- ^ Ryser, Herbert John (1963), Kombinatorická matematika, The Carus Mathematical Monographs # 14, Mathematical Association of America
- ^ E. C. Milner (1974), PŘÍČNÁ TEORIE, Sborník příspěvků z mezinárodního kongresu matematiků, str. 161
- ^ Oxley, James G. (2006), Teorie matroidůOxfordské postgraduální texty z matematiky, 3Oxford University Press, s. 48, ISBN 978-0-19-920250-8.
Další čtení
- Lawler, E. L. Kombinatorická optimalizace: Sítě a matroidy. 1976.
- Mirsky, Leon (1971). Transverzální teorie: Popis některých aspektů kombinatorické matematiky. Akademický tisk. ISBN 0-12-498550-5.