Функция Гранди

Функция Гранди — функция в теории графов.

Определение

Рассмотрим орграф $D=(V,X)$. Функция $g(v)$, ставящая в соответствие каждой вершине $v\in V$ целое число $g(v)⩾0$, называется функций Гранди для орграфа $D$, если в каждой вершине $v\in V$ число $g(v)$ является минимальным из всех целых неотрицательных чисел, не принадлежащих множеству $\{g(w)\mid w\in D(v)\}$ и $g(v)=0$ при $D(v)=\varnothing$.

Свойства

• Если орграф $D=(V,X)$ допускает функцию Гранди, то найдется вершина $v\in V$ такая, что $g(v)=0$Шаблон:Sfn.
• Пусть $D=(V,X)$ - орграф без контуров. Тогда $D$ допускает и притом единственную функцию Гранди Шаблон:Sfn. Для графов с контурами справедлив результат "Если граф допускает функцию Гранди $g(v)$, то существует его подграф, не содержащий контуров, имеющий ту же функцию Гранди $g(v)$". (Erusalimsky I.M. Family of Grandy Functions for oriented graphs. Tr. J. Math 19, No 3, 269-273)
• Если орграф $D=(V,X)$ допускает функцию Гранди $g(v)$, то множество вершин $N=\{v\in V\mid g(v)=0\}$ является ядром этого орграфаШаблон:Sfn.

Литература

• Шаблон:Книга