Введение

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

Пример

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

Деревообразование как мера плотности

Арборитность графа – это мера его плотности: графы с большим количеством ребер имеют высокую арборитность, а графы с высокой арборитностью должны содержать плотный подграф. Более конкретно, поскольку любой лес из n вершин имеет не более n-1 ребер, арборитность графа с n вершинами и m ребрами составляет как минимум. Кроме того, арборитность подграфов любого графа не может превышать арборитность самого графа, или, эквивалентно, арборитность графа должна быть не меньше максимальной арборитности любого из его подграфов. Нэш Уильямс доказал, что эти два факта можно объединить для характеристики арборитности: если обозначить количество вершин и ребер любого подграфа S данного графа как nS и mS соответственно, то арборитность графа равна.

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

Алгоритмы

Древообразность графа может быть выражена как частный случай более общей задачи разбиения матроида, в которой требуется представить множество элементов матроида в виде объединения небольшого числа независимых множеств. Как следствие, древообразность может быть вычислена за полиномиальное время. Наилучший на данный момент точный алгоритм вычисляет древообразность за время , где – количество ребер в графе. Приближенные значения древообразности графа могут быть вычислены быстрее. Существуют алгоритмы аппроксимации с линейной временной сложностью 2 и алгоритм, близкий к линейному по времени, с аддитивной погрешностью 2.

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

Анарборичность графа — это максимальное количество непересекающихся по ребрам нециклических подграфов, на которые можно разбить ребра графа. Звёздная древообразность графа — это размер минимального леса, каждое дерево которого является звездой (дерево с не более чем одним нелистовым узлом), на который можно разбить ребра графа. Если дерево само по себе не является звездой, его звёздная древообразность равна двум, что можно увидеть, разбив ребра на два подмножества по нечётным и чётным расстояниям от корня дерева соответственно. Следовательно, звёздная древообразность любого графа не меньше древообразности и не больше удвоенной древообразности. Линейная древообразность графа — это минимальное количество линейных лесов (множество путей), на которые можно разбить ребра графа. Линейная древообразность графа тесно связана с его максимальной степенью и числом наклона. Псевдолесистость графа — это минимальное количество псевдолесов, на которые можно разбить его ребра. Эквивалентно, это максимальное отношение числа ребер к числу вершин в любом подграфе графа, округлённое до целого числа. Как и в случае древообразности, псевдолесистость имеет матроидную структуру, позволяющую эффективно вычислять её. Плотность подграфа графа — это плотность его самого плотного подграфа. Толщина графа — это минимальное количество планарных подграфов, на которые можно разбить его ребра. Поскольку любой планарный граф имеет древообразность три, толщина любого графа не меньше трети древообразности и не больше древообразности. Вырождение графа — это максимум по всем индуцированным подграфам графа от минимальной степени вершины в подграфе. Вырождение графа с древообразностью не меньше , а не больше окрашивающее число графа, также известное как число Секереша — Вильфа, всегда равно его вырождению плюс 1. Сила графа — это дробное значение, целая часть которого дает максимальное количество непересекающихся покрывающих деревьев, которые можно построить в графе. Это задача упаковки, двойственная задаче покрытия, возникающей при рассмотрении древообразности. Эти два параметра были изучены совместно Тютте и Нэш-Уильямсом. Фракционная древообразность является уточнением древообразности, поскольку она определяется для графа как . Иными словами, древообразность графа — это потолок фракционной древообразности. (a,b)-декомпозируемость обобщает древообразность. Граф является (a,b)-декомпозируемым, если его ребра можно разбить на множеств, каждое из которых индуцирует лес, за исключением одного, которое индуцирует граф с максимальной степенью . Граф с древообразностью является (a,b)-декомпозируемым. Число деревьев — это минимальное количество деревьев, покрывающих ребра графа.

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

Арборичность фигурирует в гипотезе Голдберга — Сеймура.