4194
правки
Теорема Татта: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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> | |||