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

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

Навигация