График спичек - Matchstick graph

Уникальный самый маленький кубический график спички
Граф Харборта
Граф Харборта vector.svg
Вершины52
Края104
Радиус6
Диаметр9
Обхват3
Таблица графиков и параметров
3-регулярный график спичек
Winkler 3-reg обхват5 54.svg
Вершины54
Края81
Обхват5
Таблица графиков и параметров

В геометрическая теория графов, раздел математики, график спичек представляет собой граф, который можно нарисовать на плоскости таким образом, что его ребра представляют собой отрезки прямой длины, которые не пересекают друг друга. То есть это граф, вложение которого одновременно является график единичного расстояния и плоский график. Неформально, графики спичек можно построить, поместив непересекающиеся спички на плоской поверхности, отсюда и название.[1]

Графики регулярных спичек

Большая часть исследований графиков спичек касается регулярные графики, в котором каждая вершина имеет одинаковое количество соседей. Этот номер называется степень графа.

Известно, что существуют спичечные графы, регулярные любой степени до 4. полные графики с одной, двумя и тремя вершинами (одна вершина, одно ребро и треугольник) все являются графами спичек и являются 0-, 1- и 2-регулярными соответственно. Наименьший 3-регулярный Граф спичек формируется из двух копий ромбовидный график размещены таким образом, чтобы соответствующие вершины находились на единичном расстоянии друг от друга; это двусторонняя двойная обложка это 8-граф с пересеченной призмой.[1]

В 1986 г. Хайко Харборт представил граф, который будет носить его имя, График Харборта. Имея 104 ребра и 52 вершины, это наименьший из известных примеров 4-обычный график спичек.[2] Это жесткий граф.[3]

Каждый 4-регулярный спичечный граф содержит не менее 20 вершин.[4] Примеры 4-регулярных спичечных графов в настоящее время известны для любого числа вершин ≥ 52, за исключением 53, 55, 56, 58, 59, 61 и 62. Графы с 54, 57, 65, 67, 73, 74, 77 и 85 вершин были впервые опубликованы в 2016 году. Для 52, 54, 57, 60 и 64 вершин известен только один пример. Из этих пяти графов только один с 60 вершинами является гибким, остальные четыре - жесткими.[5]

Обычный график из спичек не может иметь степень выше четырех.[4] Наименьший 3-регулярный граф спичек без треугольников (обхват ≥ 4) имеет 20 вершин, как доказали Курц и Маццуокколо.[6]Самый маленький известный пример 3-регулярного графа спичек обхвата 5 имеет 54 вершины и впервые был представлен Майком Винклером в 2019 году.[7]

Вычислительная сложность

это NP-жесткий чтобы проверить, может ли данный неориентированный планарный граф быть реализован как граф спички.[8][9] Точнее, эта проблема завершена для экзистенциальная теория реальности.[10] Курц (2011) предоставляет некоторые легко проверяемые необходимые критерии для того, чтобы граф был спичечным графом, но они также не являются достаточными критериями: граф может пройти тесты Курца и по-прежнему не быть спичечным графом.[11]

Это также НП-полный чтобы определить, есть ли у спичечного графа Гамильтонов цикл, даже если все вершины графа имеют целочисленные координаты, которые задаются как часть входных данных для задачи.[12]

Комбинаторное перечисление

Количество различных (неизоморфных) спичечных графов известно для 1, 2, 3, ... до десяти ребер; они есть:

1, 1, 3, 5, 12, 28, 74, 207, 633, 2008 (последовательность A066951 в OEIS )[13][14]

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

Специальные классы графов

Равномерность длины кромок долгое время считалась желательным качеством в рисунок графика,[15] а некоторые конкретные классы плоских графов всегда можно нарисовать с полностью однородными ребрами.

Каждый дерево может быть нарисован таким образом, что если бы края листьев дерева были заменены бесконечными лучами, рисунок разделил бы плоскость на выпуклые многоугольные области без каких-либо пересечений. Для такого чертежа, если длину каждой кромки изменить произвольно без изменения наклона кромки, рисунок останется плоским. В частности, можно выбрать все ребра одинаковой длины, что приведет к реализации произвольного дерева в виде графа спичек.[16]

Реализация квадратный граф как спичечный график

Аналогичное свойство верно для квадратные графы, плоские графы, которые можно нарисовать на плоскости таким образом, что каждая ограниченная грань является четырехугольником, а каждая вершина либо лежит на неограниченной грани, либо имеет не менее четырех соседей. Эти графы могут быть нарисованы со всеми параллелограммами граней таким образом, что если подмножество ребер, которые все параллельны друг другу, удлиняются или укорачиваются одновременно, так что все они продолжают иметь одинаковую длину, то пересечение не может быть введено. В частности, можно нормализовать ребра так, чтобы все они имели одинаковую длину, и получить реализацию любого квадратного графа в виде спичечного графа.[17]

Связанные классы графов

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

Рекомендации

  1. ^ а б Вайсштейн, Эрик В. "График спичек". MathWorld.
  2. ^ Харборт, Хейко (1994), «Спички в самолете», в Guy, R.K .; Вудроу, Р. Э. (ред.), Светлая сторона математики: материалы конференции Мемориала Эжена Стренса по развлекательной математике и ее истории, Калгари, Канада, 1986, Вашингтон, округ Колумбия.: Математическая ассоциация Америки, стр. 281–288. Как указано в: Вайсштейн, Эрик В. "График спичек". MathWorld.
  3. ^ Гербрахт, Эберхард Х.-А. (2011), «Символ графа Харборта», Успехи в прикладной математике, 47 (2): 276–281, Дои:10.1016 / j.aam.2010.09.003, МИСТЕР  2803803. Дополнительные сведения см. В более раннем препринте Гербрахта «Минимальные многочлены для координат графа Харборта» (2006 г.), arXiv: math / 0609360.
  4. ^ а б Курц, Саша; Пинчаси, Ром (2011), "Регулярные графики спичек", Американский математический ежемесячный журнал, 118 (3): 264–267, arXiv:1401.4372, Дои:10.4169 / amer.math.monthly.118.03.264, МИСТЕР  2800336.
  5. ^ Винклер, Майк; Динкелакер, Питер; Фогель, Стефан (2017), «Новые минимальные (4; n) -регулярные спичечные графы», Геомбинаторика, 27: 26–44, arXiv:1604.07134.
  6. ^ Курц, Саша; Маццуокколо, Джузеппе (2010), «3-регулярные спичечные графики с заданным обхватом», Геомбинаторика, 19: 156–175, arXiv:1401.4360.
  7. ^ Винклер, Майк; Динкелакер, Питер; Фогель, Стефан (2020), «Трехмерный граф спичек обхвата 5, состоящий из 54 вершин», Геомбинаторика, 29: 116–121, arXiv:1903.04304.
  8. ^ Идс, Питер; Вормальд, Николас С. (1990), «Рисование графа с фиксированной длиной ребра NP-сложно», Дискретная прикладная математика, 28 (2): 111–134, Дои:10.1016 / 0166-218X (90) 90110-X.
  9. ^ Кабельо, Серджио; Демейн, Эрик Д.; Роте, Гюнтер (2007), «Плоские вложения графов с заданной длиной ребер» (PDF), Журнал графических алгоритмов и приложений, 11 (1): 259–276, Дои:10.7155 / jgaa.00145.
  10. ^ Авель, Захарий; Демейн, Эрик Д.; Демейн, Мартин Л.; Айзенстат, Сара; Линч, Джейсон; Шардл, Тао Б. (2016), «Кому нужны пересечения? Жесткость плоского графа», в Фекете, Шандор; Любив, Анна (ред.), 32-й Международный симпозиум по вычислительной геометрии (SoCG 2016), Международный журнал Лейбница по информатике (LIPIcs), 51, Дагштуль, Германия: Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik, стр. 3: 1–3: 15, Дои:10.4230 / LIPIcs.SoCG.2016.3, ISBN  978-3-95977-009-5.
  11. ^ Курц, Саша (2011), "Быстрое распознавание плоских графов с неединичными расстояниями", Геомбинаторика, 21 (1): 25–33, arXiv:1401.4375, МИСТЕР  2858668.
  12. ^ Итаи, Алон; Пападимитриу, Христос Х.; Szwarcfiter, Jayme Luiz (1982), "Пути Гамильтона в сеточных графах", SIAM Журнал по вычислениям, 11 (4): 676–686, Дои:10.1137/0211056, МИСТЕР  0677661.
  13. ^ Сальвия, Рафаэле (2013), Каталог спичечных графиков, arXiv:1303.5965
  14. ^ Вайсс, Алексис (2015). «Графы спичек до 10 ребер».
  15. ^ Fruchterman, Thomas M. J .; Рейнгольд, Эдвард М. (1991), "Рисование графика путем размещения под действием силы", Программное обеспечение - практика и опыт, Wiley, 21 (11): 1129–1164, Дои:10.1002 / spe.4380211102.
  16. ^ Карлсон, Иосия; Эпштейн, Дэвид (2006), «Деревья с выпуклыми гранями и оптимальными углами», у Кауфманна, Михаэля; Вагнер, Доротея (ред.), Материалы 14-го Международного симпозиума по рисованию графиков., Конспект лекций по информатике, 4372, Springer-Verlag, стр. 77–88, arXiv:cs.CG/0607113, Дои:10.1007/978-3-540-70904-6_9, ISBN  978-3-540-70903-9, МИСТЕР  2393907.
  17. ^ Эпштейн, Дэвид; Вортман, Кевин А. (2011), «Оптимальное угловое разрешение для рисунков с симметричным лицом», Журнал графических алгоритмов и приложений, 15 (4): 551–564, arXiv:0907.5474, Дои:10.7155 / jgaa.00238.