Теорема Нэша-Вильямса - Nash-Williams theorem

В теория графов, то Теорема Нэша-Вильямса это укладка деревьев теорема, описывающая, сколько ребер непересекающихся остовные деревья (и вообще леса ) граф может иметь:

График грамм имеет т реберно-непересекающиеся остовные деревья тогда и только тогда, когда для каждого раздела ${\textstyle V_{1},\ldots ,V_{k}\subset V(G)}$ куда ${\displaystyle V_{i}\neq \emptyset }$ есть по крайней мере т(k - 1) пересекающиеся края (Тутте 1961, Нэш-Вильямс 1961).^[1]

В этой статье мы скажем, что такой граф имеет родословиет или это т-древесный. (Фактическое определение родословие немного отличается и относится к лесам, а не деревьям.)

Связанные свойства упаковки деревьев

А k-арборный граф обязательно k-ребенок соединен. Обратное неверно.

Как следствие NW, каждые 2k-реберный связный граф k-аборик.

Оба NW и Теорема Менгера охарактеризовать, когда график имеет k рёберно-непересекающиеся пути между двумя вершинами.

Теорема Нэша-Вильямса для лесов

NW (1964) обобщил приведенный выше результат на леса:

G можно разбить на т гранично-непересекающиеся леса тогда и только тогда, когда для каждого ${\displaystyle U\subset V(G)}$, то индуцированный подграф грамм[U] имеет размер ${\displaystyle |G[U]|\leq t(|U|-1)}$.

Здесь приводится доказательство.^[2][1]

Вот как люди обычно определяют, что значит граф т-аборик.

Другими словами, для каждого подграфа S = грамм[U], у нас есть ${\displaystyle t\geq \lceil E(S)/(V(S)-1)\rceil }$. Туго в том, что есть подграф S что насыщает неравенство (иначе мы можем выбрать меньшее t). Это приводит к следующей формуле

${\displaystyle t=\lceil \max _{S\subset G}{\frac {E(S)}{V(S)-1}}\rceil }$

также упоминается как Формула NW.

Общая проблема состоит в том, чтобы спросить, можно ли покрыть граф реберно-непересекающимися подграфами.

Смотрите также

• Древесность
• Мост (обрезанный край)
• Теорема Менгера
• Гипотеза об упаковке деревьев

Рекомендации

1. Дистель, Рейнхард, 1959– Verfasser. (30.06.2017). Теория графов. ISBN  9783662536216. OCLC  1048203362.
2. Чен, Болионг; Мацумото, Макото; Ван, Цзяньфан; Чжан, Чжунфу; Чжан, Цзяньсюнь (1 марта 1994). «Краткое доказательство теоремы Нэша-Вильямса о древовидности графа». Графы и комбинаторика. 10 (1): 27–28. Дои:10.1007 / BF01202467. ISSN  1435-5914.