Ядро орграфа
Материал из WEGA
Ядро орграфа (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]-орграф и не имеет ядра (Вершинное ядро, Ядро реберное).
Литература
- Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.