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

Материал из Викиконспекты
Перейти к: навигация, поиск
Определение:
Родом графа [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]

См. также

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