В теории графов , то Nash-Williams теорема является дерево-упаковки теорема , которая описывает , сколько реберно непересекающихся остовных деревьев (и в более общем случае лесов ) график может иметь:
Граф G имеет t непересекающихся по ребрам остовных деревьев тогда и только тогда, когда для каждого разбиения где имеется не менее t ( k - 1) пересекающихся ребер ( Tutte 1961, Nash-Williams 1961). [1]
В этой статье мы будем говорить , что такой график имеет arboricity т или т - arboric . (Фактическое определение древовидности немного отличается и применяется к лесам, а не деревьям.)
Связанные свойства упаковки деревьев
К -arboric граф обязательно к -Станкам подключены . Обратное неверно.
Как следствие NW, каждые 2 к связным графом -Станок является к -arboric.
И NW, и теорема Менгера характеризуют, когда граф имеет k путей, непересекающихся по ребрам, между двумя вершинами.
Теорема Нэша-Вильямса для лесов
NW (1964) обобщил приведенный выше результат на леса:
G можно разбить на t рёберно непересекающихся лесов тогда и только тогда, когда для любого, индуцированный подграф G [ U ] имеет размер.
Здесь приводится доказательство. [2] [1]
Вот как люди обычно определяют, что означает т- аборичность графа.
Другими словами, для любого подграфа S = G [ U ] имеем. Он труден в том смысле, что существует подграф S, который удовлетворяет неравенству (иначе мы можем выбрать меньшее t). Это приводит к следующей формуле
также называется формулой NW.
Общая проблема состоит в том, чтобы спросить, можно ли покрыть граф реберно-непересекающимися подграфами.
Смотрите также
- Древесность
- Мост (обрезанный край)
- Теорема Менгера
- Гипотеза об упаковке деревьев
Рекомендации
- ^ a b Diestel, Reinhard, 1959– Verfasser. (30.06.2017). Теория графов . ISBN 9783662536216. OCLC 1048203362 .CS1 maint: несколько имен: список авторов ( ссылка )
- ^ Чен, Болионг; Мацумото, Макото; Ван, Цзяньфан; Чжан, Чжунфу; Чжан, Цзяньсюнь (1994-03-01). «Краткое доказательство теоремы Нэша-Вильямса о древовидности графа». Графы и комбинаторика . 10 (1): 27–28. DOI : 10.1007 / BF01202467 . ISSN 1435-5914 .