Pravidelná mapa (teorie grafů) - Regular map (graph theory)

v matematika, a běžná mapa je symetrický mozaikování uzavřené povrch. Přesnější, běžná mapa je a rozklad dvojrozměrného potrubí (například a koule, torus nebo skutečná projektivní rovina ) na topologické disky tak, aby každý vlajka (incident triple-edge-face-triple) lze transformovat na jakýkoli jiný příznak pomocí a symetrie rozkladu. Pravidelné mapy jsou v jistém smyslu topologické zobecnění Platonické pevné látky. Teorie map a jejich klasifikace souvisí s teorií Riemannovy povrchy, hyperbolická geometrie, a Galoisova teorie. Pravidelné mapy se klasifikují podle: rod a orientovatelnost nosné plochy, podkladový graf, nebo automorfická skupina.
Přehled
Pravidelné mapy jsou obvykle definovány a studovány třemi způsoby: topologicky, skupinově teoreticky a graficky teoreticky.
Topologický přístup
Topologicky je mapa a 2článková rozklad uzavřeného kompaktního 2-potrubí.
Rod g mapy M je dán vztahem Eulerův vztah což se rovná pokud je mapa orientovatelná, a pokud je mapa neorientovatelná. Je zásadním faktem, že pro každý orientovatelný rod kromě torusu existuje konečný (nenulový) počet pravidelných map.
Skupinový teoretický přístup
Seskupte teoreticky permutační zastoupení běžné mapy M je tranzitivní permutační skupina C, na setu z vlajky, generovaný třemi volnými involucemi s pevným bodem r0, r1, r2 uspokojující (r0r2)2= I. V této definici jsou tváře oběžné dráhy F = <r0, r1>, hrany jsou oběžné dráhy E = <r0, r2> a vrcholy jsou oběžné dráhy PROTI = <r1, r2>. Více abstraktně, skupina automorfismu každé pravidelné mapy je nedegenerovaný, homomorfní obraz a <2, m, n> -skupina trojúhelníků.
Graficko-teoretický přístup
Graf - teoreticky, mapa je kubický graf s okraji zbarvenými modře, žlutě, červeně tak, aby: je připojen, každý vrchol dopadá na jeden okraj každé barvy a cykly okrajů, které nejsou zbarveny žlutě, mají délku 4. Všimněte si, že je příznakový graf nebo graficky zakódovaná mapa (GEM) mapy, definované na vrcholové sadě vlajek a není kostrou G = (V, E) mapy. Obecně platí, že || = 4 | E |.
Mapa M je pravidelná, pokud Aut (M) činy pravidelně na vlajky. Aut (M) pravidelné mapy je přechodný na vrcholech, hranách a tváříchM. Mapa M se říká, že je reflexní, pokud Aut (M) je pravidelný a obsahuje automorfismus který opravuje vrcholproti a obličejF, ale obrátí pořadí hran. Říká se, že mapa, která je pravidelná, ale ne reflexivní chirální.
Příklady

- The velký dvanáctistěn je pravidelná mapa s pětiúhelníkovými tvářemi v orientovatelném povrchu rodu 4.
- The hemicube je běžná mapa typu {4,3} v projektivní rovina.
- The hemi-dodecahedron je pravidelná mapa vytvořená pětiúhelníkovým vložením Petersenova grafu do projektivní roviny.
- P-hosohedron je běžná mapa typu {2, p}.
- The Dyck mapa je běžná mapa 12 osmiúhelníků na povrchu rodu-3. Jeho základní graf, Dyckův graf, může také tvořit běžnou mapu 16 šestiúhelníků v torusu.
Následuje úplný seznam pravidelných map v povrchech pozitivních Eulerova charakteristika, χ: koule a projektivní rovina.[1]
χ | G | Schläfli | Vert. | Hrany | Tváře | Skupina | Objednat | Graf | Poznámky | |
---|---|---|---|---|---|---|---|---|---|---|
2 | 0 | {p, 2} | p | p | 2 | C2 × Dihp | 4p | Cp | ![]() | Dihedron |
2 | 0 | {2, str} | 2 | p | p | C2 × Dihp | 4p | p-složit K.2 | Hosohedron | |
2 | 0 | {3,3} | 4 | 6 | 4 | S4 | 24 | K.4 | ![]() | Čtyřstěn |
2 | 0 | {4,3} | 8 | 12 | 6 | C2 × S.4 | 48 | K.4 × K.2 | ![]() | Krychle |
2 | 0 | {3,4} | 6 | 12 | 8 | C2 × S.4 | 48 | K.2,2,2 | ![]() | Octahedron |
2 | 0 | {5,3} | 20 | 30 | 12 | C2 × A5 | 120 | ![]() | Dodecahedron | |
2 | 0 | {3,5} | 12 | 30 | 20 | C2 × A5 | 120 | K.6 × K.2 | ![]() | Dvacetistěnu |
1 | n1 | {2p, 2} / 2 | p | p | 1 | Dih2p | 4p | Cp | ![]() | Hemi-dihedron[2] |
1 | n1 | {2,2p} / 2 | 2 | p | p | Dih2p | 4p | p-složit K.2 | Hemi-hosohedron[2] | |
1 | n1 | {4,3}/2 | 4 | 6 | 3 | S4 | 24 | K.4 | ![]() | Hemicube |
1 | n1 | {3,4}/2 | 3 | 6 | 4 | S4 | 24 | 2krát K.3 | Hemioctahedron | |
1 | n1 | {5,3}/2 | 10 | 15 | 6 | A5 | 60 | Petersenův graf | ![]() | Hemidodekedr |
1 | n1 | {3,5}/2 | 6 | 15 | 10 | A5 | 60 | K.6 | ![]() | Hemi-icosahedron |
Na následujících obrázcích jsou tři z 20 běžných map v trojitý torus, označené jejich Schläfliho symboly.
{6,4}
{4,8}
{8,4}
Toroidní mnohostěn
![]() {4,4}1,0 (v: 1, e: 2, f: 1) | ![]() {4,4}1,1 (v: 2, e: 4, f: 2) | ![]() {4,4}2,0 (v: 4, e: 8, f: 4) | ![]() {4,4}2,1 (v: 5, e: 10, f: 5) | ![]() {4,4}2,2 (v: 8, e: 16, f: 8) |
![]() {3,6}1,0 (v: 1, e: 3, f: 2) | ![]() {3,6}1,1 (v: 3, e: 9, f: 6) | ![]() {3,6}2,0 (v: 4, e: 8, f: 8) | ![]() {3,6}2,1 (v: 7, e: 21, f: 14) | ![]() {3,6}2,2 (v: 12, e: 36, f: 24) |
![]() {6,3}1,0 (v: 2, e: 3, f: 1) | ![]() {6,3}1,1 (v: 6, e: 9, f: 3) | ![]() {6,3}2,0 (v: 8, e: 8, f: 4) | ![]() {6,3}2,1 (v: 14, e: 21, f: 7) | ![]() {6,3}2,2 (v: 24, e: 36, f: 12) |
Pravidelné mapy existují jako torohedrální mnohostěny jako konečné části euklidovských obkladů, zabalené na povrch duocylinder jako plochý torus. Jsou označeny jako {4,4}b,C pro ty, kteří souvisejí s čtvercové obklady, {4,4}.[3] {3,6}b,C souvisí s trojúhelníkové obklady, {3,6} a {6,3}b,C související s šestihranný obklad, {6,3}. b a C jsou celá čísla.[4] Existují 2 speciální případy (b, 0) a (b,b) s reflexní symetrií, zatímco obecné případy existují u chirálních párů (b,C) a (C,b).
Pravidelné mapy formuláře {4,4}m,0 lze reprezentovat jako konečný pravidelný zkosený mnohostěn {4,4 | m}, viděný jako čtvercové plochy a m×m duoprism ve 4 rozměrech.
Zde je příklad {4,4}8,0 mapováno z letadla jako šachovnice do části válce do torusu. Projekce z válce do torusu deformuje geometrii ve 3 rozměrech, ale lze ji provést bez zkreslení ve 4 rozměrech.

χ | G | Schläfli | Vert. | Hrany | Tváře | Skupina | Objednat | Poznámky |
---|---|---|---|---|---|---|---|---|
0 | 1 | {4,4}b,0 n=b2 | n | 2n | n | [4,4](b,0) | 8n | Plochý toroidní mnohostěn Stejné jako {4,4 | b} |
0 | 1 | {4,4}b,b n=2b2 | n | 2n | n | [4,4](b,b) | 8n | Plochý toroidní mnohostěn Stejné jako opravené {4,4 | b} |
0 | 1 | {4,4}b,C n=b2+C2 | n | 2n | n | [4,4]+ (b,C) | 4n | Plochá chirální toroidní mnohostěna |
0 | 1 | {3,6}b,0 t=b2 | t | 3t | 2t | [3,6](b,0) | 12t | Plochý toroidní mnohostěn |
0 | 1 | {3,6}b,b t=2b2 | t | 3t | 2t | [3,6](b,b) | 12t | Plochý toroidní mnohostěn |
0 | 1 | {3,6}b,C t=b2+před naším letopočtem+C2 | t | 3t | 2t | [3,6]+ (b,C) | 6t | Plochá chirální toroidní mnohostěna |
0 | 1 | {6,3}b,0 t=b2 | 2t | 3t | t | [3,6](b,0) | 12t | Plochý toroidní mnohostěn |
0 | 1 | {6,3}b,b t=2b2 | 2t | 3t | t | [3,6](b,b) | 12t | Plochý toroidní mnohostěn |
0 | 1 | {6,3}b,C t=b2+před naším letopočtem+C2 | 2t | 3t | t | [3,6]+ (b,C) | 6t | Plochá chirální toroidní mnohostěna |
V obecně pravidelném toroidním mnohostěnu {p,q}b,C lze definovat pokud p nebo q jsou sudé, i když pouze euklidovské výše mohou existovat jako toroidní mnohostěny ve 4 rozměrech. V {2p,q}, cesty (b,C) lze definovat jako krokování face-edge-face v přímkách, zatímco dual {p,2q} formuláře uvidí cesty (b,C) jako krokovací vrchol-hrana-vrchol v přímkách.
Viz také
- Topologická teorie grafů
- Abstraktní mnohostěn
- Rovinný graf
- Toroidní graf
- Vkládání grafů
- Pravidelné obklady
- Platonická pevná látka
- Platonický graf
Reference
- ^ Coxeter (1980)
- ^ A b Séquin, Carlo. „Symetrické ponoření neorientovatelných pravidelných map nízkého rodu“ (PDF). Berkeley University.
- ^ Coxeter 1980, 8.3 Mapy typu {4,4} na torusu.
- ^ Coxeter 1980, 8.4 Mapy typu {3,6} nebo {6,3} na torusu.
- ^ Coxeter a Moser, Generátory a vztahy pro jednotlivé skupiny, 1957, kapitola 8, Pravidelné mapy, 8.3 Mapy typu {4,4} na torusu, 8.4 Mapy typu {3,6} nebo {6,3} na torusu
- Coxeter, H. S. M.; Moser, W. O. J. (1980), Generátory a vztahy pro jednotlivé skupiny, Ergebnisse der Mathematik und ihrer Grenzgebiete, 14 (4. vydání), Springer Verlag, ISBN 978-0-387-09212-6.
- van Wijk, Jarke J. (2009), „Symetrický obklad uzavřených ploch: vizualizace běžných map“ (PDF), Proc. SIGGRAPH (Transakce ACM na grafice), 28 (3): 12, doi:10.1145/1531326.1531355, archivovány z originál (PDF ) dne 09.06.2011.
- Conder, Marstone; Dobcsányi, Peter (2001), „Určení všech pravidelných map malého rodu“, Journal of Combinatorial Theory, Series B, 81 (2): 224–242, doi:10.1006 / jctb.2000.2008.
- Nedela, Roman (2007), Mapy, hypermapy a související témata (PDF).
- Vince, Andrew (2004), „Mapy“, Příručka teorie grafů.
- Brehm, Ulrich; Schulte, Egon (2004), „Polyhedral Maps“, Příručka diskrétní a výpočetní geometrie.