WikiDer > Тутте теоремасы

Tutte theorem

Ішінде математикалық тәртіп графтар теориясы The Тутте теоремасы, атындағы Уильям Томас Тутте, сипаттамасы болып табылады графиктер бірге тамаша сәйкестіктер. Бұл жалпылау Холлдың неке теоремасы екіжақты графикке дейін.^{[түсіндіру қажет]} Бұл ерекше жағдай Tutte – Berge формуласы.

Тутте теоремасы

График, $G = (V, E)$ , бар тамаша сәйкестік егер және егер болса әрбір ішкі жиын үшін $U$ туралы $V$ , подограф туындаған $V - U$ ең көп дегенде $| U |$ қосылған компоненттер тақ санымен төбелер.^[1]

Дәлелдер

Тікелей дәлелдеу

Алдымен біз шартты жазамыз:

{ displaystyle (*) qquad for all U subeteq V, quad o (G-U) leq | U |}

қайда ${ displaystyle o (X)}$ -мен индукцияланған субграфтың тақ компоненттерінің санын білдіреді ${ displaystyle X}$ .

(∗) қажеттілігі: Графикті қарастырайық $G$ , тамаша сәйкестікпен. Келіңіздер $U$ ерікті ішкі жиыны болуы мүмкін $V$ . Жою $U$ . Келіңіздер $C$ ішіндегі ерікті тақ компонент болу $G - U$ . Бастап $G$ кем дегенде бір шыңы бар тамаша сәйкестік болды $C$ in шыңына сәйкес келуі керек $U$ . Демек, әр тақ компоненттің кем дегенде бір шыңы in шыңымен сәйкес келеді $U$ . Әрбір шыңнан бастап $U$ ең көп дегенде бір байланысты компонентпен байланысты болуы мүмкін (себебі ол ең жақсы сәйкестендіруге сәйкес келеді), $o (G - U) \leq | U |$ .^[2]

(Iciency) жеткіліктілігі: Келіңіздер $G$ толық сәйкес келмейтін ерікті график болыңыз. Біз а табамыз жаман шыңдар жиынтығы $S$ , яғни $V$ осындай $| S | < o (G - S)$ . Біз мұны болжай аламыз $G$ максималды, яғни, $G + e$ әр шетіне тамаша сәйкес келеді $e$ жоқ $G$ қазірдің өзінде. Шынында да, егер біз жаман жиынтығын тапсақ $S$ максималды графикте $G$ , содан кейін $S$ тармағының әр таралатын тармағында да жаман жиынтық бар $G$ , сияқты тақ тақталарының кез келгені $G - S$ мүмкін көп компоненттерге бөлінеді, олардың ең болмағанда біреуі тақ болады.

Біз анықтаймыз $S$ дәрежесі бар шыңдар жиыны болуы керек $| V | - 1$ . Алдымен біз барлық компоненттердің жағдайын қарастырамыз $G - S$ толық графиктер. Содан кейін $S$ жаман жиынтық болуы керек, өйткені егер $o (G - S) \leq | S |$ , содан кейін біз әр тақ компоненттен бір шыңды шыңнан бастап шыңға сәйкестендіру арқылы керемет сәйкестікті таба алдық $S$ және барлық басқа шыңдарды жұптастыру (егер ол жұмыс жасамаса $| V |$ тақ, бірақ содан кейін $\emptyset$ жаман).

Енді солай делік $Қ$ компоненті болып табылады $G - S$ және $х, ж \in Қ$ осындай шыңдар $xy \notin E$ . Келіңіздер $х, а, б \in Қ$ ең қысқа шыңдар $х, ж$ -жол $Қ$ . Бұл бұған кепілдік береді $xa, аб \in E$ және $xb \notin E$ . Бастап $а \notin S$ , шың бар $c$ осындай $ак \notin E$ . -Ның шетінен-максимумына дейін $G$ , біз анықтаймыз $М 1$ тамаша үйлесімділік ретінде $G + xb$ және $М 2$ тамаша үйлесімділік ретінде $G + ак$ . Мұны міндетті түрде қадағалаңыз $xb \in М 1$ және $ак \in М 2$ .

Келіңіздер $P$ максималды жол болыңыз $G$ басталады $c$ шетінен бастап $М 1$ және олардың шеттері кезектесіп тұрады $М 1$ және $М 2$ . Қалай $P$ Соңы? Егер біз «арнайы» шыңға келмесек $х, а$ немесе $б$ , біз әрқашан жалғастыра аламыз: $c$ болып табылады $М 2$ - сәйкес келеді $шамамен$ , сондықтан бірінші жиегі $P$ жоқ $М 2$ , сондықтан екінші шыңы болып табылады $М 2$ - басқа шыңмен сәйкес келеді және біз осылай жалғастырамыз.

Келіңіздер $v$ соңғы шыңын белгілеңіз $P$ . Егер соңғы жиегі болса $P$ ішінде $М 1$ , содан кейін $v$ болуы керек $а$ , әйтпесе біз шетінен жалғастыра аламыз $М 2$ (тіпті жету үшін $х$ немесе $б$ ). Бұл жағдайда біз анықтаймыз $C := P + ак$ . Егер соңғы жиегі болса $P$ ішінде $М 2$ , содан кейін сөзсіз $v \in {х, б$ } ұқсас себептермен және біз анықтаймыз $C := P + va + ак$ .

Қазір $C$ цикл болып табылады $G + ак$ барлық ұзындығы бір-біріне тең $М 2$ . Біз енді анықтай аламыз $М := М 2 Δ C$ (қайда $Δ$ болып табылады симметриялық айырмашылық) және бізде сәйкес келеді $G$ , қайшылық.

Тутте-Берге формуласынан шығару

The Tutte – Berge формуласы графиктің максималды сәйкес келу мөлшері дейді ${ displaystyle G = (V, E)}$ тең ${ displaystyle { frac {1} {2}} min _ {U subseteq V} left (| U | - operatorname {odd} (G-U) + | V | right)}$

Туттенің шарты - әрқайсысы үшін ${ displaystyle U subseteq V}$ , ${ displaystyle { text {тақ {}} (G-U) leq | U |}$ . Эквивалентті түрде минимум ішіндегі өрнек кем дегенде болады ${ displaystyle | V |}$ . Эквивалентті түрде барлық өрнек кем дегенде болады ${ displaystyle | V | / 2}$ .

Сонымен, егер графиктің өлшемі кем дегенде сәйкес болса, Таттенің шарты орындалады ${ displaystyle | V | / 2}$ , егер графиктің толық сәйкестігі болса.

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

Ескертулер

^ Lovász & Plummer (1986), б. 84; Бонди және Мурти (1976), Теорема 5.4, б. 76.
^ Бонди және Мурти (1976), 76-78 б.

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

Бонди, Дж. А .; Murty, U. S. R. (1976). Қолданбалы графикалық теория. Нью-Йорк: Американдық Elsevier Pub. Co. ISBN 0-444-19451-7.CS1 maint: ref = harv (сілтеме)
Ловас, Ласло; Пламмер, М.Д. (1986). Сәйкестік теориясы. Амстердам: Солтүстік-Голландия. ISBN 0-444-87916-1.CS1 maint: ref = harv (сілтеме)

[1] Lovász & Plummer (1986), б. 84; Бонди және Мурти (1976), Теорема 5.4, б. 76.

[bm-proof-2] Бонди және Мурти (1976), 76-78 б.

[1]

[2]

Navigation