4625
правок
Правильное паросочетание: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Правильное паросочетание''' (''[[Proper matching]]'') | '''Правильное паросочетание''' (''[[Proper matching]]'') — | ||
''частичное паросочетание'' <math>\{A,M_{A}\}</math> в [[двудольный граф|двудольном графе]] | ''частичное паросочетание'' <math>\,\{A,M_{A}\}</math> в [[двудольный граф|двудольном графе]] | ||
<math>(V,V';E)</math> такое, что после удаления всех [[вершина|вершин]] из <math>V</math> и <math>V'</math>, | <math>\,(V,V';E)</math> такое, что после удаления всех [[вершина|вершин]] из <math>\,V</math> и <math>\,V'</math>, | ||
которые участвуют в <math>M_{A}</math> и всех [[ребро|ребер]] с концом в этих вершинах | которые участвуют в <math>\,M_{A}</math> и всех [[ребро|ребер]] с концом в этих вершинах | ||
остающееся множество <math>V \setminus A</math> является множеством без дефицита | остающееся множество <math>V \setminus A</math> является множеством без дефицита | ||
(или с дефицитом, равным нулю) | (или с дефицитом, равным нулю) | ||
в полученном графе. | в полученном [[граф|графе]]. | ||
==Литература== | ==Литература== | ||
* Оре О. Теория графов. — М.: Наука, 1968. | |||