A kombinatorikus térkép egy kombinatorikus objektum, amely részt vesz objektumokra bontott topológiai struktúrák modellezésében . A legegyszerűbb változat a sík térkép , a síkbeli gráfok síkbeli ábrázolásának kombinatorikus szerkezete .
A kombinatorikus térkép koncepcióját az 1960-as évek elején informálisan vezette be Jack Edmonds a sokszögű felületek modellezésére . Az első hivatalos kártyakifejezést Alain Jacques konstelláció néven adta meg, de a fogalmat már korábban is széles körben használták, forgás néven , Gerhard Ringel és John William Theodore Youngs a színezés problémájának híres megoldásában . Heawood kártyák . Ez a kombinatorikus térkép név (angolul " kombinatorikus térkép " ), amelyet általában használnak. A koncepciót kibővítették, hogy képes legyen orientálható felosztott objektumok magasabb dimenzióban való ábrázolására.
A kombinatorikus térképeket hatékony adatstruktúrákként használják a képábrázoláshoz és -feldolgozáshoz, valamint a geometriai modellezéshez. A számítógépes grafikában ezt a modellt B-Rep modellnek hívják, mivel az objektumokat szélük szerint ábrázolja. A modell egyszerűsítő komplexekkel és kombinatorikus topológiával függ össze . A kombinatorikus térképek kiterjeszthetők úgynevezett generalizált térképekre, amelyek lehetővé teszik olyan nem orientálható objektumok ábrázolását is, mint a Möbius-szalag vagy a Klein-palack .
Különböző alkalmazások olyan adatstruktúrát igényelnek, amely az objektum felosztását reprezentálhatja. Például egy kétdimenziós objektum bomlik csúcsokká (0 dimenziós cellák), élekké (1 dimenziós cellák) és arcokká (2 dimenziós cellák). Ezenkívül gyakran szükség van az e sejtek közötti szomszédsági viszonyok ábrázolására.
A cél a felosztás összes sejtjének ismertetése, továbbá az e sejtek közötti összes incidencia és szomszédsági viszony . Ha az összes sejt szimplex, egy egyszerű komplexet lehet használni, de általában sejt topológiai modelleket, például kombinatorikus vagy általános térképeket használunk.
A kombinatorikus térképekkel kapcsolatos első munka kifejlesztette a grafikonok ábrázolását a felületeken, amelyek különösen sík grafikonokat tartalmaznak : A 2. dimenzió kombinatorikus térképe egy olyan szerkezet , ahol
Intuitív módon egy ilyen térkép megfelel egy felületre rajzolt grafikonnak, ahol minden él két részre oszlik (néha "féléleknek" is). A permutáció minden szál esetében megadja a következő szálat a csúcs pozitív irányba történő megfordulásával; a másik permutáció minden szálhoz ugyanazon él ellentétes szálát adja. A permutáció ciklusai lehetővé teszik a gráf éleinek és a csúcsok ciklusainak megkeresését . Mi határozza meg egy harmadik permutáció által
.Ez a permutáció minden szál esetében megadja a következő szálat ugyanazon az arcon; így a ciklusok azonosulnak az ábrázolás arcával. Esettől függően használhatjuk az ábrázolást, vagy amelyek ekvivalensek . A két ábrázolás kettős abban az értelemben, hogy csúcsokat és arcokat cserélnek.
A térkép akkor és csak akkor síkbeli, ha a csúcsok és az arcok számának összege megegyezik az élek számával plusz 2-vel.
A sík térkép egy összekapcsolt és sík gráf beágyazása a gömbön, folyamatos deformációig tekinthető. Bár a gömbön van meghatározva, inkább a síkba rajzoljuk a térképeket. Az egyik arc ezután kiváltságos, a külső arc. Az alábbi példában a külső felület az (1 3 18 16 14 12 10).
Síkgrafikon
Síkbeli térkép csúcsok és élek szerint
Síktérkép arcok és élek szerint
1 | 2 | 3 | 4 | 5. | 6. | 7 | 8. | 9. | 10. | 11. | 12. | 13. | 14 | 15 | 16. | 17. | 18. | |
2 | 1 | 4 | 3 | 6. | 5. | 8. | 7 | 10. | 9. | 12. | 11. | 14 | 13. | 16. | 15 | 18. | 17. | |
7 | 3 | 2 | 18. | 4 | 15 | 9. | 6. | 1 | 11. | 10. | 13. | 12. | 8. | 14 | 17. | 16. | 5. | |
3 | 7 | 18. | 2 | 15 | 4 | 6. | 9. | 11. | 1 | 13. | 10. | 8. | 12. | 17. | 14 | 5. | 16. |
A sík térképek számlálása Tutte munkájára nyúlik vissza. A bijektív kombinatorikus megközelítés az 1980-as évek elején kezdődött, különösen a bordeaux-i kombinatorika iskola fejlesztette ki. Ezt szemlélteti a "négyértékű" sík térképek (ahol minden csúcs 4 fokos) felsorolása n csúcssal: ez a szám
Ez a képlet a fák családjával kapcsolatos bijekcióra utal; ez a fajta bijekció jön létre, amely megmutatja azt is, hogy e számok generáló sorozatai algebrai. Más kérelmeket adtak.
A meghatározás a kombinatorikus térkép kiterjed minden olyan dimenzió: kombinatorikus térkép dimenzió olyan szerkezet , ahol
Egy kombinatorikus térkép dimenzió n jelentése alegységének egy orientálható zárt terét dimenzió n . A szál absztrakt elem, amelyet a bijekciók definiálására használnak. Az utolsó feltétel korlátai garantálják az ábrázolt objektum topológiai koherenciáját: a kombinatorikus térkép kvázi sokrétűséget képvisel.