Толщина (теория графов)

Количество планарных подграфов, покрывающих граф

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

Таким образом, планарный граф имеет толщину один. Графы толщиной два называются бипланарными графами . Понятие толщины берет начало в задаче Земля-Луна о хроматическом числе бипланарных графов, поставленной в 1959 году Герхардом Рингелем ^[4] и в связанной с ней гипотезе 1962 года Фрэнка Харари : каждый граф на девяти точках или его дополнительный граф не является планарным . Задача эквивалентна определению того, является ли полный граф K ₉ бипланарным (это не так, и гипотеза верна). ^[5] Всесторонний ^[3] обзор состояния дел в этой теме по состоянию на 1998 год был написан Петрой Мутцель , Томасом Оденталем и Марком Шарбродтом. ^[2]

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

Толщина полного графа на n вершинах, K _n , равна

${\displaystyle \left\lfloor {\frac {n+7}{6}}\right\rfloor ,}$

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

За некоторыми исключениями толщина полного двудольного графа K _a,b обычно равна: ^{[8] [9]}

${\displaystyle \left\lceil {\frac {ab}{2(a+b-2)}}\right\rceil .}$

Характеристики

Каждый лес является планарным, и каждый планарный граф может быть разделен не более чем на три леса. Таким образом, толщина любого графа G не более чем равна древесности того же графа (минимальному числу лесов, на которые он может быть разделен) и не менее чем равна древесности, деленной на три. ^{[2] [10]}

Графы максимальной степени имеют толщину не более . ^[11] Это нельзя улучшить: для -регулярного графа с обхватом не менее , высокий обхват заставляет любой плоский подграф быть разреженным, в результате чего его толщина будет равна точно . ^[12] ${\displaystyle d}$ ${\displaystyle \lceil d/2\rceil }$ ${\displaystyle d}$ ${\displaystyle 2d}$ ${\displaystyle \lceil d/2\rceil }$

Девятицветная карта Земля–Луна Суланке с примыканиями, описанными объединением 6 -вершинного полного графа и 5-вершинного циклического графа (в центре). Поскольку примыкания в этом графе являются объединением примыканий в двух планарных картах (левой и правой), его толщина равна двум.

Графы толщины с вершинами имеют не более ребер. Поскольку это дает им среднюю степень меньше , их вырожденность не более , а их хроматическое число не более . Здесь вырожденность может быть определена как максимум, по подграфам данного графа, минимальной степени внутри подграфа. В другом направлении, если граф имеет вырожденность, то его древесность и толщина не более . Можно найти упорядочение вершин графа, в котором каждая вершина имеет не более соседей, которые идут позже нее в упорядочении, и назначение этих ребер различным подграфам дает разбиение графа на деревья, которые являются планарными графами. ${\displaystyle t}$ ${\displaystyle n}$ ${\displaystyle t(3n-6)}$ ${\displaystyle 6t}$ ${\displaystyle 6t-1}$ ${\displaystyle 6t}$ ${\displaystyle D}$ ${\displaystyle D}$ ${\displaystyle D}$ ${\displaystyle D}$ ${\displaystyle D}$

Даже в случае точное значение хроматического числа неизвестно; это проблема Земля–Луна Герхарда Рингеля . Пример Тома Суланке показывает, что для необходимо не менее 9 цветов. ^[13] ${\displaystyle t=2}$ ${\displaystyle t=2}$

Связанные проблемы

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

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

Сложность вычислений

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

Ссылки

1. Tutte, WT (1963), «Толщина графика», Indag. Math. , 66 : 567–577, doi : 10.1016/S1385-7258(63)50055-9 , MR  0157372.
2. Mutzel, Petra ; Odenthal, Thomas; Scharbrodt, Mark (1998), "Толщина графов: обзор" (PDF) , Графы и комбинаторика , 14 (1): 59–73, CiteSeerX 10.1.1.34.6528 , doi :10.1007/PL00007219, MR  1617664, S2CID  31670574 .
3. Кристиан А. Дункан, О толщине графа, геометрической толщине и теоремах о разделителе, CCCG 2009, Ванкувер, Британская Колумбия, 17–19 августа 2009 г.
4. Рингель, Герхард (1959), Färbungsprobleme auf Flächen und Graphen , Mathematische Monographien, vol. 2, Берлин: VEB Deutscher Verlag der Wissenschaften, MR  0109349
5. Мякинен, Эркки; Поранен, Тимо (2012), «Аннотированная библиография по толщине, внешней толщине и древовидности графа», Missouri J. Math. Sci. , 24 (1): 76–87, doi : 10.35834/mjms/1337950501 , S2CID  117703458
6. Мутцель, Оденталь и Шарбродт (1998), Теорема 3.2.
7. Алексеев, В. Б.; Гончаков, В. С. (1976), "Толщина произвольного полного графа", Матем. сб. , Новая серия, 101 (143): 212–230, Bibcode :1976SbMat..30..187A, doi :10.1070/SM1976v030n02ABEH002267, MR  0460162.
8. Мутцель, Оденталь и Шарбродт (1998), Теорема 3.4.
9. Бейнеке, Лоуэлл В .; Харари, Фрэнк ; Мун, Джон В. (1964), «О толщине полного двудольного графа», Proc. Cambridge Philos. Soc. , 60 (1): 1–5, Bibcode : 1964PCPS...60....1B, doi : 10.1017/s0305004100037385, MR  0158388, S2CID  122829092.
10. Дин, Элис М.; Хатчинсон, Джоан П .; Шайнерман, Эдвард Р. (1991), «О толщине и древовидности графа», Журнал комбинаторной теории , Серия B, 52 (1): 147–151, doi :10.1016/0095-8956(91)90100-X, MR  1109429.
11. Хэлтон, Джон Х. (1991), «О толщине графов заданной степени», Information Sciences , 54 (3): 219–238, doi :10.1016/0020-0255(91)90052-V, MR  1079441
12. Сикора, Ондрей; Секели, Ласло А.; Врт'о, Имрих (2004), «Заметка о гипотезе Холтона», Information Sciences , 164 (1–4): 61–64, doi :10.1016/j.ins.2003.06.008, MR  2076570
13. Gethner, Ellen (2018), «To the Moon and beyond», в Gera, Ralucca ; Haynes, Teresa W. ; Hedetniemi, Stephen T. (ред.), Теория графов: любимые гипотезы и открытые проблемы, II , Задачники по математике, Springer International Publishing, стр. 115–133, doi :10.1007/978-3-319-97686-0_11, ISBN 978-3-319-97684-6, МР  3930641
14. Брасс, Питер; Ченек, Эовин; Дункан, Кристиан А.; Эфрат, Алон; Эртен, Чесим; Исмаилеску, Дэн П.; Кобуров, Стивен Г.; Любив, Анна ; Митчелл, Джозеф СБ (2007), «Об одновременных вложениях планарных графов», Computational Geometry , 36 (2): 117–130, doi : 10.1016/j.comgeo.2006.05.006 , MR  2278011.
15. Эппштейн, Дэвид (2004), «Отделение толщины от геометрической толщины», К теории геометрических графов , Contemp. Math., т. 342, Amer. Math. Soc., Providence, RI, стр. 75–86, arXiv : math/0204252 , doi : 10.1090/conm/342/06132, ISBN 978-0-8218-3484-8, МР  2065254.
16. Мэнсфилд, Энтони (1983), «Определение толщины графов NP-трудно», Математические труды Кембриджского философского общества , 93 (1): 9–23, Bibcode : 1983MPCPS..93....9M, doi : 10.1017/S030500410006028X, MR  0684270, S2CID  122028023.