Теорема Татта: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''Теорема Татта''' (''W.T.Tutte, 1947'') - Граф <math>G</math> имеет совершенное паросочетан...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
'''Теорема Татта''' (''W.T.Tutte, 1947'') | '''Теорема Татта''' (''[[W.T.Tutte, 1947]]'') — [[Граф]] <math>\,G</math> имеет [[совершенное паросочетание]] тогда и только тогда, когда число нечетных компонент <math>c_{1}(G \setminus X)</math> [[подграф|подграфа]] <math>G \setminus X</math> для любого подмножества [[вершина|вершин]] <math>X \subseteq V(G)</math> удовлетворяет неравенству | ||
Граф <math>G</math> имеет совершенное паросочетание тогда и только тогда, когда число нечетных компонент <math>c_{1}(G \setminus X)</math> подграфа <math>G \setminus X</math> для любого подмножества вершин <math>X \subseteq V(G)</math> удовлетворяет неравенству | |||
<math>c_{1}(G \setminus X) \leq |X|.</math> | :::::<math>c_{1}(G \setminus X) \leq |X|.</math> | ||
==Литература== | ==Литература== | ||
* Татт У. Теория графов. — М.:Мир, 1988. | |||
* Bondy J.A., Murty U.S.R. Graph theory with applications. — New York; Amsterdam; Oxford: North-Holland, 1976. | |||
* <math>Lov\acute{a}sz\,\, L.\,\, Combinatorial\,\, problems\,\, and\,\, exercises.\,\, -\,\, Budapest:\,\, Acad\acute{e}miqi\,\, Kiado,\,\, 1979. </math> | |||
Текущая версия от 11:45, 19 сентября 2011
Теорема Татта (W.T.Tutte, 1947) — Граф [math]\displaystyle{ \,G }[/math] имеет совершенное паросочетание тогда и только тогда, когда число нечетных компонент [math]\displaystyle{ c_{1}(G \setminus X) }[/math] подграфа [math]\displaystyle{ G \setminus X }[/math] для любого подмножества вершин [math]\displaystyle{ X \subseteq V(G) }[/math] удовлетворяет неравенству
- [math]\displaystyle{ c_{1}(G \setminus X) \leq |X|. }[/math]
Литература
- Татт У. Теория графов. — М.:Мир, 1988.
- Bondy J.A., Murty U.S.R. Graph theory with applications. — New York; Amsterdam; Oxford: North-Holland, 1976.
- [math]\displaystyle{ Lov\acute{a}sz\,\, L.\,\, Combinatorial\,\, problems\,\, and\,\, exercises.\,\, -\,\, Budapest:\,\, Acad\acute{e}miqi\,\, Kiado,\,\, 1979. }[/math]