Bir kombinatoryal harita , nesnelere bölünmüş topolojik yapıların modellenmesinde yer alan kombinatoryal bir nesnedir . En basit versiyon, düzlemdeki düzlemsel grafiklerin gösterimi için bir kombinatoryal yapı olan düzlemsel haritadır .
Kombinatoryal harita kavramı , çok yüzlü yüzeylerin modellenmesi için 1960'ların başında Jack Edmonds tarafından gayri resmi olarak tanıtıldı . Kartların ilk resmi ifadesi adı altında Alain Jacques tarafından verildi takımyıldızı ancak kavram zaten adı altında, yoğun önce kullanılmış olan rotasyon tarafından, Gerhard Ringel ve John William Theodore Youngs sorununa kendi ünlü çözeltide boyama arasında İyi kartlar . Bu, yaygın olarak kullanılan kombinatoryal harita ( İngilizce " kombinatoryal harita " ) adıdır . Konsept, yönlendirilebilir alt bölümlere ayrılmış nesneleri daha yüksek boyutta temsil edebilecek şekilde genişletildi.
Kombinatoryal haritalar, görüntü gösterimi ve işleme için ve geometrik modellemede verimli veri yapıları olarak kullanılır. Bilgisayar grafiklerinde bu model, nesneleri kenarlarından temsil ettiği için B-Rep modeli olarak adlandırılır . Model, basit kompleksler ve kombinatoryal topoloji ile ilgilidir . Kombinasyonel haritaları , Möbius şeridi veya Klein şişesi gibi yönlendirilemeyen nesneleri temsil etmeyi de mümkün kılan genelleştirilmiş haritalara genişletebiliriz .
Çeşitli uygulamalar, bir nesnenin alt bölümlerini temsil edebilen bir veri yapısı gerektirir. Örneğin, 2 boyutlu bir nesne köşelere (0 boyutlu hücreler), kenarlara (1 boyutlu hücreler) ve yüzlere (2 boyutlu hücreler) ayrıştırılabilir. Ek olarak, bu hücreler arasındaki komşuluk ilişkilerini temsil etmek çoğu zaman gereklidir.
Amaç, alt bölümdeki tüm hücreleri ve ayrıca bu hücreler arasındaki tüm geliş ve bitişik ilişkileri tanımlamaktır . Temsil edilen tüm hücreler simpleks olduğunda, basit bir kompleks kullanılabilir, ancak genel durumda, kombinatoryal haritalar veya genelleştirilmiş haritalar gibi hücre topolojik modelleri kullanılır.
Kombinatoryal haritalar üzerindeki ilk çalışma, belirli düzlemsel grafiklerde bulunan yüzeyler üzerindeki grafiklerin bir temsilini geliştirmiştir : Boyut 2'nin bir kombinatoryal haritası , burada bir yapıdır.
Sezgisel olarak, böyle bir harita, bir yüzey üzerine çizilen bir grafiğe karşılık gelir; burada her kenar, iki şerit halinde alt bölümlere ayrılmıştır (bazen "yarım kenarlar" da denir). Permütasyon , tepe noktasının etrafında pozitif yönde döndürülerek her bir iplikçik için bir sonraki ipliği verir; diğer permütasyon , her iplik için aynı kenarın zıt ipliğini verir. Permütasyon döngüleri , grafiğin kenarlarını ve köşelerinin döngülerini bulmayı mümkün kılar . Üçüncü bir permütasyonu şu şekilde tanımlıyoruz :
.Bu permütasyon, her tel için aynı yüzdeki bir sonraki ipliği verir; böylece, döngüleri temsilin yüzleriyle tanımlanır. Duruma bağlı olarak, temsili veya o zamandan beri eşdeğer olanı kullanabiliriz . İki temsil, köşeleri ve yüzleri değiş tokuş etme anlamında ikili.
Bir harita, ancak ve ancak köşe sayısının ve yüzlerin sayısının toplamı kenarların sayısı artı 2'ye eşitse düzlemseldir.
Düzlemsel harita, sürekli deformasyona kadar düşünülen, küre üzerindeki bağlantılı ve düzlemsel bir grafiğin gömülü halidir. Küre üzerinde tanımlanmasına rağmen, haritaları düzlemde çizmeyi tercih ediyoruz. Yüzlerden biri daha sonra ayrıcalıklı hale gelir, dış yüz. Aşağıdaki örnekte, dış yüz (1 3 18 16 14 12 10).
Düzlemsel grafik
Köşelere ve kenarlara göre düzlemsel harita
Yüzlere ve kenarlara göre düzlemsel harita
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 |
Düzlemsel haritaların sayımı Tutte'nin çalışmalarına kadar uzanmaktadır. Biyolojik kombinatoryal yaklaşım , özellikle Bordeaux kombinatorik okulu tarafından geliştirilen, 1980'lerin başında başladı. Bunun bir örneği, "dört değerlikli" düzlemsel haritaların (her köşe 4. dereceden) n köşeli numaralandırılmasıdır: bu sayı
Bu formül bir ağaç ailesiyle bir çiftleşme önermektedir; bu sayı dizilerinin üreten serilerinin cebirsel olduğunu da göstermek için kurulmuş olan bu tür önyargılardır. Diğer uygulamalar verilmiştir.
Bir kombinatoryal harita tanımı herhangi bir boyut kapsar: bir birleştirici harita boyutunun bir yapıdır ,
Boyuta bir kombinatoryal harita n boyutunun bir yönlendirilebilir kapalı alan bir alt grubu temsil eder , n . Bir iplikçik, önyargıları tanımlamak için kullanılan soyut bir unsurdur. Son koşulun kısıtlamaları, temsil edilen nesnenin topolojik tutarlılığını garanti eder: bir kombinatoryal harita, bir yarı-manifoldu temsil eder.