Древесность графа

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

Пример

Разбиение полного двудольного графа K_4,4 на три леса, что показывает, что его древесность равна трём.

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

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

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

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

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

Алгоритмы

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

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

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

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

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

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

Вырожденность графа — это максимальное число, по всем порождённым подграфам графа, минимума степеней вершин подграфа. Вырожденность графа с древесностью $a$ не меньше $a$ и не больше $2a-1$. Число раскрашивания графа, известное также как число Секереша — Вилфа , всегда равно его вырожденности плюс 1 .

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

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

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