Полунесводимый граф

Материал из WEGA
Версия от 12:25, 17 июня 2011; KEV (обсуждение | вклад)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

Полунесводимый граф (Semiirreducible graph) — двудольный граф с [math]\displaystyle{ V = S \cup T, }[/math] имеющий точно одно наименьшее вершинное покрытие [math]\displaystyle{ \,M }[/math], причем или [math]\displaystyle{ M \cap S, }[/math] или [math]\displaystyle{ M \cap T }[/math] пусто.

Верна теорема Харари и Пламмера: Граф [math]\displaystyle{ \,G }[/math] и его реберное ядро [math]\displaystyle{ \,C_{1}(G) }[/math] совпадают тогда и только тогда, когда [math]\displaystyle{ \,G }[/math] является двудольным полунесводимым или несводимым графом.

Литература

  • Харари Ф. Теория графов. — М.: Мир, 1973.