Русская Википедия:Функция Гранди

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

Определение

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

Свойства

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

Литература

• Шаблон:Книга