Древовидность
-
Определение и свойства древовидности
- Древовидность графа — минимальное количество лесов, необходимых для покрытия его ребер.
- Эквивалентно минимальному количеству остовных лесов.
- Теорема Нэша-Уильямса описывает условия для графа, чтобы быть k-образным.
-
Примеры и связь с плотностью
- Двудольный граф K4,4 имеет древовидность 3, так как не может быть разделен на меньшее количество лесов.
- Древовидность связана с плотностью графа: чем больше ребер, тем выше древовидность.
- Подграфы не могут иметь большей древовидности, чем сам граф.
-
Алгоритмы и связанные понятия
- Древовидность может быть вычислена с помощью алгоритмов за полиномиальное время.
- Существуют приближенные алгоритмы для вычисления древовидности с разной точностью.
- Анарборичность, звездообразная древовидность, линейная древовидность и псевдоарборичность — другие связанные понятия.
-
Дополнительные свойства и приложения
- Древовидность связана с другими параметрами графа, такими как плотность подграфа и толщина.
- Вырожденность графа и число раскраски также связаны с древовидностью.
- Прочность графа и дробная древовидность являются другими важными параметрами.
- (a, b)-разложимость обобщает понятие древовидности.
Полный текст статьи: