Древесный

Число лесов, на которые можно разбить ребра графа

Древовидность неориентированного графа — это минимальное количество лесов , на которые можно разбить его ребра . Эквивалентно это минимальное количество остовных лесов, необходимое для покрытия всех ребер графа. Теорема Нэша-Вильямса обеспечивает необходимые и достаточные условия для того, когда граф является k -древовидным.

Пример

Разбиение полного двудольного графа K _4,4 на три леса, показывающее, что его древесность не превышает трех.

На рисунке показан полный двудольный граф K _4,4 , цвета которого указывают на разбиение его ребер на три леса. K _4,4 не может быть разбит на меньшее количество лесов, поскольку любой лес на его восьми вершинах имеет не более семи ребер, в то время как общий граф имеет шестнадцать ребер, что более чем вдвое превышает количество ребер в одном лесу. Следовательно, древесность K _4,4 равна трем.

Древесная плотность как мера плотности

Древовидность графа — это мера его плотности : графы с большим количеством ребер имеют высокую древесность, а графы с высокой древесностью должны иметь плотный подграф.

Более подробно, поскольку любой n-вершинный лес имеет не более n-1 ребер, древесность графа с n вершинами и m ребрами не менее . Кроме того, подграфы любого графа не могут иметь древесность большую, чем сам граф, или, что эквивалентно, древесность графа должна быть не менее максимальной древесности любого из его подграфов. Нэш-Вильямс доказал, что эти два факта можно объединить для характеристики древесности: если мы обозначим n _S и m _S число вершин и ребер, соответственно, любого подграфа S данного графа, то древесность графа равна ${\displaystyle \lceil m/(n-1)\rceil }$ ${\displaystyle \max _{S}\{\lceil m_{S}/(n_{S}-1)\rceil \}.}$

Любой планарный граф с вершинами имеет не более ребер, из чего следует по формуле Нэша-Вильямса, что планарные графы имеют древесность не более трех. Шнайдер использовал специальное разложение планарного графа на три леса, называемое лесом Шнайдера, чтобы найти прямолинейное вложение любого планарного графа в сетку малой площади. ${\displaystyle n}$ ${\displaystyle 3n-6}$

Алгоритмы

Древовидность графа может быть выражена как частный случай более общей проблемы разбиения матроида , ^[1] , в которой требуется выразить множество элементов матроида как объединение небольшого числа независимых множеств. Как следствие, древовидность может быть вычислена с помощью алгоритма полиномиального времени (Gabow & Westermann 1992). Текущий наилучший точный алгоритм вычисляет древовидность за время, где — количество ребер в графе. ${\displaystyle O(m{\sqrt {m}})}$ ${\displaystyle m}$

Приближения к древовидности графа можно вычислить быстрее. Существуют линейные алгоритмы 2-приближения ^{[2] [3]} и алгоритм почти линейного времени с аддитивной ошибкой 2. ^[4]

Связанные концепции

Анарборичность графа — это максимальное число непересекающихся по рёбрам неациклических подграфов , на которые можно разбить рёбра графа.

Звездная древесность графа — это размер минимального леса, каждое дерево которого является звездой (дерево с максимум одним нелистовым узлом), на который можно разбить ребра графа. Если дерево само по себе не является звездой, его звездная древесность равна двум, как можно увидеть, разбив ребра на два подмножества на нечетном и четном расстоянии от корня дерева соответственно. Таким образом, звездная древесность любого графа по крайней мере равна древесности и по максимуму равна удвоенной древесности.

Линейная древесность графа — это минимальное число линейных лесов (совокупность путей), на которые можно разбить ребра графа. Линейная древесность графа тесно связана с его максимальной степенью и его числом наклона .

Псевдодревесность графа — это минимальное количество псевдолесов , на которые можно разбить его ребра. Эквивалентно, это максимальное отношение ребер к вершинам в любом подграфе графа, округленное до целого числа. Как и в случае с древесностью, псевдодревесность имеет структуру матроида, что позволяет эффективно ее вычислять (Gabow & Westermann 1992).

Плотность подграфа графа — это плотность его самого плотного подграфа.

Толщина графа — это минимальное число планарных подграфов, на которые можно разбить его ребра. Поскольку любой планарный граф имеет древесность три, толщина любого графа по крайней мере равна трети древесности и по крайней мере равна древесности.

Вырожденность графа — это максимум, по всем индуцированным подграфам графа, минимальной степени вершины в подграфе. Вырожденность графа с древесностью по крайней мере равна , и по крайней мере равна . Число раскраски графа, также известное как его число Секереша-Вильфа (Szekeres & Wilf 1968), всегда равно его вырожденности плюс 1 (Jensen & Toft 1995, стр. 77f.). ${\displaystyle a}$ ${\displaystyle a}$ ${\displaystyle 2a-1}$

Сила графа — это дробное значение, целая часть которого дает максимальное количество непересекающихся остовных деревьев, которые можно нарисовать в графе. Это проблема упаковки, которая является двойственной к проблеме покрытия, вызванной древесностью. Эти два параметра изучались вместе Таттом и Нэшем-Уильямсом.

Дробная древесность является уточнением древесности, поскольку она определяется для графа как Другими словами, древесность графа является потолком дробной древесности. ${\displaystyle G}$ ${\displaystyle \max\{m_{S}/(n_{S}-1)\mid S\subseteq G\}.}$

(a,b)-разложимость обобщает древесность. Граф является -разложимым, если его ребра можно разбить на множества, каждое из которых порождает лес, за исключением того, которое порождает граф с максимальной степенью . Граф с древесностью является -разложимым. ${\displaystyle (a,b)}$ ${\displaystyle a+1}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle (a,0)}$

Число деревьев — это минимальное число деревьев, покрывающих рёбра графа.

Специальные выступления

Древесность появляется в гипотезе Голдберга–Сеймура .

Ссылки

1. Эдмондс, Джек (1965), «Минимальное разбиение матроида на независимые подмножества», Журнал исследований Национального бюро стандартов, раздел B , 69B : 67, doi : 10.6028/jres.069B.004
2. Эппштейн, Дэвид (1994), «Алгоритмы листинга древовидности и двудольных подграфов», Inf. Process. Lett. , 51 (4): 207–211, CiteSeerX 10.1.1.39.8474 , doi :10.1016/0020-0190(94)90121-X 
3. Арикати, Шриниваса Рао; Махешвари, Анил; Заролиагис, Христос Д. (1997), «Эффективное вычисление неявных представлений разреженных графов», Discrete Appl. Math. , 78 (1–3): 1–16, doi : 10.1016/S0166-218X(97)00007-3
4. Блюменшток, Маркус; Фишер, Франк (2020), «Конструктивная схема аппроксимации древовидности», 46-я Международная конференция по современным тенденциям в теории и практике информатики

• Алон, Н. (1988). «Линейная древовидность графов». Israel Journal of Mathematics . 62 (3): 311–325. CiteSeerX  10.1.1.163.1965 . doi : 10.1007/BF02783300 . MR  0955135.
• Chen, B.; Matsumoto, M.; Wang, J.; Zhang, Z.; Zhang, J. (1994). «Краткое доказательство теоремы Нэша-Вильямса для древесности графа». Графы и комбинаторика . 10 (1): 27–28. doi :10.1007/BF01202467. MR  1273008.
• Эрдеш, П .; Хайнал, А. (1966). «О хроматическом числе графов и систем множеств». Acta Mathematica Hungarica . 17 (1–2): 61–99. CiteSeerX  10.1.1.414.4942 . дои : 10.1007/BF02020444 . МР  0193025.
• Габов, Х. Н.; Вестерманн, Х. Х. (1992). «Леса, фреймы и игры: алгоритмы для сумм матроидов и их применение». Algorithmica . 7 (1): 465–497. doi :10.1007/BF01758774. MR  1154585.
• Хакими, С.Л.; Митчем, Дж.; Шмейхель, Э.Е. (1996). «Звездная древовидность графов». Дискретная математика . 149 (1–3): 93–98. doi : 10.1016/0012-365X(94)00313-8 . MR  1375101.
• Дженсен, ТР; Тофт, Б. (1995). Проблемы раскраски графов . Нью-Йорк: Wiley-Interscience. ISBN 0-471-02865-7. МР  1304254.
• C. St. JA Nash-Williams (1961). «Реберно-непересекающиеся остовные деревья конечных графов». Журнал Лондонского математического общества . 36 (1): 445–450. doi :10.1112/jlms/s1-36.1.445. MR  0133253.
• C. St. JA Nash-Williams (1964). «Разложение конечных графов на леса». Журнал Лондонского математического общества . 39 (1): 12. doi :10.1112/jlms/s1-39.1.12. MR  0161333.
• W. Schnyder (1990). «Вложение планарных графов в сетку». Труды 1-го симпозиума ACM/SIAM по дискретным алгоритмам (SODA) . С. 138–148.
• Szekeres, G. ; Wilf, HS (1968). "Неравенство для хроматического числа графа". Журнал комбинаторной теории . 4 : 1–3. doi : 10.1016/s0021-9800(68)80081-x . MR  0218269.
• Tutte, WT (1961). «О проблеме разложения графа на n связанных множителей». Журнал Лондонского математического общества . 36 (1): 221–230. doi :10.1112/jlms/s1-36.1.221. MR  0140438.