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

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

Род

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

Родом (англ. 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