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

Определение

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

Примечания

Литература

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