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

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

Родом графа [math]G[/math] называется наименьшее число ручек, которые нужно добавить к сфере, чтобы уложить [math]G[/math].

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

Толщиной (англ. thickness) графа [math]G[/math] называется наименьшее число планарных графов, объединение которых есть [math]G[/math].

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

Крупностью графа [math]G[/math] называется наибольшее число непланарных графов в [math]G[/math], не пересекающихся по рёбрам.

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

Числом скрещиваний (англ. crossing number) графа [math]G[/math] называется число пересечений рёбер, которое должно быть при расположении [math]G[/math] на плоскости.

Укладка графа на ориентируемой поверхности

Утверждение:

Любой граф можно уложить на некоторой ориентируемой поверхности.

[math]\triangleright[/math]

Это лекго понять, если нарисовать произвольный граф на плоскости, причём некоторые рёбра могут пересекаться, и для каждомого пересечении рёбер добавить к плоскости ручку; затем провести одно ребро по ручке, другое — под ней.

[math]\triangleleft[/math]

Укладка графа на сфере

Утверждение:

Любой планарный граф можно уложить на сфере.

[math]\triangleright[/math]

Положим сферу на плоскость так, чтобы точка касания сферы плоскости не пренадлежала графу. Проведём линии, соединяющие вершины графа с центром сферы. Точки пересечений линий со сферой будут вершинами графа на сфере. Таким образом мы получили однозначное соответствие точек сферы и точек плоскости, значит планарный граф можно уложить на сфере, так как каждой точке сферы (кроме точки, противоположной точки касания сферы плоскости) соответствует одна точка плоскости.

[math]\triangleleft[/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]

Источники информации

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