4634
правки
Ядро орграфа: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
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>-орграф и не имеет ядра | ||
(''Вершинное ядро, Ядро реберное''). | (''[[Вершинное ядро]], [[Ядро реберное]]''). | ||
==Литература== | ==Литература== | ||
[Лекции] | [Лекции] | ||