Функция Гранди (Srutenx Ijgu;n)
Перейти к навигации
Перейти к поиску
Функция Гранди — функция в теории графов.
Определение
[править | править код]Рассмотрим орграф . Функция , ставящая в соответствие каждой вершине целое число , называется функций Гранди для орграфа , если в каждой вершине число является минимальным из всех целых неотрицательных чисел, не принадлежащих множеству и при .
Свойства
[править | править код]- Если орграф допускает функцию Гранди, то найдется вершина такая, что [1].
- Пусть - орграф без контуров. Тогда допускает и притом единственную функцию Гранди [2]. Для графов с контурами справедлив результат "Если граф допускает функцию Гранди , то существует его подграф, не содержащий контуров, имеющий ту же функцию Гранди ". (Erusalimsky I.M. Family of Grandy Functions for oriented graphs. Tr. J. Math 19, No 3, 269-273)
- Если орграф допускает функцию Гранди , то множество вершин является ядром этого орграфа[3].
Примечания
[править | править код]- ↑ Нефедов, 1992, с. 246.
- ↑ Нефедов, 1992, с. 247.
- ↑ Нефедов, 1992, с. 248.
Литература
[править | править код]- Нефедов В. Н., Осипова В. А. Курс дискретной математики. — М.: МАИ, 1992. — 262 с.