Изменения

|definition ='''Родом''' ''(англ. genus)'' [[Основные определения теории графов|графа]] <tex>G</tex> называется наименьшее число ручек, которые нужно добавить к сфере, чтобы [[Укладка графа на плоскости|уложить]] <tex>G</tex>на этой сфере.

Обобщённая [[Формула Эйлера|формула Эйлера]], доказанная Курантом и Роббинсоном: <tex>V - E + F = 2 - 2\gamma</tex>. С её помощью можно доказать следующие утверждения.{{Утверждение|statement =Род [[Основные определения теории графов|полного]] графа <tex>\gamma(K_pK_n) = \left \lceil\dfrac{(p n - 3)(p 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, n}) = \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}\rceil</tex>. Доказательство верхней оценки следует из укладки графа на сферу с ручками.}}[[Укладка графа с планарными компонентами реберной двусвязности|Род планарного графа]] равен <tex>0</tex>.

|definition ='''Толщиной''' ''(англ. thickness)'' графа <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 ='''Числом скрещиваний ''' ''(англ. crossing number)'' графа <tex>G</tex> называется наименьшее число пересечений рёбер, которое должно быть будет при расположении укладке <tex>G</tex> на плоскости.

Число скрещиваний полного графа <tex>\nu(K_n) \le 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}) \le 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>.

== Укладка Укладу планарного графа на сфере =={{Утверждение|statement =Любой планарный граф можно уложить на сфере.сделать с помощью [[Гамма-алгоритм|proof =Положим сферу на плоскость так, чтобы точка касания сферы плоскости не пренадлежала графу. Проведём линии, соединяющие вершины графа с центром сферы. Точки пересечений линий со сферой будут вершинами графа на сфере. Таким образом мы получили однозначное соответствие точек сферы и точек плоскостигамма-алгоритма]], значит планарный граф можно уложить на сфере, так как каждой точке сферы (кроме точки, противоположной точки касания сферы плоскости) соответствует одна точка плоскости.}}Так как планарный граф можно уложить на сфере, то род планарного графа равен где число скрещиваний будет равно <tex>0</tex>.

Тороидальный граф <tex>G</tex> имеет род <tex>\gamma(G) \le leqslant 1</tex>.

* Харари Фрэнк '''Теория графов''' Перстр. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2141-е. 148 — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6