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

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

Версия от 11:40, 2 июня 2010

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

Литература

[Лекции]