Ядро орграфа: различия между версиями

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

 

 

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

 

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

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

 

 

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