Правильное паросочетание

Материал из WikiGrapp
Версия от 18:26, 22 декабря 2009; Glk (обсуждение | вклад) (Создана новая страница размером '''Правильное паросочетание''' (''Proper matching'') - ''частичное паросочетание'' <math>\{A...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

Правильное паросочетание (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] является множеством без дефицита (или с дефицитом, равным нулю) в полученном графе.

Литература

[Оре]