146
правок
Изменения
Нет описания правки
}}
{{Определение
|definition ='''Толщиной''' ''(англ. thickness)'' графа <tex>G</tex> называется наименьшее число [[Укладка графа на плоскости|планарных]] графов, объединение которых есть <tex>G</tex>.
}}
{{Определение
}}
{{Определение
|definition ='''Числом скрещиваний ''' ''(англ. crossing number)'' графа <tex>G</tex> называется число пересечений рёбер, которое должно быть при расположении <tex>G</tex> на плоскости.
}}
== Укладка графа на ориентируемой поверхности ==
{{Утверждение
|statement =
Любой граф можно уложить на некоторой ориентируемой поверхности.
|proof =
Это лекго понять, если нарисовать произвольный граф на плоскости, причём некоторые рёбра могут пересекаться, и для каждомого пересечении рёбер добавить к плоскости ручку; затем провести одно ребро по ручке, другое — под ней.
}}
== Укладка графа на сфере ==
{{Утверждение
|statement =
Любой планарный граф можно уложить на сфере.
|proof =
Положим сферу на плоскость так, чтобы точка касания сферы плоскости не пренадлежала графу. Проведём линии, соединяющие вершины графа с центром сферы. Точки пересечений линий со сферой будут вершинами графа на сфере. Таким образом мы получили однозначное соответствие точек сферы и точек плоскости, значит планарный граф можно уложить на сфере, так как каждой точке сферы (кроме точки, противоположной точки касания сферы плоскости) соответствует одна точка плоскости.
}}
== Укладка графа на торе ==
{{Определение
|definition = Если граф можно уложить на торе, то он '''тороидальный'''.
}}
{{Утверждение
|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> на торе. Вершины с номерами одного цвета принадлежат одной доле.]]
}}
== См. также ==
* [[Укладка графа на плоскости]]
* [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]]
== Источники информации ==
* Харари Фрэнк '''Теория графов''' Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
* [http://ru.wikipedia.org/wiki/Толщина_графа Википедия — Толщина графа]
* [http://en.wikipedia.org/wiki/Crossing_number_(graph_theory) Wikipedia — Crossing number]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Укладки графов]]
