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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Определение |definition ='''Родом''' графа <tex>G</tex> называ...»)
 
Строка 3: Строка 3:
 
}}
 
}}
 
{{Определение
 
{{Определение
−
|definition ='''Толщиной''' графа <tex>G</tex> называется наименьшее число [[Укладка графа на плоскости|планарных]] графов, объединение которых есть <tex>G</tex>.
+
|definition ='''Толщиной''' ''(англ. thickness)'' графа <tex>G</tex> называется наименьшее число [[Укладка графа на плоскости|планарных]] графов, объединение которых есть <tex>G</tex>.
 
}}
 
}}
 
{{Определение
 
{{Определение
Строка 9: Строка 9:
 
}}
 
}}
 
{{Определение
 
{{Определение
−
|definition ='''Числом скрещиваний ''' графа <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
 
* Харари Фрэнк '''Теория графов''' Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 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]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Укладки графов]]
 
[[Категория: Укладки графов]]

Версия 00:40, 5 января 2016

Определение:
Родом графа [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]

См. также

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Род,_толщина,_крупность,_число_скрещиваний&oldid=50760»