График спичек

График спичек 3-регулярного обхвата 5
График спичек 3-регулярного обхвата 5
Вершины	54
Края	81
Обхват	5
	Таблица графиков и параметров

График Харборта
График Харборта
Вершины	52
Края	104
Радиус	6
Диаметр	9
Обхват	3
	Таблица графиков и параметров

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

Обычные спичечные графики

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

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

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

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

Обычный спичечный граф не может иметь степень больше четырех. ^[5] Сильнее, каждый $n$ -вершинный граф из спичек имеет $\Omega ({\sqrt {n}})$ вершины степени четыре или меньше. ^[8] Самый маленький 3-правильный граф из спичек без треугольников (обхват ≥ 4) имеет 20 вершин, как доказали Курц и Маццуокколо. ^[9]Самый маленький известный пример 3-регулярного спичечного графа обхвата 5 имеет 54 вершины и впервые был представлен Майком Винклером в 2019 году. ^[10]

Максимальное количество ребер в спичечном графе $n$ вершины могут иметь $\left\lfloor 3n-{\sqrt {12n-3}}\right\rfloor$ . ^[11]

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

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

Также NP-полным является определение того, имеет ли спичечный граф гамильтонов цикл , даже если все вершины графа имеют целочисленные координаты, которые задаются как часть входных данных для задачи. ^[16]

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

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

1, 1, 3, 5, 12, 28, 74, 207, 633, 2008, 6774, 23868, 87667 (последовательность A066951 в OEIS ) ^[17]^[18]

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

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

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

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

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

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

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

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

Ссылки

^ Джервасио, Северино В.; Лим, Иветт Ф.; Маэхара, Хироши (2008), «Плоские графы единичных расстояний, имеющие плоское дополнение единичных расстояний», Discrete Mathematics , 308 (10): 1973–1984, doi : 10.1016/j.disc.2007.04.050 , MR 2394465
^ Jump up to: ^а ^б Вайсштейн, Эрик В. , «График из спичек» , MathWorld
^ Харборт, Хейко (1994), «Спички в самолете», Гай, РК; Вудро, Р.Э. (ред.), Светлая сторона математики: материалы конференции по развлекательной математике и ее истории, посвященной памяти Юджина Стренса, Калгари, Канада, 1986 , Вашингтон, округ Колумбия: Математическая ассоциация Америки , стр. 281–288 . Как цитируется в: Вайсштейн, Эрик В. , «График из спичек» , MathWorld
^ Гербрахт, Эберхард Х.-А. (2011), «Разработка символов на графе Харборта», «Достижения в области прикладной математики» , 47 (2): 276–281, doi : 10.1016/j.aam.2010.09.003 , MR 2803803 . Дополнительную информацию см. в предыдущем препринте в Гербрахт, Эберхард Х.-А. (2006), «Минимальные полиномы для координат графа Харборта», arXiv : math/0609360 .
^ Jump up to: ^а ^б Курц, Саша; Пинчаси, Ром (2011), «Регулярные спичечные графики», American Mathematical Monthly , 118 (3): 264–267, arXiv : 1401.4372 , doi : 10.4169/amer.math.monthly.118.03.264 , MR 2800336 , S2CID 866740 .
^ Винклер, Майк; Динкелакер, Питер; Фогель, Стефан (2017), «Новые минимальные (4; n)-регулярные спичечные графы», Geombinatorics , 27 : 26–44, arXiv : 1604.07134 .
^ Винклер, Майк; Динкелакер, Питер; Фогель, Стефан (2017), О существовании 4-регулярных спичечных графов , arXiv : 1705.00293 .
^ Лаволле, Жереми; Свейнпол, Конрад Дж. (2023), «Количество вершин малой степени в спичечных графах», Австралазийский журнал комбинаторики , 85 : 92–99, arXiv : 2206.03956 , MR 4515475
^ Курц, Саша; Маццуокколо, Джузеппе (2010), «3-регулярные спичечные графы заданного обхвата», Geombinatorics , 19 : 156–175, arXiv : 1401.4360 .
^ Винклер, Майк; Динкелакер, Питер; Фогель, Стефан (2020), «Трёхрегулярный спичечный граф обхвата 5, состоящий из 54 вершин», Geombinatorics , 29 : 116–121, arXiv : 1903.04304 .
^ Лаволле, Жереми; Свейнпол, Конрад (18 августа 2023 г.), «Точная граница числа ребер спичечных графов», Дискретная и вычислительная геометрия , arXiv : 2209.09800 , doi : 10.1007/s00454-023-00530-z , ISSN 1432-0444
^ Идс, Питер ; Вормальд, Николас К. (1990), «Рисование графа с фиксированной длиной ребра NP-сложно», Discrete Applied Mathematics , 28 (2): 111–134, doi : 10.1016/0166-218X(90)90110-X .
^ Кабельо, Серджио; Демейн, Эрик Д .; Роте, Гюнтер (2007), «Плоские вложения графов с заданными длинами ребер» (PDF) , Journal of Graph Algorithms and Applications , 11 (1): 259–276, doi : 10.7155/jgaa.00145 (неактивно с 2024 г.) 29) {{citation}}:CS1 maint: DOI неактивен по состоянию на июль 2024 года ( ссылка ) .
^ Авель, Закари; Демейн, Эрик Д .; Демейн, Мартин Л .; Эйзенштат, Сара; Линч, Джейсон; Шардл, Тао Б. (2016), «Кому нужны пересечения? Твердость жесткости плоского графа», в Фекете, Шандор; Любив, Анна (ред.), 32-й Международный симпозиум по вычислительной геометрии (SoCG 2016) , Международные труды Лейбница по информатике (LIPIcs), том. 51, Дагштуль, Германия: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, стр. 3:1–3:15, doi : 10.4230/LIPIcs.SoCG.2016.3 , ISBN 978-3-95977-009-5 .
^ Курц, Саша (2011), «Быстрое распознавание плоских графов неединичных расстояний», Geombinatorics , 21 (1): 25–33, arXiv : 1401.4375 , MR 2858668 .
^ Итай, Алон; Пападимитриу, Христос Х .; Шварцфитер, Хайме Луис (1982), «Пути Гамильтона в сеточных графах», SIAM Journal on Computing , 11 (4): 676–686, CiteSeerX 10.1.1.383.1078 , doi : 10.1137/0211056 , MR 0677661 .
^ Сальвиа, Раффаэле (2013), «Каталог спичечных графиков», arXiv : 1303.5965 [ math.CO ]
^ Вайссе, Алексис (2023), Спичечные графы с числом ребер до 13
^ Фрухтерман, Томас М.Дж.; Рейнгольд, Эдвард М. (1991), «Построение графика путем принудительного размещения», Software: Practice and Experience , 21 (11), Wiley: 1129–1164, doi : 10.1002/spe.4380211102 , S2CID 31468174 .
^ Карлсон, Джозайя; Эппштейн, Дэвид (2006), «Деревья с выпуклыми гранями и оптимальными углами», Кауфманн, Майкл; Вагнер, Доротея (ред.), Труды 14-го Международного симпозиума по рисованию графиков , Конспекты лекций по информатике, том. 4372, Springer-Verlag, стр. 77–88, arXiv : cs.CG/0607113 , doi : 10.1007/978-3-540-70904-6_9 , ISBN 978-3-540-70903-9 , МР 2393907 , S2CID 12598338 .
^ Эппштейн, Дэвид; Вортман, Кевин А. (2011), «Оптимальное угловое разрешение для лице-симметричных рисунков», Журнал графовых алгоритмов и приложений , 15 (4): 551–564, arXiv : 0907.5474 , doi : 10.7155/jgaa.00238 (неактивен в 2024 г.) -07-29), S2CID 10356432 {{citation}}:CS1 maint: DOI неактивен по состоянию на июль 2024 года ( ссылка ) .

[1] Джервасио, Северино В.; Лим, Иветт Ф.; Маэхара, Хироши (2008), «Плоские графы единичных расстояний, имеющие плоское дополнение единичных расстояний», Discrete Mathematics , 308 (10): 1973–1984, doi : 10.1016/j.disc.2007.04.050 , MR 2394465

[mmg-2] Jump up to: ^а ^б Вайсштейн, Эрик В. , «График из спичек» , MathWorld

[mhg-3] Харборт, Хейко (1994), «Спички в самолете», Гай, РК; Вудро, Р.Э. (ред.), Светлая сторона математики: материалы конференции по развлекательной математике и ее истории, посвященной памяти Юджина Стренса, Калгари, Канада, 1986 , Вашингтон, округ Колумбия: Математическая ассоциация Америки , стр. 281–288 . Как цитируется в: Вайсштейн, Эрик В. , «График из спичек» , MathWorld

[4] Гербрахт, Эберхард Х.-А. (2011), «Разработка символов на графе Харборта», «Достижения в области прикладной математики» , 47 (2): 276–281, doi : 10.1016/j.aam.2010.09.003 , MR 2803803 . Дополнительную информацию см. в предыдущем препринте в Гербрахт, Эберхард Х.-А. (2006), «Минимальные полиномы для координат графа Харборта», arXiv : math/0609360 .

[Kurz,Pinchasi,2011-5] Jump up to: ^а ^б Курц, Саша; Пинчаси, Ром (2011), «Регулярные спичечные графики», American Mathematical Monthly , 118 (3): 264–267, arXiv : 1401.4372 , doi : 10.4169/amer.math.monthly.118.03.264 , MR 2800336 , S2CID 866740 .

[6] Винклер, Майк; Динкелакер, Питер; Фогель, Стефан (2017), «Новые минимальные (4; n)-регулярные спичечные графы», Geombinatorics , 27 : 26–44, arXiv : 1604.07134 .

[7] Винклер, Майк; Динкелакер, Питер; Фогель, Стефан (2017), О существовании 4-регулярных спичечных графов , arXiv : 1705.00293 .

[8] Лаволле, Жереми; Свейнпол, Конрад Дж. (2023), «Количество вершин малой степени в спичечных графах», Австралазийский журнал комбинаторики , 85 : 92–99, arXiv : 2206.03956 , MR 4515475

[9] Курц, Саша; Маццуокколо, Джузеппе (2010), «3-регулярные спичечные графы заданного обхвата», Geombinatorics , 19 : 156–175, arXiv : 1401.4360 .

[10] Винклер, Майк; Динкелакер, Питер; Фогель, Стефан (2020), «Трёхрегулярный спичечный граф обхвата 5, состоящий из 54 вершин», Geombinatorics , 29 : 116–121, arXiv : 1903.04304 .

[11] Лаволле, Жереми; Свейнпол, Конрад (18 августа 2023 г.), «Точная граница числа ребер спичечных графов», Дискретная и вычислительная геометрия , arXiv : 2209.09800 , doi : 10.1007/s00454-023-00530-z , ISSN 1432-0444

[12] Идс, Питер ; Вормальд, Николас К. (1990), «Рисование графа с фиксированной длиной ребра NP-сложно», Discrete Applied Mathematics , 28 (2): 111–134, doi : 10.1016/0166-218X(90)90110-X .

[13] Кабельо, Серджио; Демейн, Эрик Д .; Роте, Гюнтер (2007), «Плоские вложения графов с заданными длинами ребер» (PDF) , Journal of Graph Algorithms and Applications , 11 (1): 259–276, doi : 10.7155/jgaa.00145 (неактивно с 2024 г.) 29) {{citation}}:CS1 maint: DOI неактивен по состоянию на июль 2024 года ( ссылка ) .

[14] Авель, Закари; Демейн, Эрик Д .; Демейн, Мартин Л .; Эйзенштат, Сара; Линч, Джейсон; Шардл, Тао Б. (2016), «Кому нужны пересечения? Твердость жесткости плоского графа», в Фекете, Шандор; Любив, Анна (ред.), 32-й Международный симпозиум по вычислительной геометрии (SoCG 2016) , Международные труды Лейбница по информатике (LIPIcs), том. 51, Дагштуль, Германия: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, стр. 3:1–3:15, doi : 10.4230/LIPIcs.SoCG.2016.3 , ISBN 978-3-95977-009-5 .

[15] Курц, Саша (2011), «Быстрое распознавание плоских графов неединичных расстояний», Geombinatorics , 21 (1): 25–33, arXiv : 1401.4375 , MR 2858668 .

[16] Итай, Алон; Пападимитриу, Христос Х .; Шварцфитер, Хайме Луис (1982), «Пути Гамильтона в сеточных графах», SIAM Journal on Computing , 11 (4): 676–686, CiteSeerX 10.1.1.383.1078 , doi : 10.1137/0211056 , MR 0677661 .

[17] Сальвиа, Раффаэле (2013), «Каталог спичечных графиков», arXiv : 1303.5965 [ math.CO ]

[18] Вайссе, Алексис (2023), Спичечные графы с числом ребер до 13

[19] Фрухтерман, Томас М.Дж.; Рейнгольд, Эдвард М. (1991), «Построение графика путем принудительного размещения», Software: Practice and Experience , 21 (11), Wiley: 1129–1164, doi : 10.1002/spe.4380211102 , S2CID 31468174 .

[20] Карлсон, Джозайя; Эппштейн, Дэвид (2006), «Деревья с выпуклыми гранями и оптимальными углами», Кауфманн, Майкл; Вагнер, Доротея (ред.), Труды 14-го Международного симпозиума по рисованию графиков , Конспекты лекций по информатике, том. 4372, Springer-Verlag, стр. 77–88, arXiv : cs.CG/0607113 , doi : 10.1007/978-3-540-70904-6_9 , ISBN 978-3-540-70903-9 , МР 2393907 , S2CID 12598338 .

[21] Эппштейн, Дэвид; Вортман, Кевин А. (2011), «Оптимальное угловое разрешение для лице-симметричных рисунков», Журнал графовых алгоритмов и приложений , 15 (4): 551–564, arXiv : 0907.5474 , doi : 10.7155/jgaa.00238 (неактивен в 2024 г.) -07-29), S2CID 10356432 {{citation}}:CS1 maint: DOI неактивен по состоянию на июль 2024 года ( ссылка ) .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]