Ядро орграфа: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''Ядро орграфа''' (''Kernel of a digraph'') - множество вершин, являющееся одновременно ...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показаны 2 промежуточные версии этого же участника) | |||
| Строка 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> | |||
(''Вершинное ядро, Ядро реберное''). | (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]-орграф и не имеет ядра (Вершинное ядро, Ядро реберное).
Литература
- Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.