Kombinatorisk karta

En kombinatorisk karta är en kombinatorisk representation av en graf på en orienterbar yta. En kombinatorisk karta kan också kallas en kombinatorisk inbäddning , ett rotationssystem , en orienterbar bandgraf , en fet graf eller en cyklisk graf. Mer generellt är en $n$ -dimensionell kombinatorisk karta en kombinatorisk representation av en graf på ett $n$ -dimensionellt orienterbart grenrör.

Kombinatoriska kartor används som effektiva datastrukturer i bildrepresentation och bearbetning , i geometrisk modellering. Denna modell är relaterad till enkla komplex och till kombinatorisk topologi . En kombinatorisk karta är en gränsrepresentationsmodell ; den representerar objekt genom sina gränser.

Historia

Konceptet med en kombinatorisk karta introducerades informellt av J. Edmonds för polyedriska ytor som är plana grafer . Det fick sitt första definitiva formella uttryck under namnet "Constellations" av A. Jacques, men konceptet användes redan flitigt under namnet "rotation" av Gerhard Ringel och JWT Youngs i deras berömda lösning av Heawoods kartfärgningsproblem. Termen "konstellation" behölls inte och istället gynnades "kombinatorisk karta".

Kombinatoriska kartor generaliserades senare för att representera högre dimensionella orienterbara underuppdelade objekt.

Motivering

Flera applikationer kräver en datastruktur för att representera underindelningen av ett objekt. Till exempel kan ett 2D-objekt delas upp i hörn (0-celler), kanter (1-celler) och ytor (2-celler). Mer generellt är ett n-dimensionellt objekt sammansatt av celler med dimension 0 till n. Dessutom är det också ofta nödvändigt att representera närliggande relationer mellan dessa celler.

Därför vill vi beskriva alla celler i underavdelningen, plus alla förekomst och närliggande relationer mellan dessa celler. När alla representerade celler är simplexar kan ett enkelt komplex användas, men när vi vill representera vilken typ av celler som helst måste vi använda cellulära topologiska modeller som kombinatoriska kartor eller generaliserade kartor.

Definition

En kombinatorisk karta är en triplett M = ( D , σ , α ) så att:

D är en ändlig uppsättning pilar;
σ är en permutation på D ;
α är en involution på D utan någon fixpunkt.

Intuitivt motsvarar en kombinatorisk karta en graf där varje kant är uppdelad i två pilar (ibland även kallade halvkanter). Permutationen σ ger, för varje pil, nästa pil genom att vrida runt vertexen i positiv orientering; den andra permutationen α ger, för varje pil, den andra pilen av samma kant.

α tillåter en att hämta kanter ( en lpha för en rête på franska), och σ låter en hämta hörn ( s igma för s ommet på franska). Vi definierar φ = σ o α som ger, för varje pil, nästa pil i samma ansikte ( p hi för ansikte också på franska).

Så det finns två sätt att representera en kombinatorisk karta beroende på om permutationen är σ eller φ (se exempel nedan). Dessa två representationer är dubbla till varandra: hörn och ansikten är utbytta.

**Exempel på kombinatoriska kartor** : en plan graf och de två kombinatoriska kartorna beroende på om vi använder notationen ( D , σ , α ) eller ( D , φ , α ).
En plan graf	Motsvarande kombinatorisk karta ( D , σ , α ). Pilar representeras av numrerade segment, σ av grå pilar (exempel σ (1)=7), två pilar sammanlänkade med α ritas i följd och separeras av en liten stapel (exempel α (1)=2).	Motsvarande kombinatorisk karta ( D , φ , α ). Pilar representeras av numrerade pilar, två pilar länkade med φ ritas i följd (exempel φ (1)=3) och två pilar länkade av α ritas parallellt och i omvänd orientering (exempel α (1)=2).

Högdimensionell generalisering

En n -dimensionell kombinatorisk karta (eller n -karta) är en ( n + 1)-tuppel M = ( D , β ₁ , ..., β _n ) så att:

D är en ändlig uppsättning pilar;
P1 är en permutation på D _;
β2 _, ... , βn _är involutioner på D ;
β _i o β _j är en involution om i + 2 ≤ j ( i , j ∈ { 1, ,..., n }).

En n -dimensionell kombinatorisk karta representerar underindelningen av ett slutet orienterbart n -dimensionellt utrymme. Restriktionen på β _i o β _j garanterar den topologiska giltigheten av kartan som en kvasi-manifold underavdelning. Tvådimensionella kombinatoriska kartor kan hämtas genom att fixera n = 2 och byta namn på σ med β ₁ och α med β ₂ .

Utrymmen som inte nödvändigtvis är stängda eller orienterbara kan representeras med ( n -dimensionella) generaliserade kartor .

Se även

externa länkar

Kombinatoriska kartor i CGAL , Computational Geometry Algorithms Library:
- Damiand, Guillaume. "Kombinatoriska kartor" . Hämtad 6 februari 2021 .

Kombinatoriska kartor i CGoGN , kombinatoriska och geometriska modellering med generiska N - dimensionella kartor
Kombinatorisk karta på n Lab