Комбинаторная карта

Комбинаторное отображение — это комбинаторное представление графа на ориентируемой поверхности. Комбинаторное отображение также можно назвать комбинаторным вложением , системой вращения , ориентируемым ленточным графом , толстым графом или циклическим графом. ^[1] В более общем смысле, $n$ -мерное комбинаторное отображение является комбинаторным представлением графа на $n$ -мерное ориентируемое многообразие.

Комбинаторные карты используются как эффективные структуры данных при представлении и обработке изображений , при геометрическом моделировании. Эта модель связана с симплициальными комплексами и комбинаторной топологией . Комбинаторная карта — это модель представления границ ; он представляет объект по его границам.

История

Понятие комбинаторного отображения было неофициально введено Дж. Эдмондсом для многогранных поверхностей. ^[2] которые являются плоскими графами . Свое первое определенное формальное выражение оно получило под названием «Созвездия» А. Жака. ^[3]^[4] но эта концепция уже широко использовалась под названием «вращение» Герхардом Рингелем. ^[5] и Дж. У. Т. Янгса в их знаменитом решении проблемы раскраски карт Хивуда. Термин «созвездие» не был сохранен, а вместо него было отдано предпочтение «комбинаторной карте». ^[6]

Позже комбинаторные карты были обобщены для представления ориентируемых подразделенных объектов более высокой размерности.

Мотивация

Некоторым приложениям требуется структура данных для представления подразделения объекта. Например, 2D-объект можно разложить на вершины (0 ячеек), ребра (1 ячейки) и грани (2 ячейки). В более общем смысле n-мерный объект состоит из ячеек размерностью от 0 до n. Более того, часто также необходимо представлять соседские отношения между этими ячейками.

Таким образом, мы хотим описать все ячейки подразделения, а также все отношения инцидентности и смежности между этими ячейками. Когда все представленные ячейки являются симплексами, можно использовать симплициальный комплекс , но когда мы хотим представить ячейки любого типа, нам необходимо использовать клеточные топологические модели, такие как комбинаторные карты или обобщенные карты.

Определение

Комбинаторное отображение — это тройка $M = (D, σ, α)$ такая, что:

$D$ — конечное множество дротиков;
$σ$ является перестановкой на $D$ ?
$α$ — инволюция на $D$ без неподвижной точки.

Интуитивно, комбинаторное отображение соответствует графу, в котором каждое ребро разделено на два дротика (иногда их также называют полуребрами). Перестановка $σ$ дает для каждого дротика следующий дротик, поворачивая вершину в положительной ориентации; другая перестановка $α$ дает для каждого дротика другой дротик того же края.

$α$ позволяет извлекать ребра ( lpha для rête на французском языке), а $σ$ позволяет извлекать вершины ( sigma для sommet на французском языке). Мы определяем $φ = σ \circ α$ , что дает для каждого дротика следующий дротик с той же гранью ( phi для лица также на французском языке).

Итак, существует два способа представления комбинаторного отображения в зависимости от того, является ли перестановка $σ$ или $φ$ (см. пример ниже). Эти два представления двойственны друг другу: вершины и грани поменяны местами.

**Пример комбинаторных карт** : плоский граф и две комбинаторные карты в зависимости от того, используем ли мы обозначение $(D, σ, α)$ или $(D, φ, α)$ .
Плоский граф	Соответствующее комбинаторное отображение $(D, σ, α)$ . Дротики представлены пронумерованными сегментами, $σ$ — серыми стрелками (пример $σ (1) = 7$ ), два дротика, соединенные символом $α$ , нарисованы последовательно и разделены небольшой полоской (пример $α (1) = 2$ ).	Соответствующее комбинаторное отображение $(D, φ, α)$ . Дротики представлены пронумерованными стрелками, два дротика, связанные символом $φ,$ нарисованы последовательно (пример $φ (1) = 3$ ), а два дротика, связанные символом $α,$ нарисованы параллельно и в обратной ориентации (пример $α (1) = 2$ ).

Многомерное обобщение

- мерное n комбинаторное отображение (или n -отображение) представляет собой ( n + 1)-кортеж $M = (D, β 1, ..., β n)$ такой, что: ^[7]^[8]

$D$ — конечное множество дротиков;
$β 1$ — перестановка на $D$ ;
$β 2, ..., β n$ — инволюции на $D$ ;
$β i \circ β j$ является инволюцией, если $я + 2 \leq j (я, j \in { 1, ,..., n})$ .

n - мерное комбинаторное отображение представляет собой подразделение замкнутого ориентируемого n -мерного пространства. Ограничение на $β i \circ β j$ гарантирует топологическую достоверность отображения как подразделения квазимногообразия. Двумерные комбинаторные карты можно получить, зафиксировав $n = 2$ и переименовав $σ$ на $β 1$ и $α$ на $β 2$ .

Пространства, которые не обязательно замкнуты или ориентируемы, могут быть представлены с помощью ( n -мерных) обобщенных карт .

См. также

Ссылки

^ Боллобас, Бела; Риордан, Оливер (2001). «Полиномиальный инвариант графов на ориентируемых поверхностях». Труды Лондонского математического общества . 83 (3). Уайли: 513–531. дои : 10.1112/plms/83.3.513 . ISSN 0024-6115 . S2CID 15895860 .
^ Эдмондс, Дж. (1960). «Комбинаторное представление многогранных поверхностей». Замечания амер. Математика. Соц . 7 . hdl : 1903/24820 .
^ Жак, А. (1969). Созвездия и алгебраические свойства топологических графов (доктор философии). Парижский университет.
^ Жак, А. (1970). «Созвездия и топологические графы». Математическая конференция. Соц. Янош Боляи : 657–672.
^ Рингель, Г. (2012) [1974]. Теорема о цвете карты . Спрингер. ISBN 978-3-642-65759-7 .
^ Кори, Р. (1975). «Код для плоских графов и его приложения» . Звездочка . 27 . МР 0404045 . Збл 0313.05115 .
^ Линхардт, П. (1991). «Топологические модели представления границ: сравнение с n-мерными обобщенными картами». Компьютерное проектирование . 23 (1): 59–82. дои : 10.1016/0010-4485(91)90082-8 .
^ Линхардт, П. (1994). «N-мерные обобщенные комбинаторные отображения и клеточные квазимногообразия». Международный журнал вычислительной геометрии и приложений . 4 (3): 275–324. дои : 10.1142/S0218195994000173 .

Внешние ссылки

Комбинаторные карты в CGAL , библиотеке алгоритмов вычислительной геометрии:
- Дамиан, Гийом. «Комбинаторные отображения» . Проверено 6 февраля 2021 г.

в CGoGN , Комбинаторное и геометрическое моделирование использованием с общих Комбинаторные отображения N - отображений мерных
Комбинаторная карта в n Lab

[br01-1] Боллобас, Бела; Риордан, Оливер (2001). «Полиномиальный инвариант графов на ориентируемых поверхностях». Труды Лондонского математического общества . 83 (3). Уайли: 513–531. дои : 10.1112/plms/83.3.513 . ISSN 0024-6115 . S2CID 15895860 .

[2] Эдмондс, Дж. (1960). «Комбинаторное представление многогранных поверхностей». Замечания амер. Математика. Соц . 7 . hdl : 1903/24820 .

[3] Жак, А. (1969). Созвездия и алгебраические свойства топологических графов (доктор философии). Парижский университет.

[4] Жак, А. (1970). «Созвездия и топологические графы». Математическая конференция. Соц. Янош Боляи : 657–672.

[5] Рингель, Г. (2012) [1974]. Теорема о цвете карты . Спрингер. ISBN 978-3-642-65759-7 .

[6] Кори, Р. (1975). «Код для плоских графов и его приложения» . Звездочка . 27 . МР 0404045 . Збл 0313.05115 .

[7] Линхардт, П. (1991). «Топологические модели представления границ: сравнение с n-мерными обобщенными картами». Компьютерное проектирование . 23 (1): 59–82. дои : 10.1016/0010-4485(91)90082-8 .

[8] Линхардт, П. (1994). «N-мерные обобщенные комбинаторные отображения и клеточные квазимногообразия». Международный журнал вычислительной геометрии и приложений . 4 (3): 275–324. дои : 10.1142/S0218195994000173 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]