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

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

Определение

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

Свойства

• Если орграф $D=(V,X)$ допускает функцию Гранди, то найдется вершина $v\in V$ такая, что $g(v)=0$.
• Пусть $D=(V,X)$ - орграф без контуров. Тогда $D$ допускает и притом единственную функцию Гранди . Для графов с контурами справедлив результат "Если граф допускает функцию Гранди $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=\left\{v\in V\mid g(v)=0\right\}$ является ядром этого орграфа.

Литература

• Нефедов В. Н., Осипова В. А. Курс дискретной математики. — М.: МАИ, 1992. — 262 с.