Древовидность

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

Пример

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

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

мера

Основная статья: теорема Нэша-Вильямса

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

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

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

Алгоритмы

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

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

Связанные понятия

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

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

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

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

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

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

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

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

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

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

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

Особые выступления

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

Ссылки

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