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

Материал из WikiGrapp
Перейти к:навигация, поиск

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

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

Литература

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