146
правок
Изменения
м
Нет описания правки
== Род ==
{{Определение
|definition ='''Родом''' ''(англ. genus)'' <tex>\gamma</tex> графа <tex>G</tex> называется наименьшее число ручек, которые нужно добавить к сфере, чтобы уложить <tex>G</tex> на этой сфере.
}}
Обобщённая [[Формула Эйлера|формула Эйлера]], доказанная Курантом и Роббинсоном: <tex>V - E + F = 2 - 2\gamma</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> не является бипланарным.
== Крупность ==
{{Определение
|definition ='''Крупностью''' ''(англ. coarseness)'' <tex>\xi</tex> графа <tex>G</tex> называется наибольшее число непланарных графов в <tex>G</tex>, не пересекающихся по рёбрам.
}}
Формулы для вычисления крупности полного графа не такие простые, как для других топологических инвариантов.
== Число скрещиваний ==
{{Определение
|definition ='''Числом скрещиваний ''' ''(англ. crossing number)'' <tex>\nu</tex> графа <tex>G</tex> называется наименьшее число пересечений рёбер, которое будет при укладке <tex>G</tex> на плоскости.
}}
Точное значения числа скрещиваний не известно, установлена только верхняя оценка.
