Род, толщина, крупность, число скрещиваний

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

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

Род

Определение:

Родом (англ. genus) [math]\gamma[/math] графа [math]G[/math] называется наименьшее число ручек, которые нужно добавить к сфере, чтобы уложить [math]G[/math] на этой сфере.

Обобщённая формула Эйлера, доказанная Курантом и Роббинсоном: [math]V - E + F = 2 - 2\gamma[/math]. С её помощью можно доказать следующие утверждения.

Утверждение:

Род полного графа [math]\gamma(K_n) = \left \lceil\dfrac{(n - 3)(n - 4)}{12} \right \rceil[/math].

[math]\triangleright[/math]

Из обобщённой формулы Эйлера следует, что если граф [math]G[/math] связен, то его род [math]\gamma \geqslant \dfrac{q}{6} - \dfrac{(p - 2)}{2}[/math], где [math]q[/math] — количество рёбер, [math]p[/math] — количество вершин. Тогда [math]\gamma(K_n) \geqslant \dfrac{1}{6} \dfrac{n(n - 1)}{2} - \dfrac{(n - 2)}{2} = \dfrac{(n - 3)(n - 4)}{12}[/math]. Доказательство того, что правая часть является также верхней оценкой для рода графа, можно осуществить, произведя укладку этого графа на сфере с указанным числом ручек.

[math]\triangleleft[/math]

Утверждение:

Род полного двудольного графа [math]\gamma(K_{n, m}) =\left \lceil\dfrac{(n - 2)(m - 2)}{4} \right \rceil[/math].

[math]\triangleright[/math]

Аналогично предыдущему утверждению, [math]\gamma(K_{n, m}) \geqslant \dfrac{nm}{4} - \dfrac{n + m - 2}{2} = \dfrac{(n - 2)(m - 2)}{4}[/math]. Доказательство верхней оценки следует из укладки графа на сферу с ручками.

[math]\triangleleft[/math]

Род планарного графа равен [math]0[/math].

Если граф [math]G[/math] состоит из блоков [math]B_1, B_2, \ldots, B_n[/math], то [math]\gamma(G) = \sum\limits^{n}_{i = 1}\gamma(B_i)[/math].

Толщина

Определение:

Толщиной (англ. thickness) [math]\theta[/math] графа [math]G[/math] называется наименьшее число планарных графов, объединение которых есть [math]G[/math].

По определению, если существует набор [math]k[/math] планарных графов, имеющих одинаковый набор вершин, объединение которых даёт граф [math]G[/math], то толщина графа [math]G[/math] не больше [math]k[/math]. Таким образом, планарный граф имеет толщину [math]1[/math]. Графы с толщиной [math]2[/math] называются двупланарными графами. Концепция толщины возникла в гипотезе Фрэнка Харари: любой граф с [math]9[/math] вершинами либо сам, либо его дополнение, является непланарным. Эта гипотеза верна, так как полный граф [math]K_9[/math] не является бипланарным.

Толщина полного графа [math]\theta(K_n) = \left \lfloor\dfrac{n + 7}{6} \right \rfloor[/math], но толщина графов [math]K_9[/math] и [math]K_{10}[/math] равна [math]3[/math].

Крупность

Определение:

Крупностью (англ. coarseness) [math]\xi[/math] графа [math]G[/math] называется наибольшее число непланарных графов в [math]G[/math], не пересекающихся по рёбрам.

Формулы для вычисления крупности полного графа не такие простые, как для других топологических инвариантов.

Крупность планарного графа равна [math]0[/math], так как планарный граф не может содержать непланарный подграф.

Крупность [math]\xi(K_5) = 1[/math] и [math]\xi(K_{3,3}) = 1[/math], так как [math]K_5[/math] и [math]K_{3,3}[/math] содеражат только один непланарный подграф.

Число скрещиваний

Определение:

Числом скрещиваний (англ. crossing number) [math]\nu[/math] графа [math]G[/math] называется наименьшее число пересечений рёбер, которое будет при укладке [math]G[/math] на плоскости.

Точное значения числа скрещиваний не известно, установлена только верхняя оценка.

Число скрещиваний полного графа [math]\nu(K_n) \leqslant \dfrac{1}{4} \left \lfloor \dfrac{n}{2} \right \rfloor \left \lfloor \dfrac{n - 1}{2} \right \rfloor \left \lfloor \dfrac{n - 2}{2} \right \rfloor \left \lfloor \dfrac{n - 3}{2} \right \rfloor[/math].

Число скрещиваний полного двудольного графа [math]\nu(K_{n, m}) \leqslant \left \lfloor \dfrac{n}{2} \right \rfloor \left \lfloor \dfrac{n - 1}{2} \right \rfloor \left \lfloor \dfrac{m}{2} \right \rfloor \left \lfloor \dfrac{m - 1}{2} \right \rfloor[/math].

Укладу планарного графа можно сделать с помощью гамма-алгоритма, где число скрещиваний будет равно [math]0[/math].

Укладка графа на торе

Определение:

Если граф можно уложить на торе, то он тороидальный.

Тороидальный граф [math]G[/math] имеет род [math]\gamma(G) \leqslant 1[/math].

Утверждение:

[math]K_5[/math] и [math]K_{3,3}[/math] являются тороидальными.

[math]\triangleright[/math]

Укладки графа на торе представлены на рисунках с помощью прямоугольника, в котором отождествлены обе пары противоположных сторон. Укладка [math]K_5[/math] на торе. Укладка [math]K_{3,3}[/math] на торе. Вершины с номерами одного цвета принадлежат одной доле.

[math]\triangleleft[/math]

См. также

• Укладка графа на плоскости
• Непланарность [math]K_5[/math] и [math]K_{3,3}[/math]
• Формула Эйлера

Источники информации

• Харари Фрэнк Теория графов стр. 141-148 — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
• Википедия — Толщина графа
• Wikipedia — Crossing number