Правильное паросочетание: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''Правильное паросочетание''' (''Proper matching'') - ''частичное паросочетание'' <math>\{A...) |
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> является множеством без дефицита | ||
(или с дефицитом, равным нулю) | (или с дефицитом, равным нулю) | ||
Версия от 17:00, 23 декабря 2009
Правильное паросочетание (Proper matching) - частичное паросочетание [math]\displaystyle{ \{A,M_{A}\} }[/math] в двудольном графе [math]\displaystyle{ (V,V';E) }[/math] такое, что после удаления всех вершин из [math]\displaystyle{ V }[/math] и [math]\displaystyle{ V' }[/math], которые участвуют в [math]\displaystyle{ M_{A} }[/math] и всех ребер с концом в этих вершинах остающееся множество [math]\displaystyle{ V \setminus A }[/math] является множеством без дефицита (или с дефицитом, равным нулю) в полученном графе.
Литература
[Оре]