Ядро орграфа: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''Ядро орграфа''' (''Kernel of a digraph'') - множество вершин, являющееся одновременно ...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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]-орграф и не имеет ядра (Вершинное ядро, Ядро реберное).
Литература
[Лекции]