Struktura výskytu - Incidence structure

Příklad 1: body a přímky euklidovské roviny (nahoře)
Příklad 2: body a kružnice (uprostřed),
Příklad 3: konečná struktura dopadu definovaná maticí dopadu (dole)
v matematika, abstraktní systém skládající se ze dvou typů objektů a jednoho vztahu mezi těmito typy objektů se nazývá an struktura výskytu. Zvažte body a čáry Euklidovské letadlo jako dva typy objektů a ignorovat všechny vlastnosti této geometrie kromě vztah z nichž bodů jsou čáry pro všechny body a čáry. Zbývá tedy struktura dopadu euklidovské roviny.
Výskytové struktury jsou nejčastěji uvažovány v geometrických souvislostech, kde jsou abstrahovány od, a tedy zobecňují, roviny (jako např. afinní, projektivní, a Möbiova letadla ), ale koncept je velmi široký a neomezuje se pouze na geometrické nastavení. Dokonce i v geometrickém prostředí nejsou dopadové struktury omezeny pouze na body a čáry; objekty vyšších rozměrů (roviny, tělesa, n-spaces, conics, etc.) can be used. Studium konečných struktur se někdy nazývá konečná geometrie.[1]
Formální definice a terminologie
An struktura výskytu je trojitý (P, L, Já) kde P je množina, jejíž prvky se nazývají bodů, L je odlišná množina, jejíž prvky se nazývají řádky a Já ⊆ P × L je výskyt vztah. Prvky Já jsou nazývány vlajky. Pokud (p, l) je v Já pak lze říci ten bod p řádek „leží na“ l nebo že linka l bod „prochází“ p. Více „symetrická“ terminologie, aby odrážela symetrický povahou tohoto vztahu je, že “p je incident s l„nebo tak“l je incident s p"a používá notaci p Já l synonymně s (p, l) ∈ Já.[2]
V některých běžných situacích L může být sada podmnožin P v takovém případě výskyt Já bude zadržení (p Já l kdyby a jen kdyby p je členem l). Incidentní struktury tohoto typu se nazývají set-teoretický.[3] Ne vždy tomu tak je, například pokud P je sada vektorů a L sada náměstí matice, můžeme definovat Já = {(proti, M) : vektor proti je vlastní vektor matice M}. Tento příklad také ukazuje, že zatímco se používá geometrický jazyk bodů a čar, typy objektů nemusí být těmito geometrickými objekty.
Příklady
- Některé příklady struktur výskytu
1. Fano letadlo
2. Nerovnoměrná struktura
Struktura výskytu je jednotný pokud každá řada dopadá se stejným počtem bodů. Každý z těchto příkladů, s výjimkou druhého, je jednotný se třemi body na řádek.
Grafy
Žádný graf (což nemusí být jednoduchý; smyčky a více hran jsou povoleny) je jednotná struktura dopadu se dvěma body na řádek. U těchto příkladů tvoří vrcholy grafu množinu bodů, hrany grafu tvoří množinu čar a výskyt znamená, že vrchol je koncovým bodem hrany.
Lineární prostory
Výskytové struktury jsou málokdy studovány v plné obecnosti; je typické studovat struktury výskytu, které splňují některé další axiomy. Například a částečný lineární prostor je struktura výskytu, která splňuje:
- Jakékoli dva odlišné body jsou incidenty s nanejvýš jednou společnou čarou a
- Každá řada dopadá s nejméně dvěma body.
Pokud je první výše uvedený axiom nahrazen silnějším:
- Jakékoli dva odlišné body se shodují s přesně jednou společnou čarou,
struktura výskytu se nazývá a lineární prostor.[4][5]
Sítě
Specializovanějším příkladem je a k-síť. Toto je struktura dopadu, do které řádky spadají k paralelní třídy, takže dva řádky ve stejné paralelní třídě nemají žádné společné body, ale dva řádky v různých třídách mají přesně jeden společný bod a každý bod patří přesně jednomu řádku z každé paralelní třídy. Příklad a k-net je množina bodů an afinní letadlo dohromady s k paralelní třídy afinních linií.
Dvojitá struktura
Pokud si vyměníme roli „bodů“ a „čar“ v
- C = (P, L, Já)
získáme duální struktura,
- C∗ = (L, P, Já∗),
kde Já∗ je konverzní vztah z Já. Z definice bezprostředně vyplývá, že:
- C∗∗ = C.
Toto je abstraktní verze projektivní dualita.[2]
Struktura C to je izomorfní na jeho duální C∗ je nazýván self-dual. Fano rovina nahoře je struktura dvojího dopadu.
Jiná terminologie
Koncept struktury dopadu je velmi jednoduchý a vznikl v několika oborech, z nichž každý zavedl svůj vlastní slovník a specifikoval typy otázek, které se na tyto struktury obvykle kladou. Výskytové struktury používají geometrickou terminologii, ale v teoretická graf termíny, kterým se říká hypergrafy a z teoretického hlediska designu se jim říká blokové vzory. Oni jsou také známí jako nastavený systém nebo rodina sad v obecném kontextu.
Hypergrafy

Každý hypergraf nebo nastavený systém lze považovat za incidenční strukturu, ve které univerzální sada hraje roli „bodů“, odpovídajících rodina sad hraje roli „čar“ a relace výskytu je nastavit členství „∈“. Naopak každou strukturu dopadu lze chápat jako hypergraf, když identifikujeme čáry se sadami bodů, které s nimi souvisejí.
Blokové vzory
(Obecný) návrh bloku je sada X společně s a rodina F podmnožin z X (opakované podmnožiny jsou povoleny). K uspokojení podmínek numerické pravidelnosti je obvykle vyžadován návrh bloku. Jako struktura výskytu X je množina bodů a F je sada řádků, obvykle nazývaná bloky v tomto kontextu (opakované bloky musí mít odlišná jména, takže F je ve skutečnosti sada a ne multiset). Pokud jsou všechny podmnožiny v F mají stejnou velikost, nazývá se návrh bloku jednotný. Pokud každý prvek X se objeví ve stejném počtu podmnožin, říká se, že je blokový design pravidelný. Duál jednotného designu je běžný design a naopak.
Příklad: Fano letadlo
Zvažte návrh bloku / hypergraf daný:
- ,
- .
Tato struktura dopadů se nazývá Fano letadlo. Jako blokový design je jednotný i pravidelný.
V daném označení jsou řádky přesně podmnožinami bodů, které se skládají ze tří bodů, jejichž popisky se s použitím sčítají až na nulu nim navíc. Alternativně každé číslo, pokud je zapsáno binární, lze identifikovat nenulovým vektorem délky tři přes binární pole. Tři vektory, které generují a podprostor tvoří linii; v tomto případě to odpovídá jejich vektorovému součtu, který je nulovým vektorem.
Zastoupení
Výskytové struktury mohou být zastoupeny mnoha způsoby. Pokud jsou sady P a L jsou konečné, tyto reprezentace mohou kompaktně kódovat všechny relevantní informace týkající se struktury.
Matice výskytu
The matice výskytu (konečné) struktury dopadu je a (0,1) matice který má své řádky indexované podle bodů {pi} a sloupce indexované řádky {lj} Kde ij-tý záznam je 1, pokud pi Já lj a 0 jinak.[6] Matice dopadu není jednoznačně určena, protože závisí na libovolném pořadí bodů a přímek.[7]
Nerovnoměrná struktura dopadu na obrázku výše (příklad číslo 2) je dána vztahem:
- P = {A, B, C, D, E, P}
- L = { l = {C, P, E}, m = {P}, n = {P, D}, Ó = {P, A}, p = {A, B}, q = {P, B} }.
Matice výskytu pro tuto strukturu je:
což odpovídá tabulce výskytu:
Já l m n Ó p q A 0 0 0 1 1 0 B 0 0 0 0 1 1 C 1 0 0 0 0 0 D 0 0 1 0 0 0 E 1 0 0 0 0 0 P 1 1 1 1 0 1
Pokud je struktura dopadu C má incidenční matici M, pak duální struktura C∗ má transponovat matici MT jako její matice dopadu (a je touto maticí definována).
Struktura dopadu je duální, pokud existuje uspořádání bodů a čar, takže matice dopadu vytvořená s tímto uspořádáním je symetrická matice.
Se štítky uvedenými v příkladu číslo 1 výše as objednanými body A, B, C, D, G, F, E a řádky objednané l, p, n, s, r, m, q, Fano rovina má matici dopadu:
Jelikož se jedná o symetrickou matici, je rovina Fano struktura s dvojitým dopadem.
Obrázková znázornění
Údaj o incidenci (tj. Zobrazení struktury dopadu) je konstruován tak, že body jsou reprezentovány tečkami v rovině a mají vizuální prostředky pro spojování teček, aby odpovídaly přímkám.[7] Tečky mohou být umístěny jakýmkoli způsobem, neexistují žádná omezení vzdálenosti mezi body ani žádné vztahy mezi body. Ve struktuře dopadu neexistuje koncept, že by bod byl mezi dvěma dalšími body; pořadí bodů na řádku není definováno. Porovnejte to s uspořádaná geometrie, který má představu mezi. Stejná prohlášení lze učinit o vyobrazení čar. Zejména nemusí být čáry zobrazeny pomocí „přímkových segmentů“ (viz příklady 1, 3 a 4 výše). Stejně jako u obrazového znázornění grafy „překročení dvou„ čar “na jakémkoli jiném místě než tečce nemá žádný význam z hlediska struktury dopadu; je to jen nehoda reprezentace. Tyto údaje o incidenci se někdy mohou podobat grafům, ale nejsou to grafy, pokud struktura výskytu není graf.
Realizovatelnost
Výskytové struktury lze modelovat pomocí bodů a křivek v Euklidovské letadlo s obvyklým geometrickým významem dopadu. Některé struktury dopadu připouštějí zastoupení pomocí bodů a (přímých) čar. Struktury, které lze nazývat realizovatelné. Pokud není uveden žádný okolní prostor, předpokládá se euklidovská rovina. Fano rovina (příklad 1 výše) není realizovatelná, protože potřebuje alespoň jednu křivku. Konfigurace Möbius-Kantor (příklad 4 výše) není realizovatelná v euklidovské rovině, ale je realizovatelná v složité letadlo.[8] Na druhé straně jsou příklady 2 a 5 výše realizovatelné a uvedené údaje o incidenci to dokazují. Steinitz (1894)[9] to ukázal n3-konfigurace (dopadové struktury s n body a n čáry, tři body na čáru a tři čáry skrz každý bod) jsou buď realizovatelné, nebo vyžadují ve svých reprezentacích použití pouze jedné zakřivené čáry.[10] Fano letadlo je jedinečný (73) a konfigurace Möbius-Kantor je jedinečná (83).
Incidentní graf (Leviho graf)

Každá struktura dopadu C odpovídá a bipartitní graf volal Leviho graf nebo graf výskytu struktury. Jelikož jakýkoli bipartitní graf je dvoubarevný, může být grafu Levi přiřazen černobílý vrchol zbarvení, kde černé vrcholy odpovídají bodům a bílé vrcholy odpovídají čarám C. Okraje tohoto grafu odpovídají příznakům (páry dopadajících bodů / přímek) struktury dopadu. Původní Leviho graf byl grafem dopadu zobecněný čtyřúhelník objednávky dva (příklad 3 výše),[11] ale termín byl prodloužen o H.S.M. Coxeter[12] odkazovat na graf dopadu jakékoli struktury výskytu.[13]

Příklady grafu Levi
Leviho graf Fano letadlo je Heawoodův graf. Protože graf Heawood je připojeno a vrchol-tranzitivní, existuje automorfismus (například ten, který je definován odrazem kolem svislé osy na obrázku grafu Heawood) zaměňující černé a bílé vrcholy. To zase znamená, že rovina Fano je sebe-duální.
Specifické znázornění Leviho grafu konfigurace Möbius-Kantor (příklad 4 výše) vlevo ukazuje, že rotace π/4 kolem středu (ve směru hodinových ručiček nebo proti směru hodinových ručiček) diagramu zaměňuje modré a červené vrcholy a mapuje hrany na hrany. To znamená, že v tomto grafu existuje barevná záměna automorfismu. V důsledku toho je struktura výskytu známá jako konfigurace Möbius-Kantor sama sebe.
Zobecnění
Je možné zobecnit pojem struktury dopadu tak, aby zahrnoval více než dva typy objektů. Struktura s k typy objektů se nazývá struktura výskytu hodnosti k nebo a hodnost k geometrie.[13] Formálně jsou definovány jako k + 1 n-tice S = (P1, P2, ..., Pk, Já) s Pi ∩ Pj = ∅ a
Graf Levi pro tyto struktury je definován jako a multipartitní graf přičemž vrcholy odpovídající každému typu jsou vybarveny stejně.
Viz také
Poznámky
- ^ Colbourn & Dinitz 2007, str. 702
- ^ A b Dembowski 1968, s. 1–2
- ^ Biliotti, Jha & Johnson 2001, str. 508
- ^ Termín lineární prostor se také používá k označení vektorových prostorů, ale to málokdy způsobí zmatek.
- ^ Moorhouse 2007, str. 5
- ^ Druhá konvence indexování řádků po řádcích a sloupců podle bodů je také široce používána.
- ^ A b Beth, Jungnickel a Lenz 1986, str. 17
- ^ Pisanski & Servatius 2013, str. 222
- ^ E. Steinitz (1894), Über die Construction der Configurationen n3„Dizertační práce, Vratislav
- ^ Gropp, Harald (1997), „Konfigurace a jejich realizace“, Diskrétní matematika, 174: 137–151, doi:10.1016 / s0012-365x (96) 00327-5
- ^ Levi, F. W. (1942), Konečné geometrické systémy, Kalkata: University of Kalkata, PAN 0006834
- ^ Coxeter, H.S.M. (1950), „Self-dual configurations and regular graphs“, Bulletin of the American Mathematical Society, 56: 413–455, doi:10.1090 / s0002-9904-1950-09407-5
- ^ A b Pisanski & Servatius 2013, str. 158
Reference
- Beth, Thomas; Jungnickel, Dieter; Lenz, Hanfried (1986), Teorie designu, Cambridge University Press, ISBN 3-411-01675-2
- Biliotti, Mauro; Jha, Vikram; Johnson, Norman L. (2001), Základy překladových rovin, Marcel Dekker, ISBN 0-8247-0609-9
- Colbourn, Charles J .; Dinitz, Jeffrey H. (2007), Příručka kombinatorických vzorů (2. vyd.), Boca Raton: Chapman & Hall / CRC, ISBN 1-58488-506-8
- Dembowski, Peter (1968), Konečné geometrie, Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 44, Berlín, New York: Springer-Verlag, ISBN 3-540-61786-8, PAN 0233275
- G. Eric Moorhouse (2014) Geometrie dopadu přes John Baez na University of California, Riverside
- Pisanski, Tomaž; Servatius, Brigitte (2013), Konfigurace z grafického hlediskaSpringer, doi:10.1007/978-0-8176-8364-1, ISBN 978-0-8176-8363-4
Další čtení
- CRC Press (2000). Příručka diskrétní a kombinatorické matematiky, (Kapitola 12.2), ISBN 0-8493-0149-1
- Harold L. Dorwart (1966) Geometrie dopadu, Prentice Hall