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

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
(не показана 1 промежуточная версия этого же участника)
Строка 1: Строка 1:
'''Ядро орграфа''' (''[[Kernel of a digraph]]'') -
'''Ядро орграфа''' (''[[Kernel of a digraph]]'') множество [[вершина|вершин]], являющееся одновременно и ''независимым'', и ''доминирующим''. Каждый [[орграф]], не имеющий [[контур|контуров]] нечетной длины, обладает ядром.
множество [[вершина|вершин]], являющееся одновременно и ''независимым'', и
 
''доминирующим''. Каждый [[орграф]], не имеющий [[контур|контуров]] нечетной длины,
обладает ядром.
Орграф <math>D</math> называется
Орграф <math>D</math> называется
(1) квази <math>KP</math>-орграфом, если каждый собственный индуцированный
 
[[подграф]] в <math>D</math> имеет ядро; (2) ядровым совершенным орграфом или
(1) квази <math>KP</math>-орграфом, если каждый собственный индуцированный [[подграф]] в <math>D</math> имеет ядро;  
<math>KP</math>-орграфом, если каждый индуцированный подграф имеет ядро; (3)
 
критическим ядровым несовершенным орграфом или <math>CKI</math>-орграфом, если
(2) ядровым совершенным орграфом или <math>KP</math>-орграфом, если каждый индуцированный подграф имеет ядро;
<math>D</math> --- квази <math>KP</math>-орграф и не имеет ядра
(''[[Вершинное ядро]], [[Ядро реберное]]'').
(3) критическим ядровым несовершенным орграфом или <math>CKI</math>-орграфом, если <math>D</math> квази <math>KP</math>-орграф и не имеет ядра (''[[Вершинное ядро]], [[Ядро реберное]]'').
 
[[Файл:Kernel of a digraph.png]]
 
==Литература==
==Литература==
[Лекции]
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.

Текущая версия от 12:05, 13 октября 2011

Ядро орграфа (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]-орграф и не имеет ядра (Вершинное ядро, Ядро реберное).

Kernel of a digraph.png

Литература

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