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

Пример

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

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

Точнее, поскольку любой n-вершинный лес имеет максимум n − 1 рёбер, древовидность графа с n вершинами и m рёбрами не меньше . Кроме того, подграфы любого графа не могут иметь древовидность, большую древовидности самого графа, или, эквивалентно, древовидность графа должна быть не меньше максимальной древосности его подграфов. доказал, что эти два факта можно скомбинировать для характеризации древовидности — если nS и mS обозначают соответственно число вершин и рёбер произвольного подграфа S данного графа, тогда древовидность графа равна

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

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

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

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

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

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

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

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

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

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

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

Примечания

Литература

Категория:Инварианты графов Категория:Остовное дерево