Нэш-Уильямс теоремасы - Nash-Williams theorem

Жылы графтар теориясы, Нэш-Уильямс теоремасы Бұл ағаш жинау қанша жиек-дизьюнкті сипаттайтын теорема ағаштар (және жалпы түрде) ормандар ) графикте мыналар болуы мүмкін:

График G бар т әр бөлікке арналған iff жиекті ағаштар ${ textstyle V_ {1}, ldots, V_ {k} ішкі жиын V (G)}$ қайда ${ displaystyle V_ {i} neq emptyset}$ кем дегенде бар т(к - 1) қиылысқан шеттер (Тутте 1961, Нэш-Уильямс 1961).^[1]

Бұл мақала үшін біз осындай графикке ие деп айтамыз ағаш өсірут немесе болып табылады т-ағашты. (Нақты анықтамасы ағаш өсіру сәл өзгеше және ағаштарға қарағанда ормандарға қатысты.)

Ағаштарды орауға қатысты қасиеттер

A к-орборикалық график міндетті түрде болуы керек к- жиек жалғанған. Керісінше емес.

NW қорытындысы ретінде, әр 2к-шеттермен байланысты график к- табиғи.

NW және Менгер теоремасы график болған кезде сипаттайды к екі шыңның арасындағы шеттік-айырылған жолдар.

Нэш-Уильямс ормандары туралы теорема

NW (1964) ормандарға жоғарыда келтірілген нәтижені жалпылау жасады:

G-ді бөлуге болады т егер әрқайсысы үшін шеткі орман ${ displaystyle U ішкі жиын V (G)}$ , индукцияланған субография G[U] өлшемі бар ${ displaystyle | G [U] | leq t (| U | -1)}$ .

Мұнда дәлел келтірілген.^[2]^[1]

Адамдар әдетте графиктің мағынасын осылай анықтайды т- табиғи.

Басқаша айтқанда, әрбір подграф үшін S = G[U], Бізде бар ${ displaystyle t geq lceil E (S) / (V (S) -1) rceil}$ . Ішкі сызба бар екендігі өте тығыз S бұл теңсіздікті қанықтырады (әйтпесе кіші t-ді таңдай аламыз). Бұл келесі формулаға әкеледі

${ displaystyle t = lceil max _ {S ішкі жиын G} { frac {E (S)} {V (S) -1}} rceil}$

деп те аталады NW формуласы.

Жалпы проблема - графикті қашанғы-дисжитті ішкі графиктермен жабуға болатындығын сұрау.

Сондай-ақ қараңыз

Әдебиеттер тізімі

^ ^а ^б Диестель, Рейнхард, 1959 - Верфассер. (2017-06-30). Графикалық теория. ISBN 9783662536216. OCLC 1048203362.CS1 maint: бірнеше есімдер: авторлар тізімі (сілтеме)
^ Чен, Болионг; Мацумото, Макото; Ван, Цзянфанг; Чжан, Чжунфу; Чжан, Цзянсюнь (1994-03-01). «Нэш-Уильямстың графиктің арборлығы туралы теоремасының қысқаша дәлелі». Графиктер және комбинаторика. 10 (1): 27–28. дои:10.1007 / BF01202467. ISSN 1435-5914.

[:0-1] а ^б Диестель, Рейнхард, 1959 - Верфассер. (2017-06-30). Графикалық теория. ISBN 9783662536216. OCLC 1048203362.CS1 maint: бірнеше есімдер: авторлар тізімі (сілтеме)

[2] Чен, Болионг; Мацумото, Макото; Ван, Цзянфанг; Чжан, Чжунфу; Чжан, Цзянсюнь (1994-03-01). «Нэш-Уильямстың графиктің арборлығы туралы теоремасының қысқаша дәлелі». Графиктер және комбинаторика. 10 (1): 27–28. дои:10.1007 / BF01202467. ISSN 1435-5914.

[1]

[2]