Ядро орграфа

Ядро орграфа (Kernel of a digraph) - множество вершин, являющееся одновременно и независимым, и доминирующим. Каждый орграф, не имеющий контуров нечетной длины, обладает ядром. Орграф [math]\displaystyle{ D }[/math] называется (1) квази [math]\displaystyle{ KP }[/math]-орграфом, если каждый собственный индуцированный подграф в [math]\displaystyle{ D }[/math] имеет ядро; (2) ядровым совершенным орграфом или [math]\displaystyle{ KP }[/math]-орграфом, если каждый индуцированный подграф имеет ядро; (3) критическим ядровым несовершенным орграфом или [math]\displaystyle{ CKI }[/math]-орграфом, если [math]\displaystyle{ D }[/math] --- квази [math]\displaystyle{ KP }[/math]-орграф и не имеет ядра (Вершинное ядро, Ядро реберное).

Литература

[Лекции]