Перевернуть график
Граф, кодирующий локальные операции в математике
Графы переворота четырехугольника (вверху слева), пятиугольника (вверху справа) и шестиугольника (внизу).
Примеры переворотов в измерении 1 (справа вверху), 2 (слева вверху и в центральном ряду) и 3 (нижний ряд).

В математике флип-граф — это граф , вершины которого являются комбинаторными или геометрическими объектами, а ребра связывают два из этих объектов, когда они могут быть получены друг из друга с помощью элементарной операции, называемой флипом. Флип-графы являются частными случаями геометрических графов .

Среди заметных флип-графов можно найти 1-скелет многогранников, таких как ассоциэдры [1] или циклоэдры [2] .

Примеры

Прототипический флип-граф — это выпуклый -угольник . Вершины этого графа — триангуляции , и две триангуляции смежны в нем, если они отличаются одним внутренним ребром. В этом случае операция флипа заключается в обмене диагоналями выпуклого четырехугольника. Эти диагонали — внутренние ребра, которыми отличаются две смежные в флип-графе триангуляции. Полученный флип-граф является как диаграммой Хассе решетки Тамари [ 3] , так и 1-скелетом -мерного ассоциаэдра . [1] н {\displaystyle n} π {\displaystyle \пи} π {\displaystyle \пи} ( н − 3 ) {\displaystyle (n-3)}

Эту базовую конструкцию можно обобщить несколькими способами.

Конечные множества точек в евклидовом пространстве

Пусть будет триангуляцией конечного множества точек . При некоторых условиях можно преобразовать в другую триангуляцию с помощью флипа. Эта операция состоит в изменении способа триангуляции контура (минимально аффинно зависимого подмножества ). Точнее, если некоторая триангуляция контура является подмножеством , и если все ячейки (грани максимальной размерности) из имеют одинаковую связь в , то можно выполнить флип внутри , заменив на , где Т {\displaystyle Т} А ⊂ Р г {\displaystyle {\mathcal {A}}\subset \mathbb {R} ^{d}} Т {\displaystyle Т} А {\displaystyle {\mathcal {A}}} Т {\displaystyle Т} А {\displaystyle {\mathcal {A}}} τ − {\displaystyle \тау ^{-}} з ⊂ А {\displaystyle z\subset {\mathcal {A}}} Т {\displaystyle Т} τ − {\displaystyle \тау ^{-}} λ {\displaystyle \лямбда} Т {\displaystyle Т} Т {\displaystyle Т} λ ⋆ τ − {\displaystyle \lambda {\mathord {\star }}\tau ^{-}} λ ⋆ τ + {\displaystyle \lambda {\mathord {\star }}\tau ^{+}}

Х ⋆ И = { х ∪ у : ( х , у ) ∈ Х × И } , {\displaystyle X{\mathord {\star }}{Y}=\{x\cup {y}:(x,y)\in {X{\mathord {\times }}{Y}}\},}

и является, по теореме Радона о разбиении , единственной другой триангуляцией . Только что сформулированные условия, при которых возможен флип, гарантируют, что эта операция приводит к триангуляции . [4] Соответствующий флип-граф, вершины которого являются триангуляциями , а ребра соответствуют флипам между ними, является естественным обобщением флип-графа выпуклого многоугольника, поскольку два флип-графа совпадают, когда — множество вершин выпуклого -угольника. τ + {\displaystyle \тау ^{+}} з {\displaystyle z} А {\displaystyle {\mathcal {A}}} А {\displaystyle {\mathcal {A}}} А {\displaystyle {\mathcal {A}}} н {\displaystyle n}

Топологические поверхности

Другой вид флип-графов получается путем рассмотрения триангуляции топологической поверхности : [5] рассмотрим такую ​​поверхность , поместим на нее конечное число точек и соединим их дугами таким образом, что никакие две дуги никогда не пересекутся. Когда этот набор дуг максимален, он распадается на треугольники. Если вдобавок нет ни кратных дуг ( различных дуг с той же парой вершин), ни петель , этот набор дуг определяет триангуляцию . С {\displaystyle {\mathcal {S}}} н {\displaystyle n} С {\displaystyle {\mathcal {S}}} С {\displaystyle {\mathcal {S}}}

В этом случае две триангуляции, которые могут быть получены друг из друга с помощью непрерывного преобразования, идентичны. С {\displaystyle {\mathcal {S}}}

Две триангуляции связаны переворотом, когда они отличаются ровно на одну из дуг, из которых они состоят. Обратите внимание, что эти две триангуляции обязательно имеют одинаковое количество вершин. Как и в евклидовом случае, переворотный граф — это граф, вершинами которого являются триангуляции с вершинами и чьи ребра соответствуют переворотам между ними. Это определение можно напрямую распространить на ограниченные топологические поверхности . С {\displaystyle {\mathcal {S}}} С {\displaystyle {\mathcal {S}}} н {\displaystyle n}

Граф переворота поверхности обобщает граф переворота -угольника , поскольку они совпадают, когда поверхность представляет собой топологический диск с точками, расположенными на его границе. н {\displaystyle n} н {\displaystyle n}

Другие перевернутые графики

Ряд других флип-графов можно определить с помощью альтернативных определений триангуляции. Например, флип-граф, вершины которого являются центрально-симметричными триангуляциями -угольника , а ребра соответствуют операции выполнения двух центрально-симметричных флипов, является 1-скелетом -мерного циклоэдра . [2] Можно также рассмотреть альтернативный флип-граф топологической поверхности , определенный путем разрешения множественных дуг и петель в триангуляциях этой поверхности. ( 2 г + 2 ) {\displaystyle (2d+2)} г {\displaystyle д}

Графы переворотов также могут быть определены с использованием комбинаторных объектов, отличных от триангуляции. Примером таких комбинаторных объектов являются плитки домино заданной области на плоскости. В этом случае переворот может быть выполнен, когда две соседние кости домино покрывают квадрат: он заключается в повороте этих костей домино на 90 градусов вокруг центра квадрата, что приводит к другой плитке домино той же области.

Характеристики

Политопальность

Помимо ассоциэдров и циклоэдров , ряд многогранников обладают свойством, что их 1-скелет является флип-графом. Например, если — конечное множество точек в , то регулярные триангуляции — это те, которые могут быть получены путем проецирования некоторых граней -мерного многогранника на . Подграф, индуцированный этими триангуляциями в флип-графе , является 1-скелетом многогранника , вторичного многогранника . [6 ] А {\displaystyle {\mathcal {A}}} Р г {\displaystyle \mathbb {R} ^{d}} А {\displaystyle {\mathcal {A}}} ( г + 1 ) {\displaystyle (d+1)} Р г {\displaystyle \mathbb {R} ^{d}} А {\displaystyle {\mathcal {A}}} А {\displaystyle {\mathcal {A}}}

Связанность

Политопальные флип-графы, по этому свойству, связаны . Как показал Клаус Вагнер в 1930-х годах, флип-граф топологической сферы связан. [7] Среди связных флип-графов можно также найти флип-графы любого конечного 2-мерного множества точек. [8] В евклидовых пространствах более высокой размерности ситуация гораздо сложнее. Конечные множества точек с несвязными флип-графами были найдены, когда не менее 5. [4] [9] [10] Р г {\displaystyle \mathbb {R} ^{d}} г {\displaystyle д}

Известно , что граф переворотов множества вершин 4-мерного гиперкуба связен. [11] Однако пока неизвестно, всегда ли связны графы переворотов конечных 3- и 4-мерных множеств точек. [4]

Диаметр

Максимальное число переворотов, необходимое для преобразования одной триангуляции в другую, равно диаметру переворотного графа. Диаметр переворотного графа выпуклого -угольника был получен Дэниелом Слейтором, Робертом Тарьяном и Уильямом Терстоном [12] при достаточно большом и Лайонелом Пурнином для всех . Этот диаметр равен , когда . [13] н {\displaystyle n} н {\displaystyle n} н {\displaystyle n} 2 н − 10 {\displaystyle 2n-10} н ≥ 13 {\displaystyle n\geq 13}

Диаметр других флип-графов был изучен. Например, Клаус Вагнер предоставил квадратичную верхнюю границу диаметра флип-графа множества неотмеченных точек на сфере. [7] Текущая верхняя граница диаметра равна , [14] в то время как наиболее известная нижняя граница равна . [15] Диаметр флип-графов произвольных топологических поверхностей с границей также был изучен и известен точно в нескольких случаях. [16] [17] [18] н {\displaystyle n} 5.2 н − 33.6 {\displaystyle 5.2n-33.6} 7 н / 3 + Θ ( 1 ) {\displaystyle 7n/3+\Тета (1)}

Смотрите также

Ссылки

  1. ^ ab Lee, Carl (1989), «Ассоциаэдр и триангуляции -угольника », European Journal of Combinatorics , 10 (6): 551–560, doi : 10.1016/S0195-6698(89)80072-1 , MR  1022776 н {\displaystyle n}
  2. ^ ab Simion, Rodica (2003), "Ассоциаэдр типа B", Advances in Applied Mathematics , 30 (1–2): 2–25, doi : 10.1016/S0196-8858(02)00522-5 , MR  1979780
  3. ^ Тамари, Дов (1962), «Алгебра скобок и их перечисление», Nieuw Archief voor Wiskunde , Series 3, 10 : 131–146, MR  0146227
  4. ^ abc Де Лоэра, Хесус А .; Рамбау, Йорг; Сантос, Франциско (2010). Триангуляции, структуры для алгоритмов и приложений . Алгоритмы и вычисления в математике. Том. 25. Спрингер.
  5. ^ Negami, Seiya (1994), «Диагональные перевороты в триангуляциях поверхностей», Discrete Mathematics , 135 (1–3): 225–232, doi : 10.1016/0012-365X(93)E0101-9 , MR  1310882
  6. ^ Гельфанд, Израиль М .; Зелевинский Андрей Владимирович ; Капранов, Михаил М. (1990), "Многогранники Ньютона главных A-определителей", Советская математика - Доклады , 40 : 278–281, MR  1020882
  7. ^ аб Вагнер, Клаус (1936), «Bemerkungen zum Vierfarbenproblem», Jahresbericht der Deutschen Mathematiker-Vereinigung , 46 : 26–32
  8. ^ Лоусон, Чарльз Л. (1972), «Преобразование триангуляции», Дискретная математика , 3 : 365–372, doi : 10.1016/0012-365X(72)90093-3 , MR  0311491
  9. ^ Сантос, Франциско (2000), «Точечное множество, пространство триангуляций которого несвязно», Журнал Американского математического общества , 13 : 611–637, doi : 10.1090/S0894-0347-00-00330-1 , hdl : 10902/2584 , MR  1758756
  10. ^ Сантос, Франциско (2005), «Несвязные торические схемы Гильберта», Mathematische Annalen , 332 : 645–665, arXiv : math/0204044 , doi : 10.1007/s00208-005-0643-5, MR  2181765
  11. ^ Pournin, Lionel (2013), «Флип-граф 4-мерного куба связан», Дискретная и вычислительная геометрия , 49 : 511–530, arXiv : 1201.6543 , doi : 10.1007/s00454-013-9488-y , MR  3038527
  12. ^ Sleator, Daniel D.; Tarjan, Robert E .; Thurston, William P. (1988). «Расстояние вращения, триангуляции и гиперболическая геометрия». Журнал Американского математического общества . 1 (3): 647–681. doi : 10.1090/s0894-0347-1988-0928904-4 .
  13. ^ Pournin, Lionel (2014). «Диаметр ассоциэдров». Advances in Mathematics . 259 : 13–42. arXiv : 1207.6296 . doi : 10.1016/j.aim.2014.02.035 . MR  3197650.
  14. ^ Бозе, Просенжит; Вердоншот, Сандер (2012). «История переворотов в комбинаторных триангуляциях». Конспект лекций по информатике . Берлин, Гейдельберг: Springer Berlin Heidelberg. стр. 29–44. doi :10.1007/978-3-642-34191-5_3. ISBN 978-3-642-34190-8. ISSN  0302-9743.
  15. ^ Фрати, Фабрицио (2017). «Нижняя граница диаметра флип-графа». Электронный журнал комбинаторики . 24 (1): P1.43. arXiv : 1508.03473 . doi : 10.37236/5489 .
  16. ^ Парлье, Хьюго; Пурнин, Лионель (2017). «Пространства модулей флип-графов заполняющих поверхностей». Журнал Европейского математического общества . 19 (9): 2697–2737. arXiv : 1407.1516 . doi : 10.4171/JEMS/726 .
  17. ^ Парлье, Хьюго; Пурнин, Лионель (2018). «Модулярные флип-графы поверхностей с одним отверстием». Европейский журнал комбинаторики . 67 : 158–173. arXiv : 1510.07664 . doi : 10.1016/j.ejc.2017.07.003 .
  18. ^ Парлье, Хьюго; Пурнин, Лионель (2018). «Однажды проколотые диски, невыпуклые многоугольники и пуантиэдры». Annals of Combinatorics . 22 (3): 619–640. arXiv : 1602.04576 . doi : 10.1007/s00026-018-0393-1.
Взято с "https://en.wikipedia.org/w/index.php?title=Flip_graph&oldid=1195818894"