Толщина графа

Перейти к навигацииПерейти к поиску

В теории графов толщина графа G — это наименьшее число плоских подграфов, на которые можно разложить рёбра графа G. То есть, если существует набор k плоских графов, имеющих одинаковый набор вершин, объединение которых даёт граф G, то толщина графа G не больше k[1][2][3][4].

Таким образом, плоский граф имеет толщину 1. Графы с толщиной 2 называются двупланарными графами. Концепция толщины возникла в гипотезе Фрэнка Харари 1962 года: любой граф с 9 вершинами либо сам, либо его дополнение, является непланарным. Задача эквивалентна определению, является ли полный граф K9 бипланарным (он не бипланарен, так что гипотеза верна)[5]. Всесторонний обзор по теме толщины графа (по состоянию на 1998 год) написан Мутцелем, Оденталем и Шарбродтом[6].

Конкретные графы

Толщина полного графа с n вершинами, Kn, равна

за исключением случаев n = 9, 10, для которых толщина равна трём [7][8].

За исключением нескольких случаев, толщина полного двудольного графа Ka,b равна[7][9]

Связанные задачи

Любой лес планарен, а любой планарный граф можно разложить на три леса или меньше. Таким образом, толщина любого графа G не больше древесности того же графа (минимального числа лесов, на которые граф можно разложить) и не меньше древесности, делённой на три[10]. Толщина графа G связана с другим стандартным инвариантом, вырожденностью, определяемой как максимум по всем подграфам графа G минимальной степени подграфа. Если граф с n вершинами имеет толщину t, то число его рёбер не превосходит t(3n − 6), откуда следует, что вырожденность не превосходит 6t − 1. С другой стороны, если вырожденность графа равна D, то его древесность и толщина не превосходит D.

Толщина тесно связана с задачей одновременного вложения[11]. Если два или более планарных графов имеют тот же самый набор вершин, то имеется возможность вложить все эти графы в плоскость с представлением рёбер в виде кривых, так что все вершины будут иметь одну и ту же позицию во всех рисунках. Однако может оказаться, что построение таких рисунков невозможно, если использовать отрезки прямых.

Другой инвариант графов — прямолинейная толщина или геометрическая толщина графа G, подсчитывает наименьшее число планарных графов, на которые можно разложить G с ограничением, что все они могут быть нарисованы одновременно с помощью отрезков. Книжная толщина (или толщина книги) добавляет ограничение, что все вершины должны лежать на изгибе (переплёте книги). Однако, в отличие от древесности и вырожденности, нет прямой связи между этими величинами[12].

Вычислительная сложность

Вычисление толщины заданного графа является NP-трудной, а проверка, что толщина не превосходит двух, является NP-полной задачей[13]. Однако связь с древесностью позволяет аппроксимировать толщину с аппроксимационным коэффициентом 3 за полиномиальное время.

Примечания

  1. ↑ Tutte, 1963, с. 567—577.
  2. ↑ Mutzel, Odenthal, Scharbrodt, 1998, с. 59—73.
  3. ↑ Christian, 2009.
  4. ↑ Алексеев, Гончаков, 1976, с. 212.
  5. ↑ Mäkinen, Poranen, 2012, с. 76—87.
  6. ↑ Petra Mutzel, Thomas Odenthal and Mark Scharbrodt, The Thickness of Graphs: A Survey Архивная копия от 3 марта 2016 на Wayback Machine
  7. ↑ 1 2 Mutzel, Odenthal, Scharbrodt, 1998.
  8. ↑ Алексеев, Гончаков, 1976, с. 212—230.
  9. ↑ Beineke, Harary, Moon, 1964, с. 1—5.
  10. ↑ Dean, Hutchinson, Scheinerman, 1991, с. 147—151.
  11. ↑ Brass и др., 2007, с. 117—130.
  12. ↑ Eppstein, 2004, с. 75—86.
  13. ↑ Mansfield, 1983, с. 9—23.

Литература

  • David Eppstein. Towards a theory of geometric graphs. — Amer. Math. Soc., Providence, RI, 2004. — Т. 342. — (Contemp. Math). — doi:10.1090/conm/342/06132.
  • Anthony Mansfield. Determining the thickness of graphs is NP-hard // Mathematical Proceedings of the Cambridge Philosophical Society. — 1983. — Т. 93, вып. 1. — doi:10.1017/S030500410006028X.
  • W. T. Tutte. The thickness of a graph. — Indag. Math. — 1963. — Т. 25.
  • Petra Mutzel, Thomas Odenthal, Mark Scharbrodt. The thickness of graphs: a survey // Graphs and Combinatorics. — 1998. — Т. 14, вып. 1. — doi:10.1007/PL00007219.
  • Christian A. Duncan. On Graph Thickness, Geometric Thickness, and Separator Theorems // CCCG. — Vancouver, BC, 2009. — 17—19 August.
  • Erkki Mäkinen, Timo Poranen. An Annotated Bibliography on the Thickness, Outerthickness, and Arboricity of a Graph // Missouri J. Math. Sci. — 2012. — Т. 24, вып. 1.
  • В. Б. Алексеев, В. С. Гончаков. Толщина произвольного полного графа // Матем. сб. — 1976. — Т. 101(143), вып. 2(10).
  • Peter Brass, Eowyn Cenek, Cristian A. Duncan, Alon Efrat, Cesim Erten, Dan P. Ismailescu, Stephen G. Kobourov, Anna Lubiw, Joseph S. B. Mitchell. On simultaneous planar graph embeddings // Computational Geometry. — 2007. — Т. 36, вып. 2. — doi:10.1016/j.comgeo.2006.05.006.
  • Alice M. Dean, Joan P. Hutchinson, Edward R. Scheinerman. On the thickness and arboricity of a graph // Journal of Combinatorial Theory. — 1991. — Т. 52, вып. 1. — doi:10.1016/0095-8956(91)90100-X.
  • Lowell W. Beineke, Frank Harary, John W. Moon. On the thickness of the complete bipartite graph // Proc. Cambridge Philos. Soc. — 1964. — Т. 60. — doi:10.1017/s0305004100037385.