Меню Главная Случайная статья Настройки Толщина графа Материал из https://ru.wikipedia.org В теории графов толщина графа G — это наименьшее число плоских подграфов, на которые можно разложить рёбра графа Таким образом, плоский граф имеет толщину 1. Графы с толщиной 2 называются двупланарными графами. Концепция толщины возникла в гипотезе Фрэнка Харари 1962 года: любой граф с 9 вершинами либо сам, либо его дополнение, является непланарным. Задача эквивалентна определению, является ли полный граф Содержание 1 Конкретные графы 2 Связанные задачи 3 Вычислительная сложность 4 Примечания 5 Литература Конкретные графы Толщина полного графа с ${\displaystyle \left\lfloor {\frac {n+7}{6}}\right\rfloor ,}$ за исключением случаев За исключением нескольких случаев, толщина полного двудольного графа ${\displaystyle \left\lceil {\frac {ab}{2(a+b-2)}}\right\rceil .}$ Связанные задачи Любой лес планарен, а любой планарный граф можно разложить на три леса или меньше. Таким образом, толщина любого графа Толщина тесно связана с задачей одновременного вложения[11]. Если два или более планарных графов имеют тот же самый набор вершин, то имеется возможность вложить все эти графы в плоскость с представлением рёбер в виде кривых, так что все вершины будут иметь одну и ту же позицию во всех рисунках. Однако может оказаться, что построение таких рисунков невозможно, если использовать отрезки прямых. Другой инвариант графов — прямолинейная толщина или геометрическая толщина графа G, подсчитывает наименьшее число планарных графов, на которые можно разложить G с ограничением, что все они могут быть нарисованы одновременно с помощью отрезков. Книжная толщина (или толщина книги) добавляет ограничение, что все вершины должны лежать на изгибе (переплёте книги). Однако, в отличие от древесности и вырожденности, нет прямой связи между этими величинами[12]. Вычислительная сложность Вычисление толщины заданного графа является NP-трудной, а проверка, что толщина не превосходит двух, является NP-полной задачей[13]. Однако связь с древесностью позволяет аппроксимировать толщину с аппроксимационным коэффициентом 3 за полиномиальное время. Примечания Tutte, 1963, с. 567—577. Mutzel, Odenthal, Scharbrodt, 1998, с. 59—73. Christian, 2009. Алексеев, Гончаков, 1976, с. 212. Mkinen, Poranen, 2012, с. 76—87. Petra Mutzel, Thomas Odenthal and Mark Scharbrodt, The Thickness of Graphs: A Survey Архивная копия от 3 марта 2016 на Wayback Machine 1 2 Mutzel, Odenthal, Scharbrodt, 1998. Алексеев, Гончаков, 1976, с. 212—230. Beineke, Harary, Moon, 1964, с. 1—5. Dean, Hutchinson, Scheinerman, 1991, с. 147—151. Brass и др., 2007, с. 117—130. Eppstein, 2004, с. 75—86. 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 Mkinen, 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.