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

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

• Если орграф ${\displaystyle D=(V,X)}$ допускает функцию Гранди, то найдется вершина ${\displaystyle v\in V}$ такая, что ${\displaystyle g(v)=0}$[1].
• Пусть ${\displaystyle D=(V,X)}$ - орграф без контуров. Тогда ${\displaystyle D}$ допускает и притом единственную функцию Гранди [2].
• Если орграф ${\displaystyle D=(V,X)}$ допускает функцию Гранди ${\displaystyle g(v)}$, то множество вершин ${\displaystyle N=\left\{v\in V\mid g(v)=0\right\}}$ является ядром этого орграфа[3].

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