Несводимый граф

Материал из WikiGrapp
Версия от 16:28, 24 ноября 2009; Glk (обсуждение | вклад) (Создана новая страница размером '''Несводимый граф''' (''Irreducible graph'') - двудольный граф с множеством вершин <math>V ...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

Несводимый граф (Irreducible graph) - двудольный граф с множеством вершин [math]\displaystyle{ V = S \cup T }[/math], имеющий в точности два наименьших вершинных покрытия [math]\displaystyle{ M_{1}, \; M_{2} }[/math], причем или [math]\displaystyle{ M_{1} \cap S }[/math] и [math]\displaystyle{ M_{2} \cap T }[/math] пусты, или [math]\displaystyle{ M_{1} \cap T }[/math] и [math]\displaystyle{ M_{2} \cap S }[/math] пусты.

Литература

[Харари]