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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки

^ Тутте, WT (1963), «Толщина графа», Indag. Математика. , 66 : 567–577, doi : 10.1016/S1385-7258(63)50055-9 , MR 0157372 .
^ Jump up to: ^а ^б ^с Мюцель, Петра ; Оденталь, Томас; Шарбродт, Марк (1998), «Толщина графиков: обзор» (PDF) , Graphs and Combinatorics , 14 (1): 59–73, CiteSeerX 10.1.1.34.6528 , doi : 10.1007/PL00007219 , MR 1617664 , S2CID 31670574 .
^ Jump up to: ^а ^б Кристиан А. Дункан, О толщине графа, геометрической толщине и теоремах о разделителях , CCCG 2009, Ванкувер, Британская Колумбия, 17–19 августа 2009 г.
^ Рингель, Герхард (1959), Проблемы раскраски поверхностей и графов , Математические монографии, том. 2, Берлин: Немецкое научное издательство VEB, MR 0109349
^ Мякинен, Эркки; Поранен, Тимо (2012), «Аннотированная библиография о толщине, внешней толщине и древесности графа» , Missouri J. Math. наук. , 24 (1): 76–87, doi : 10.35834/mjms/1337950501 , S2CID 117703458
^ Мутцель, Оденталь и Шарбродт (1998) , Теорема 3.2.
^ Алексеев В.Б.; Гончаков В. С. (1976), "Толщина произвольного полного графа", Матем. Сб. , Новая серия, 101 (143): 212–230, Бибкод : 1976SbMat..30..187A , doi : 10.1070/SM1976v030n02ABEH002267 , MR 0460162 .
^ Мутцель, Оденталь и Шарбродт (1998) , Теорема 3.4.
^ Бейнеке, Лоуэлл В .; Харари, Фрэнк ; Мун, Джон В. (1964), «О толщине полного двудольного графа», Proc. Кембриджская философия. Соц. , 60 (1): 1–5, Bibcode : 1964PCPS...60....1B , doi : 10.1017/s0305004100037385 , MR 0158388 , S2CID 122829092 .
^ Дин, Элис М.; Хатчинсон, Джоан П .; Шайнерман, Эдвард Р. (1991), «О толщине и древесности графа», Журнал комбинаторной теории , серия B, 52 (1): 147–151, doi : 10.1016/0095-8956(91)90100-X , МР 1109429 .
^ Хэлтон, Джон Х. (1991), «О толщине графов заданной степени», Information Sciences , 54 (3): 219–238, doi : 10.1016/0020-0255(91)90052-V , MR 1079441
^ Сикора, Ондрей; Секели, Ласло А.; Врт'о, Имрих (2004), «Заметка о гипотезе Холтона», Information Sciences , 164 (1–4): 61–64, doi : 10.1016/j.ins.2003.06.008 , MR 2076570
^ Гетнер, Эллен (2018), «На Луну и дальше», в Гере, Ралукка ; Хейнс, Тереза В .; Хедетниеми, Стивен Т. (ред.), Теория графов: любимые гипотезы и открытые проблемы, II , задачники по математике, Springer International Publishing, стр. 115–133, номер документа : 10.1007/978-3-319-97686-0_11 , МР 3930641
^ Брасс, Питер; Сенек, Эовин; Дункан, Кристиан А.; Эфрат, Алон; Эртен, Чесим; Исмаилеску, Дэн П.; Кобуров, Стивен Г.; Любив, Анна ; Митчелл, Джозеф С.Б. (2007), «Об одновременных вложениях плоских графов», Вычислительная геометрия , 36 (2): 117–130, doi : 10.1016/j.comgeo.2006.05.006 , MR 2278011 .
^ Эппштейн, Дэвид (2004), «Отделение толщины от геометрической толщины», К теории геометрических графов , Contemp. Матем., вып. 342, амер. Математика. Soc., Провиденс, Род-Айленд, стр. 75–86, arXiv : math/0204252 , doi : 10.1090/conm/342/06132 , MR 2065254 .
^ Мэнсфилд, Энтони (1983), «Определение толщины графов NP-сложно», Mathematical Proceedings of the Cambridge Philosophical Society , 93 (1): 9–23, Bibcode : 1983MPCPS..93....9M , doi : 10.1017/S030500410006028X , MR 0684270 , S2CID 122028023 .

[1] Тутте, WT (1963), «Толщина графа», Indag. Математика. , 66 : 567–577, doi : 10.1016/S1385-7258(63)50055-9 , MR 0157372 .

[mos-2] Jump up to: ^а ^б ^с Мюцель, Петра ; Оденталь, Томас; Шарбродт, Марк (1998), «Толщина графиков: обзор» (PDF) , Graphs and Combinatorics , 14 (1): 59–73, CiteSeerX 10.1.1.34.6528 , doi : 10.1007/PL00007219 , MR 1617664 , S2CID 31670574 .

[duncan2009-3] Jump up to: ^а ^б Кристиан А. Дункан, О толщине графа, геометрической толщине и теоремах о разделителях , CCCG 2009, Ванкувер, Британская Колумбия, 17–19 августа 2009 г.

[4] Рингель, Герхард (1959), Проблемы раскраски поверхностей и графов , Математические монографии, том. 2, Берлин: Немецкое научное издательство VEB, MR 0109349

[anno-5] Мякинен, Эркки; Поранен, Тимо (2012), «Аннотированная библиография о толщине, внешней толщине и древесности графа» , Missouri J. Math. наук. , 24 (1): 76–87, doi : 10.35834/mjms/1337950501 , S2CID 117703458

[6] Мутцель, Оденталь и Шарбродт (1998) , Теорема 3.2.

[7] Алексеев В.Б.; Гончаков В. С. (1976), "Толщина произвольного полного графа", Матем. Сб. , Новая серия, 101 (143): 212–230, Бибкод : 1976SbMat..30..187A , doi : 10.1070/SM1976v030n02ABEH002267 , MR 0460162 .

[8] Мутцель, Оденталь и Шарбродт (1998) , Теорема 3.4.

[9] Бейнеке, Лоуэлл В .; Харари, Фрэнк ; Мун, Джон В. (1964), «О толщине полного двудольного графа», Proc. Кембриджская философия. Соц. , 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 , МР 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] Гетнер, Эллен (2018), «На Луну и дальше», в Гере, Ралукка ; Хейнс, Тереза В .; Хедетниеми, Стивен Т. (ред.), Теория графов: любимые гипотезы и открытые проблемы, II , задачники по математике, Springer International Publishing, стр. 115–133, номер документа : 10.1007/978-3-319-97686-0_11 , МР 3930641

[14] Брасс, Питер; Сенек, Эовин; Дункан, Кристиан А.; Эфрат, Алон; Эртен, Чесим; Исмаилеску, Дэн П.; Кобуров, Стивен Г.; Любив, Анна ; Митчелл, Джозеф С.Б. (2007), «Об одновременных вложениях плоских графов», Вычислительная геометрия , 36 (2): 117–130, doi : 10.1016/j.comgeo.2006.05.006 , MR 2278011 .

[15] Эппштейн, Дэвид (2004), «Отделение толщины от геометрической толщины», К теории геометрических графов , Contemp. Матем., вып. 342, амер. Математика. Soc., Провиденс, Род-Айленд, стр. 75–86, arXiv : math/0204252 , doi : 10.1090/conm/342/06132 , MR 2065254 .

[16] Мэнсфилд, Энтони (1983), «Определение толщины графов NP-сложно», Mathematical Proceedings of the Cambridge Philosophical Society , 93 (1): 9–23, Bibcode : 1983MPCPS..93....9M , doi : 10.1017/S030500410006028X , MR 0684270 , S2CID 122028023 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]