Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Уникальный график наименьших кубических спичек
Граф Харборта
Граф Харборта vector.svg
Вершины52
Края104
Радиус6
Диаметр9
Обхват3
Таблица графиков и параметров
3-регулярный график спичек
Винклер 3-рег обхват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]

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

Комбинаторное перечисление [ править ]

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

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

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

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

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

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

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

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

Связанные классы графиков [ править ]

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

Ссылки [ править ]

  1. ^ a b Вайсштейн, Эрик В. «Граф спичек» . MathWorld .
  2. ^ Harborth, Хайко (1994), "Совпадение палки в плоскости", в Гай, РК; Вудро, RE (ред.), The Light Side of Mathematics: Proceedings of the Eugéne Strens Memorial Conference of Recreational Mathematics and its History, Calgary, Canada, 1986 , Washington, DC: Mathematical Association of America , pp. 281–288. Как цитируется в: Weisstein, Eric W. «Граф спичек» . MathWorld .
  3. ^ Гербрахт, Эберхард Х.-А. (2011), "Символ-хруст Harborth график", Достижения в области прикладной математики , 47 (2): 276-281, DOI : 10.1016 / j.aam.2010.09.003 , МР 2803803 . Дополнительные сведения см. В более раннем препринте Гербрахта «Минимальные многочлены для координат графа Харборта» (2006 г.), arXiv: math / 0609360 .
  4. ^ а б Курц, Саша; Пинчаси, Ром (2011), «Обычные графики спичек», American Mathematical Monthly , 118 (3): 264–267, arXiv : 1401.4372 , doi : 10.4169 / amer.math.monthly.118.03.264 , MR 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. ^ Идс, Питер ; Wormald, Николас С. (1990), "Fixed край длина график рисунок NP-трудный", Дискретная прикладная математика , 28 (2): 111-134, DOI : 10.1016 / 0166-218X (90) 90110-X.
  9. ^ Кабельо, Серджио; Демейн, Эрик Д .; Роте, Гюнтер (2007), «Планарные вложения графов с заданной длиной ребер» (PDF) , Журнал алгоритмов и приложений графов , 11 (1): 259–276, doi : 10.7155 / jgaa.00145 .
  10. ↑ Абель, Захарий; Демейн, Эрик Д .; Демейн, Мартин Л .; Айзенстат, Сара; Линч, Джейсон; Шардл, Тао Б. (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.
  11. ^ Курц, Саша (2011), «Быстрое распознавание плоских графов с неединичными расстояниями», Геомбинаторика , 21 (1): 25–33, arXiv : 1401.4375 , MR 2858668 .
  12. ^ Итаи, Алон; Пападимитриу, Христос Х .; Szwarcfiter, Джейм Луис (1982), "Гамильтон пути в графах сетки", SIAM журнал по вычислениям , 11 (4): 676-686, DOI : 10,1137 / 0211056 , MR 0677661 .
  13. ^ Сальвия, Раффаэле (2013), Каталог для графиков спички , arXiv : 1303.5965
  14. ^ Vaisse, Alexis (2015). «Графы спичек до 10 ребер» .
  15. ^ Fruchterman, Томас MJ; Рейнгольд, Эдвард М. (1991), «Рисование графиков путем размещения под действием силы», Программное обеспечение - практика и опыт , Wiley, 21 (11): 1129–1164, doi : 10.1002 / spe.4380211102.
  16. ^ Карлсон, Иосия; Эпштейн, Дэвид (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.
  17. ^ Эппштейн, Дэвид; Вортман, Кевин А. (2011), «Оптимальное угловое разрешение для рисунков с симметричным лицом», Журнал алгоритмов и приложений графов , 15 (4): 551–564, arXiv : 0907.5474 , doi : 10.7155 / jgaa.00238.