Это не официальный сайт wikipedia.org 01.01.2023

Спичечный граф — Википедия
Википедия

Спичечный граф

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

Граф Харборта

Регулярные спичечные графыПравить

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

 
Наименьший 3-регулярный спичечный граф.

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

 
Граф 8-угольной призмы с пересечениями.

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

Невозможно для регулярного спичечного графа иметь степень больше чем четыре[4].

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

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

Проверка, можно ли представить заданный неориентированный планарный граф в виде спичечного графа, является NP-трудной задачей[6][7]

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

Число различных (с точностью до изоморфизма) спичечных графов известно вплоть до десяти рёбер[8][9]:

1, 1, 3, 5, 12, 28, 74, 207, 633, 2008, …

ПримечанияПравить

  1. ↑ 1 2 Weisstein, Eric W. MatchstickGraph (англ.) на сайте Wolfram MathWorld.
  2. ↑ Heiko Harborth. The Lighter Side of Mathematics: Proceedings of the Eugéne Strens Memorial Conference of Recreational Mathematics and its History, Calgary, Canada, 1986 / R. K. Guy, R. E. Woodrow. — Washington, D. C.: Mathematical Association of America, 1994. — С. 281—288.. Как цитировано в Weisstein, Eric W. HarborthGraph (англ.) на сайте Wolfram MathWorld.
  3. ↑ Gerbracht E. H.-A. Minimal polynomials for the coordinates of the Harborth graph. — 2006. — arXiv:math.CO/0609360.
  4. ↑ Sascha Kurz, Rom Pinchasi. Regular matchstick graphs // American Mathematical Monthly. — 2011. — Т. 118, вып. 3. — С. 264—267. — doi:10.4169/amer.math.monthly.118.03.264.
  5. ↑ Kurz Sascha, Mazzuoccolo Giuseppe. 3-regular matchstick graphs with given girth // Geombinatorics. — 2010. — Т. 19. — С. 156—175.
  6. ↑ Peter Eades, Nicholas C. Wormald. Fixed edge-length graph drawing is NP-hard // Discrete Applied Mathematics. — 1990. — Т. 28, вып. 2. — С. 111—134. — doi:10.1016/0166-218X(90)90110-X.
  7. ↑ Sergio Cabello, Erik D. Demaine, Günter Rote. Planar embeddings of graphs with specified edge lengths // Journal of Graph Algorithms and Applications. — 2007. — Т. 11, вып. 1. — С. 259—276.
  8. ↑ Последовательность A066951 в OEIS = Number of nonisomorphic connected graphs that can be drawn in the plane using n unit-length edges
  9. ↑ Raffaele Salvia. A catalog for matchstick graphs. — 2013. — arXiv:1303.5965.
Источник — https://ru.wikipedia.org/w/index.php?title=Спичечный_граф&oldid=118519347