Nash-Williamsova věta - Nash-Williams theorem

v teorie grafů, Nash-Williamsova věta je balení stromů věta, která popisuje, kolik hran-disjunktních klenout se nad stromy (a obecněji lesy ) graf může mít:

Graf G má t okrajově disjunktní překlenující stromy iff pro každý oddíl ${ textstyle V_ {1}, ldots, V_ {k} podmnožina V (G)}$ kde ${ displaystyle V_ {i} neq emptyset}$ existuje alespoň t(k - 1) hrany hran (Tutte 1961, Nash-Williams 1961).^[1]

U tohoto článku řekneme, že takový graf má arboricitat nebo je t-arborický. (Skutečná definice arboricita se mírně liší a vztahuje se spíše na lesy než na stromy.)

Související vlastnosti balení stromů

A k-borborový graf je nutně k- hrana připojena. Opak není pravdivý.

Jako důsledek NW, každé 2k-je spojen grafem k-aborický.

Oba NW a Mengerova věta charakterizovat, když má graf k okrajové disjunktní cesty mezi dvěma vrcholy.

Nash-Williamsova věta pro lesy

NW (1964) zobecnil výše uvedený výsledek na lesy:

G lze rozdělit na t okrajové disjunktní lesy, pokud pro všechny ${ displaystyle U podmnožina V (G)}$, indukovaný podgraf G[U] má velikost ${ displaystyle | G [U] | leq t (| U | -1)}$.

Zde je uveden důkaz.^[2][1]

Takto lidé obvykle definují, co to znamená pro graf t-aborický.

Jinými slovy, pro každý podgraf S = G[U], my máme ${ Displaystyle t geq lceil E (S) / (V (S) -1) rceil}$. Je to těsné v tom, že existuje podgraf S která saturuje nerovnost (nebo můžeme zvolit menší t). To vede k následujícímu vzorci

${ displaystyle t = lceil max _ {S podmnožina G} { frac {E (S)} {V (S) -1}} rceil}$

označovaný také jako NW vzorec.

Obecným problémem je zeptat se, kdy lze graf zakrýt hraničními disjunktními podgrafy.

Viz také

• Arboricita
• Most (řezná hrana)
• Mengerova věta
• Domněnka o balení stromu

Reference