Русская Википедия:Толщина графа
В теории графов толщина графа Шаблон:Mvar — это наименьшее число плоских подграфов, на которые можно разложить рёбра графа Шаблон:Mvar. То есть, если существует набор Шаблон:Mvar плоских графов, имеющих одинаковый набор вершин, объединение которых даёт граф Шаблон:Mvar, то толщина графа Шаблон:Mvar не больше Шаблон:MvarШаблон:SfnШаблон:SfnШаблон:SfnШаблон:Sfn.
Таким образом, плоский граф имеет толщину 1. Графы с толщиной 2 называются двупланарными графами. Концепция толщины возникла в гипотезе Фрэнка Харари 1962 года: любой граф с 9 вершинами либо сам, либо его дополнение, является непланарным. Задача эквивалентна определению, является ли полный граф Шаблон:Math бипланарным (он не бипланарен, так что гипотеза верна)Шаблон:Sfn. Всесторонний обзор по теме толщины графа (по состоянию на 1998 год) написан Мутцелем, Оденталем и Шарбродтом[1].
Конкретные графы
Толщина полного графа с Шаблон:Mvar вершинами, Шаблон:Mvar, равна
- <math>\left \lfloor \frac{n+7}{6} \right\rfloor,</math>
за исключением случаев Шаблон:Math, для которых толщина равна трём Шаблон:SfnШаблон:Sfn.
За исключением нескольких случаев, толщина полного двудольного графа Шаблон:Mvar равнаШаблон:SfnШаблон:Sfn
- <math>\left \lceil \frac{ab}{2(a+b-2)} \right \rceil.</math>
Связанные задачи
Любой лес планарен, а любой планарный граф можно разложить на три леса или меньше. Таким образом, толщина любого графа Шаблон:Mvar не больше древесности того же графа (минимального числа лесов, на которые граф можно разложить) и не меньше древесности, делённой на триШаблон:Sfn. Толщина графа Шаблон:Mvar связана с другим стандартным инвариантом, вырожденностью, определяемой как максимум по всем подграфам графа Шаблон:Mvar минимальной степени подграфа. Если граф с Шаблон:Mvar вершинами имеет толщину t, то число его рёбер не превосходит Шаблон:Math, откуда следует, что вырожденность не превосходит Шаблон:Math. С другой стороны, если вырожденность графа равна Шаблон:Mvar, то его древесность и толщина не превосходит Шаблон:Mvar.
Толщина тесно связана с задачей одновременного вложенияШаблон:Sfn. Если два или более планарных графов имеют тот же самый набор вершин, то имеется возможность вложить все эти графы в плоскость с представлением рёбер в виде кривых, так что все вершины будут иметь одну и ту же позицию во всех рисунках. Однако может оказаться, что построение таких рисунков невозможно, если использовать отрезки прямых.
Другой инвариант графов — прямолинейная толщина или геометрическая толщина графа Шаблон:Mvar, подсчитывает наименьшее число планарных графов, на которые можно разложить Шаблон:Mvar с ограничением, что все они могут быть нарисованы одновременно с помощью отрезков. Книжная толщина (или толщина книги) добавляет ограничение, что все вершины должны лежать на изгибе (переплёте книги). Однако, в отличие от древесности и вырожденности, нет прямой связи между этими величинамиШаблон:Sfn.
Вычислительная сложность
Вычисление толщины заданного графа является NP-трудной, а проверка, что толщина не превосходит двух, является NP-полной задачейШаблон:Sfn. Однако связь с древесностью позволяет аппроксимировать толщину с аппроксимационным коэффициентом 3 за полиномиальное время.
Примечания
Литература
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- ↑ Petra Mutzel, Thomas Odenthal and Mark Scharbrodt, The Thickness of Graphs: A Survey Шаблон:Wayback
