Правильное паросочетание: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
Строка 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.