Изменения

Перейти к: навигация, поиск
Нет описания правки
{{Определение
|id = odd
|definition =<tex>\mathrm{odd}({G})</tex> {{---}} число нечетных компонент связности в графе <tex>{G}</tex>, где '''нечетная компонента''' (англ. ''odd component'') {{---}} это [[Отношение связности, компоненты связности#def2|компонента связности]], содержащая нечетное число вершин.
}}
{{Определение
|id = Tutt_set
|definition ='''Множество Татта''' графа <tex>{G}</tex> {{---}} множество <tex>S \subset {V_{G}}</tex>, для которого выполнено условие: <tex>\mathrm{odd}({G} \setminus S) > \left\vert S \right\vert</tex>
}}
}}
 
==См. также==
* [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]
* [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]]
* [[Декомпозиция Эдмондса-Галлаи]]
==Примечания==
Анонимный участник

Навигация