Правильное паросочетание: различия между версиями
Перейти к навигации
Перейти к поиску
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. | |||
Текущая версия от 11:32, 23 июня 2011
Правильное паросочетание (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] является множеством без дефицита (или с дефицитом, равным нулю) в полученном графе.
Литература
- Оре О. Теория графов. — М.: Наука, 1968.