Спичечный граф
В теории графов спичечным графом называется граф, который можно нарисовать на плоскости таким образом, что все его рёбра представляют собой отрезки прямой длиной единица и рёбра не пересекаются. Таким образом, этот граф имеет вложение в плоскость одновременно в виде графа единичных расстояний и планарного графа.
Говоря неформально, спичечный граф можно выложить непересекающимися на плоской поверхности спичками, откуда и название[1].
Содержание
Регулярные спичечные графы
Много исследований спичечных графов касается регулярных графов, в которых каждая вершина имеет одинаковое число соседей. Это число называется степенью графа.
Известно, что существуют спичечные графы всех степеней вплоть до четвёртой. Полные графы с одной, двумя и тремя вершинами (отдельная вершина, ребро и треугольник) являются спичечными графами, 0-, 1- и 2-регулярными соответственно. Наименьший 3-регулярный спичечный граф образуется двумя копиями ромбов, расположенных так, что соответствующие вершины располагаются на единичном расстоянии. Его двойное двудольное покрытие[en] — это граф 8-угольной призмы с пересечениями[1].
В 1986 году Хейко Харборт представил граф, который получил его имя — граф Харборта. Имея 104 ребра и 52 вершины, этот граф является наименьшим известным примером 4-регулярного спичечного графа[2]. Граф является жёстким[3].
Невозможно для регулярного спичечного графа иметь степень больше чем четыре[4].
Как показали Курц и Мазуколо[5], наименьший 3-регулярный спичечный граф без треугольников (обхват ≥ 4) имеет 20 вершин. Кроме того, они представили наименьший известный пример 3-регулярного спичечного графа с обхватом 5 (180 вершин).
Вычислительная сложность
Проверка, можно ли представить заданный неориентированный планарный граф в виде спичечного графа, является NP-трудной задачей[6][7]
Комбинаторное перечисление
Число различных (с точностью до изоморфизма) спичечных графов известно вплоть до десяти рёбер[8][9]:
Напишите отзыв о статье "Спичечный граф"
Примечания
- ↑ 1 2 Weisstein, Eric W. [mathworld.wolfram.com/.html MatchstickGraph] (англ.) на сайте Wolfram MathWorld.
- ↑ 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. [mathworld.wolfram.com/.html HarborthGraph] (англ.) на сайте Wolfram MathWorld.
- ↑ Gerbracht E. H.-A. Minimal polynomials for the coordinates of the Harborth graph. — 2006. — arXiv:math.CO/0609360.
- ↑ Sascha Kurz, Rom Pinchasi Regular matchstick graphs // American Mathematical Monthly. — 2011. — Т. 118, вып. 3. — С. 264—267. — DOI:10.4169/amer.math.monthly.118.03.264.
- ↑ Kurz Sascha, Mazzuoccolo Giuseppe 3-regular matchstick graphs with given girth // Geombinatorics. — 2010. — Т. 19. — С. 156—175.
- ↑ 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.
- ↑ 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.
- ↑ Последовательность A066951 в OEIS = Number of nonisomorphic connected graphs that can be drawn in the plane using n unit-length edges
- ↑ Raffaele Salvia A catalog for matchstick graphs. — 2013. — arXiv:1303.5965.
<imagemap>: неверное или отсутствующее изображение |
Для улучшения этой статьи желательно?:
|
Отрывок, характеризующий Спичечный граф
– Я тебе говорю – вздор, еще молоко не обсохло, а в военную службу хочет! Ну, ну, я тебе говорю, – и граф, взяв с собой бумаги, вероятно, чтобы еще раз прочесть в кабинете перед отдыхом, пошел из комнаты.– Петр Кириллович, что ж, пойдем покурить…
Пьер находился в смущении и нерешительности. Непривычно блестящие и оживленные глаза Наташи беспрестанно, больше чем ласково обращавшиеся на него, привели его в это состояние.
– Нет, я, кажется, домой поеду…
– Как домой, да вы вечер у нас хотели… И то редко стали бывать. А эта моя… – сказал добродушно граф, указывая на Наташу, – только при вас и весела…
– Да, я забыл… Мне непременно надо домой… Дела… – поспешно сказал Пьер.
– Ну так до свидания, – сказал граф, совсем уходя из комнаты.
– Отчего вы уезжаете? Отчего вы расстроены? Отчего?.. – спросила Пьера Наташа, вызывающе глядя ему в глаза.
«Оттого, что я тебя люблю! – хотел он сказать, но он не сказал этого, до слез покраснел и опустил глаза.
– Оттого, что мне лучше реже бывать у вас… Оттого… нет, просто у меня дела.
– Отчего? нет, скажите, – решительно начала было Наташа и вдруг замолчала. Они оба испуганно и смущенно смотрели друг на друга. Он попытался усмехнуться, но не мог: улыбка его выразила страдание, и он молча поцеловал ее руку и вышел.
Пьер решил сам с собою не бывать больше у Ростовых.
Петя, после полученного им решительного отказа, ушел в свою комнату и там, запершись от всех, горько плакал. Все сделали, как будто ничего не заметили, когда он к чаю пришел молчаливый и мрачный, с заплаканными глазами.
На другой день приехал государь. Несколько человек дворовых Ростовых отпросились пойти поглядеть царя. В это утро Петя долго одевался, причесывался и устроивал воротнички так, как у больших. Он хмурился перед зеркалом, делал жесты, пожимал плечами и, наконец, никому не сказавши, надел фуражку и вышел из дома с заднего крыльца, стараясь не быть замеченным. Петя решился идти прямо к тому месту, где был государь, и прямо объяснить какому нибудь камергеру (Пете казалось, что государя всегда окружают камергеры), что он, граф Ростов, несмотря на свою молодость, желает служить отечеству, что молодость не может быть препятствием для преданности и что он готов… Петя, в то время как он собирался, приготовил много прекрасных слов, которые он скажет камергеру.
Петя рассчитывал на успех своего представления государю именно потому, что он ребенок (Петя думал даже, как все удивятся его молодости), а вместе с тем в устройстве своих воротничков, в прическе и в степенной медлительной походке он хотел представить из себя старого человека. Но чем дальше он шел, чем больше он развлекался все прибывающим и прибывающим у Кремля народом, тем больше он забывал соблюдение степенности и медлительности, свойственных взрослым людям. Подходя к Кремлю, он уже стал заботиться о том, чтобы его не затолкали, и решительно, с угрожающим видом выставил по бокам локти. Но в Троицких воротах, несмотря на всю его решительность, люди, которые, вероятно, не знали, с какой патриотической целью он шел в Кремль, так прижали его к стене, что он должен был покориться и остановиться, пока в ворота с гудящим под сводами звуком проезжали экипажи. Около Пети стояла баба с лакеем, два купца и отставной солдат. Постояв несколько времени в воротах, Петя, не дождавшись того, чтобы все экипажи проехали, прежде других хотел тронуться дальше и начал решительно работать локтями; но баба, стоявшая против него, на которую он первую направил свои локти, сердито крикнула на него:
