146
правок
Изменения
Нет описания правки
== Род ==
{{Определение
|definition ='''Родом''' ''(англ. genus)'' [[Основные определения теории графов|графа]] <tex>G</tex> называется наименьшее число ручек, которые нужно добавить к сфере, чтобы [[Укладка графа на плоскости|уложить]] <tex>G</tex>.
}}
Род [[Основные определения теории графов|полного]] графа <tex>\gamma(K_p) = \lceil\dfrac{(p - 3)(p - 4)}{12}\rceil</tex>.
Род [[Основные определения теории графов|полного двудольного]] графа <tex>\gamma(K_{m, n}) = \lceil\dfrac{(m - 2)(n - 2)}{4}\rceil</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>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) = \lfloor\dfrac{n + 7}{6}\rfloor</tex>, но толщина графов <tex>K_9</tex> и <tex>K_{10}</tex> равна <tex>3</tex>.
== Крупность ==
{{Определение
|definition ='''Крупностью''' ''(англ. coarseness)'' графа <tex>G</tex> называется наибольшее число непланарных графов в <tex>G</tex>, не пересекающихся по рёбрам.
}}
Формулы для вычисления крупности полного графа не такие простые, как для других топологических инвариантов.
== Число скрещиваний ==
{{Определение
|definition ='''Числом скрещиваний ''' ''(англ. crossing number)'' графа <tex>G</tex> называется число пересечений рёбер, которое должно быть при расположении <tex>G</tex> на плоскости.
}}
== Укладка графа на сфере ==
Положим сферу на плоскость так, чтобы точка касания сферы плоскости не пренадлежала графу. Проведём линии, соединяющие вершины графа с центром сферы. Точки пересечений линий со сферой будут вершинами графа на сфере. Таким образом мы получили однозначное соответствие точек сферы и точек плоскости, значит планарный граф можно уложить на сфере, так как каждой точке сферы (кроме точки, противоположной точки касания сферы плоскости) соответствует одна точка плоскости.
}}
Так как планарный граф можно уложить на сфере, то род планарного графа равен <tex>0</tex>.
== Укладка графа на торе ==
{{Определение
|definition = Если граф можно уложить на торе, то он '''тороидальный'''.
}}
Тороидальный граф <tex>G</tex> имеет род <tex>\gamma(G) \le 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> на торе. Вершины с номерами одного цвета принадлежат одной доле.]]
}}
== Замечание ==Знание этих инвариантов помогает при проектировании транспортных сетей. Например, если представить сеть в виде графа, то число скрещиваний этого графа будет равно количеству перекрёстков.
== См. также ==
* [[Укладка графа на плоскости]]
