Ядро орграфа

Ядро орграфа (Kernel of a digraph) — множество вершин, являющееся одновременно и независимым, и доминирующим. Каждый орграф, не имеющий контуров нечетной длины, обладает ядром.

Орграф $D$ называется

(1) квази $KP$-орграфом, если каждый собственный индуцированный подграф в $D$ имеет ядро;

(2) ядровым совершенным орграфом или $KP$-орграфом, если каждый индуцированный подграф имеет ядро;

(3) критическим ядровым несовершенным орграфом или $CKI$-орграфом, если $D$ — квази $KP$-орграф и не имеет ядра (Вершинное ядро, Ядро реберное).

Литература

• Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.