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

Материал из Викиконспекты
Перейти к: навигация, поиск

Род

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

Род полного графа [math]\gamma(K_p) = \lceil\dfrac{(p - 3)(p - 4)}{12}\rceil[/math].

Род полного двудольного графа [math]\gamma(K_{m, n}) = \lceil\dfrac{(m - 2)(n - 2)}{4}\rceil[/math].

Если граф [math]G[/math] состоит из блоков [math]B_1, B_2, \ldots, B_n[/math], то [math]\gamma(G) = \sum\limits^{n}_{i = 1}\gamma(B_i)[/math].

Толщина

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

По определению, если существует набор [math]k[/math] планарных графов, имеющих одинаковый набор вершин, объединение которых даёт граф [math]G[/math], то толщина графа [math]G[/math] не больше [math]k[/math]. Таким образом, планарный граф имеет толщину [math]1[/math]. Графы с толщиной [math]2[/math] называются двупланарными графами. Концепция толщины возникла в гипотезе Фрэнка Харари: любой граф с [math]9[/math] вершинами либо сам, либо его дополнение, является непланарным. Задача эквивалентна определению, является ли полный граф [math]K_9[/math] бипланарным (он не бипланарен, так что гипотеза верна).

Толщина полного графа [math]\theta(K_n) = \lfloor\dfrac{n + 7}{6}\rfloor[/math], но толщина графов [math]K_9[/math] и [math]K_{10}[/math] равна [math]3[/math].

Крупность

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

Формулы для вычисления крупности полного графа не такие простые, как для других топологических инвариантов.

Число скрещиваний

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

Точное значения числа скрещиваний не известно, установлена только верхняя оценка.

Число скрещиваний полного графа [math]\nu(K_n) \le \dfrac{1}{4} \lfloor \dfrac{n}{2} \rfloor \lfloor \dfrac{n - 1}{2} \rfloor \lfloor \dfrac{n - 2}{2} \rfloor \lfloor \dfrac{n - 3}{2} \rfloor[/math].

Число скрещиваний полного двудольного графа [math]\nu(K_{n, m}) \le \lfloor \dfrac{n}{2} \rfloor \lfloor \dfrac{n - 1}{2} \rfloor \lfloor \dfrac{m}{2} \rfloor \lfloor \dfrac{m - 1}{2} \rfloor[/math].

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

Утверждение:
Любой планарный граф можно уложить на сфере.
[math]\triangleright[/math]
Положим сферу на плоскость так, чтобы точка касания сферы плоскости не пренадлежала графу. Проведём линии, соединяющие вершины графа с центром сферы. Точки пересечений линий со сферой будут вершинами графа на сфере. Таким образом мы получили однозначное соответствие точек сферы и точек плоскости, значит планарный граф можно уложить на сфере, так как каждой точке сферы (кроме точки, противоположной точки касания сферы плоскости) соответствует одна точка плоскости.
[math]\triangleleft[/math]

Так как планарный граф можно уложить на сфере, то род планарного графа равен [math]0[/math].

Укладка графа на торе

Определение:
Если граф можно уложить на торе, то он тороидальный.

Тороидальный граф [math]G[/math] имеет род [math]\gamma(G) \le 1[/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=50778»