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

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

Определение

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

Литература

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