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

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

ОпределениеПравить

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

СвойстваПравить

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

ЛитератураПравить

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