Функция Гранди — функция в теории графов.
Определение Рассмотрим орграф . Функция , ставящая в соответствие каждой вершине целое число , называется функций Гранди для орграфа , если в каждой вершине число является минимальным из всех целых неотрицательных чисел, не принадлежащих множеству и при .
Свойства Если орграф допускает функцию Гранди, то найдется вершина такая, что . Пусть - орграф без контуров. Тогда допускает и притом единственную функцию Гранди . Для графов с контурами справедлив результат "Если граф допускает функцию Гранди , то существует его подграф, не содержащий контуров, имеющий ту же функцию Гранди ". (Erusalimsky I.M. Family of Grandy Functions for oriented graphs. Tr. J. Math 19, No 3, 269-273) Если орграф допускает функцию Гранди , то множество вершин является ядром этого орграфа.
Примечания
Литература
Категория:Теория графов