1632
правки
Изменения
м
{{Определение|definition ='''Толщиной''' ''(англ. thickness)'' графа <tex>G</tex> называется наименьшее число Обобщённая [[Укладка графа на плоскостиФормула Эйлера|планарныхформула Эйлера]] графов, объединение которых есть доказанная Курантом и Роббинсоном: <tex>G</tex>.}}{{Определение|definition V - E + F ='''Крупностью''' графа <tex>G2 - 2\gamma</tex> называется наибольшее число непланарных графов в <tex>G</tex>, не пересекающихся по рёбрам.}}{{Определение|definition ='''Числом скрещиваний ''' ''(англ. crossing number)'' графа <tex>G</tex> называется число пересечений рёбер, которое должно быть при расположении <tex>G</tex> на плоскостиС её помощью можно доказать следующие утверждения.}}== Укладка графа на ориентируемой поверхности ==
Любой граф можно уложить на некоторой ориентируемой поверхностиРод [[Основные определения теории графов|полного]] графа <tex>\gamma(K_n) = \left \lceil\dfrac{(n - 3)(n - 4)}{12} \right \rceil</tex>.
Это лекго понятьИз обобщённой формулы Эйлера следует, что если нарисовать произвольный граф на плоскости<tex>G</tex> связен, причём некоторые рёбра могут пересекатьсято его род <tex>\gamma \geqslant \dfrac{q}{6} - \dfrac{(p - 2)}{2}</tex>, и для каждомого пересечении где <tex>q</tex> — количество рёбер добавить к плоскости ручку; затем провести одно ребро по ручке, другое <tex>p</tex> — под нейколичество вершин. Тогда <tex>\gamma(K_n) \geqslant \dfrac{1}{6} \dfrac{n(n - 1)}{2} - \dfrac{(n - 2)}{2} = \dfrac{(n - 3)(n - 4)}{12}</tex>. Доказательство того, что правая часть является также верхней оценкой для рода графа, можно осуществить, произведя укладку этого графа на сфере с указанным числом ручек.
== Укладка графа на сфере ==
Любой планарный граф можно уложить на сфереРод [[Основные определения теории графов|полного двудольного]] графа <tex>\gamma(K_{n, m}) =\left \lceil\dfrac{(n - 2)(m - 2)}{4} \right \rceil</tex>.
Положим сферу на плоскость такАналогично предыдущему утверждению, чтобы точка касания сферы плоскости не пренадлежала графу. Проведём линии<tex>\gamma(K_{n, соединяющие вершины графа с центром сферыm}) \geqslant \dfrac{nm}{4} - \dfrac{n + m - 2}{2} = \dfrac{(n - 2)(m - 2)}{4}</tex>. Точки пересечений линий со сферой будут вершинами Доказательство верхней оценки следует из укладки графа на сфере. Таким образом мы получили однозначное соответствие точек сферы и точек плоскости, значит планарный граф можно уложить на сфере, так как каждой точке сферы (кроме точки, противоположной точки касания сферы плоскости) соответствует одна точка плоскостисферу с ручками.
rollbackEdits.php mass rollback
При проектировании транспортных сетей встаёт задача об [[Укладка графа на плоскости|укладке]] [[Основные определения теории графов|графа]] на плоскости, но не каждый граф [[Укладка графа на плоскости|планарен]]. Если сеть представляет из себя непланарный граф, то придётся делать перекрёстки или строить мосты. Постройка мостов обойдётся дороже постройки обычной дороги, а перекрёстки увеличивают время поездки. Поэтому перед началом работы будет полезно вычислить род, толщину, крупность и число срещиваний графа.
== Род ==
{{Определение
|definition ='''Родом''' [[Основные определения теории графов|''(англ. genus)'' <tex>\gamma</tex> графа]] <tex>G</tex> называется наименьшее число ручек, которые нужно добавить к сфере, чтобы [[Укладка графа на плоскости|уложить]] <tex>G</tex>на этой сфере.
}}
{{Утверждение
|statement =
|proof =
}}
{{Утверждение
|statement =
|proof =
}}
[[Укладка графа с планарными компонентами реберной двусвязности|Род планарного графа]] равен <tex>0</tex>.
Если граф <tex>G</tex> состоит из [[Отношение вершинной двусвязности|блоков]] <tex>B_1, B_2, \ldots, B_n</tex>, то <tex>\gamma(G) = \sum\limits^{n}_{i = 1}\gamma(B_i)</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> не является бипланарным.
Толщина полного графа <tex>\theta(K_n) = \left \lfloor\dfrac{n + 7}{6} \right \rfloor</tex>, но толщина графов <tex>K_9</tex> и <tex>K_{10}</tex> равна <tex>3</tex>.
== Крупность ==
{{Определение
|definition ='''Крупностью''' ''(англ. coarseness)'' <tex>\xi</tex> графа <tex>G</tex> называется наибольшее число непланарных графов в <tex>G</tex>, не пересекающихся по рёбрам.
}}
Формулы для вычисления крупности полного графа не такие простые, как для других топологических инвариантов.
Крупность планарного графа равна <tex>0</tex>, так как планарный граф не может содержать непланарный подграф.
Крупность <tex>\xi(K_5) = 1</tex> и <tex>\xi(K_{3,3}) = 1</tex>, так как <tex>K_5</tex> и <tex>K_{3,3}</tex> содеражат только один непланарный подграф.
== Число скрещиваний ==
{{Определение
|definition ='''Числом скрещиваний ''' ''(англ. crossing number)'' <tex>\nu</tex> графа <tex>G</tex> называется наименьшее число пересечений рёбер, которое будет при укладке <tex>G</tex> на плоскости.
}}
Точное значения числа скрещиваний не известно, установлена только верхняя оценка.
Число скрещиваний полного графа <tex>\nu(K_n) \leqslant \dfrac{1}{4} \left \lfloor \dfrac{n}{2} \right \rfloor \left \lfloor \dfrac{n - 1}{2} \right \rfloor \left \lfloor \dfrac{n - 2}{2} \right \rfloor \left \lfloor \dfrac{n - 3}{2} \right \rfloor</tex>.
Число скрещиваний полного двудольного графа <tex>\nu(K_{n, m}) \leqslant \left \lfloor \dfrac{n}{2} \right \rfloor \left \lfloor \dfrac{n - 1}{2} \right \rfloor \left \lfloor \dfrac{m}{2} \right \rfloor \left \lfloor \dfrac{m - 1}{2} \right \rfloor</tex>.
Укладу планарного графа можно сделать с помощью [[Гамма-алгоритм|гамма-алгоритма]], где число скрещиваний будет равно <tex>0</tex>.
== Укладка графа на торе ==
{{Определение
|definition = Если граф можно уложить на торе, то он '''тороидальный'''.
}}
Тороидальный граф <tex>G</tex> имеет род <tex>\gamma(G) \leqslant 1</tex>.
{{Утверждение
|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>]]
* [[Формула Эйлера]]
== Источники информации ==
* Харари Фрэнк '''Теория графов''' Перстр. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2141-е. 148 — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
* [http://ru.wikipedia.org/wiki/Толщина_графа Википедия — Толщина графа]
* [http://en.wikipedia.org/wiki/Crossing_number_(graph_theory) Wikipedia — Crossing number]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Укладки графов]]
