Просмотр исходного текста страницы Род, толщина, крупность, число скрещиваний

При проектировании транспортных сетей встаёт задача об [[Укладка графа на плоскости|укладке]] [[Основные определения теории графов|графа]] на плоскости, но не каждый граф [[Укладка графа на плоскости|планарен]]. Если сеть представляет из себя непланарный граф, то придётся делать перекрёстки или строить мосты. Постройка мостов обойдётся дороже постройки обычной дороги, а перекрёстки увеличивают время поездки. Поэтому перед началом работы будет полезно вычислить род, толщину, крупность и число срещиваний графа.
== Род ==
{{Определение
|definition ='''Родом''' ''(англ. genus)'' <tex>\gamma</tex> графа <tex>G</tex> называется наименьшее число ручек, которые нужно добавить к сфере, чтобы уложить <tex>G</tex> на этой сфере.
}}
Обобщённая [[Формула Эйлера|формула Эйлера]], доказанная Курантом и Роббинсоном: <tex>V - E + F = 2 - 2\gamma</tex>. С её помощью можно доказать следующие утверждения.
{{Утверждение
|statement =
Род [[Основные определения теории графов|полного]] графа <tex>\gamma(K_n) = \left \lceil\dfrac{(n - 3)(n - 4)}{12} \right \rceil</tex>.
|proof =
Из обобщённой формулы Эйлера следует, что если граф <tex>G</tex> связен, то его род <tex>\gamma \geqslant \dfrac{q}{6} - \dfrac{(p - 2)}{2}</tex>, где <tex>q</tex> — количество рёбер, <tex>p</tex> — количество вершин.

Тогда <tex>\gamma(K_n) \geqslant \dfrac{1}{6} \dfrac{n(n - 1)}{2}  - \dfrac{(n - 2)}{2} = \dfrac{(n - 3)(n - 4)}{12}</tex>.

Доказательство того, что правая часть является также верхней оценкой для рода графа, можно осуществить, произведя укладку этого графа на сфере с указанным числом ручек.
}}
{{Утверждение
|statement =
Род [[Основные определения теории графов|полного двудольного]] графа <tex>\gamma(K_{n, m}) =\left \lceil\dfrac{(n - 2)(m - 2)}{4} \right \rceil</tex>.
|proof =
Аналогично предыдущему утверждению, <tex>\gamma(K_{n, m}) \geqslant \dfrac{nm}{4}  - \dfrac{n + m - 2}{2} = \dfrac{(n - 2)(m - 2)}{4}</tex>.

Доказательство верхней оценки следует из укладки графа на сферу с ручками.
}}
[[Укладка графа с планарными компонентами реберной двусвязности|Род планарного графа]] равен <tex>0</tex>.

Если граф <tex>G</tex> состоит из [[Отношение вершинной двусвязности|блоков]] <tex>B_1, B_2, \ldots, B_n</tex>, то <tex>\gamma(G) = \sum\limits^{n}_{i = 1}\gamma(B_i)</tex>.

== Толщина ==
{{Определение
|definition ='''Толщиной''' ''(англ. thickness)'' <tex>\theta</tex> графа <tex>G</tex> называется наименьшее число планарных графов, объединение которых есть <tex>G</tex>.
}}
По определению, если существует набор <tex>k</tex> планарных графов, имеющих одинаковый набор вершин, объединение которых даёт граф <tex>G</tex>, то толщина графа <tex>G</tex> не больше <tex>k</tex>. Таким образом, планарный граф имеет толщину <tex>1</tex>. Графы с толщиной <tex>2</tex> называются двупланарными графами. Концепция толщины возникла в гипотезе Фрэнка Харари: любой граф с <tex>9</tex> вершинами либо сам, либо его дополнение, является непланарным. Эта гипотеза верна, так как полный граф <tex>K_9</tex> не является бипланарным.

Толщина полного графа <tex>\theta(K_n) = \left \lfloor\dfrac{n + 7}{6} \right \rfloor</tex>, но толщина графов <tex>K_9</tex> и <tex>K_{10}</tex> равна <tex>3</tex>.
== Крупность ==
{{Определение
|definition ='''Крупностью''' ''(англ. coarseness)'' <tex>\xi</tex> графа <tex>G</tex> называется наибольшее число непланарных графов в <tex>G</tex>, не пересекающихся по рёбрам.
}}
Формулы для вычисления крупности полного графа не такие простые, как для других топологических инвариантов.

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

Крупность <tex>\xi(K_5) = 1</tex> и <tex>\xi(K_{3,3}) = 1</tex>, так как <tex>K_5</tex> и <tex>K_{3,3}</tex> содеражат только один непланарный подграф.
== Число скрещиваний ==
{{Определение
|definition ='''Числом скрещиваний ''' ''(англ. crossing number)'' <tex>\nu</tex> графа <tex>G</tex> называется наименьшее число пересечений рёбер, которое будет при укладке <tex>G</tex> на плоскости.
}}
Точное значения числа скрещиваний не известно, установлена только верхняя оценка.

Число скрещиваний полного графа <tex>\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</tex>.

Число скрещиваний полного двудольного графа <tex>\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</tex>.

Укладу планарного графа можно сделать с помощью [[Гамма-алгоритм|гамма-алгоритма]], где число скрещиваний будет равно <tex>0</tex>.
== Укладка графа на торе ==
{{Определение
|definition = Если граф можно уложить на торе, то он '''тороидальный'''.
}}
Тороидальный граф <tex>G</tex> имеет род <tex>\gamma(G) \leqslant 1</tex>.
{{Утверждение
|statement =
<tex>K_5</tex> и <tex>K_{3,3}</tex> являются тороидальными.
|proof =
Укладки графа на торе представлены на рисунках с помощью прямоугольника, в котором отождествлены обе пары противоположных сторон.
[[Файл: K5_на_торе.png|300px|thumb|left|Укладка <tex>K_5</tex> на торе.]]
[[Файл: K3,3_на_торе.png|300px|thumb|center|Укладка <tex>K_{3,3}</tex> на торе. Вершины с номерами одного цвета принадлежат одной доле.]]
}}

== См. также ==
* [[Укладка графа на плоскости]]
* [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]]
* [[Формула Эйлера]]

== Источники информации ==
* Харари Фрэнк '''Теория графов''' стр. 141-148 — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
* [http://ru.wikipedia.org/wiki/Толщина_графа Википедия — Толщина графа]
* [http://en.wikipedia.org/wiki/Crossing_number_(graph_theory) Wikipedia — Crossing number]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Укладки графов]]