§ 29. Функция Гранди

Рассмотрим граф и функцию сопоставляющую каждой вершине целое число

Будем говорить, что есть функция Гранди для графа если в каждой вершине значение представляет собой наименьшее из тех целых неотрицательных чисел, которые не принадлежат множеству

и

Итак, для произвольной вершины имеем если и если то равно наименьшему неотрицательному целому числу, не сопоставленному никакой из вершин в

Построим функцию для графа на рис. 115 следующим образом:

(кликните для просмотра скана)

Легко убедиться, сравнивая в таблице столбцы (3) и (4), что -функция Гранди. Не всякий граф обладает функцией Гранди. Например, граф на рис. 116 не обладает гакой функцией. Функция Гранди не всегда определяется однозначно (рис. 117).

Для графа без контуров каждой порядковой функции (она всегда существует) однозначно сопоставляется функция Гранди, если начать с того, что приписать нуль вершинам, из которых не исходит никакая дуга Рассмотрим, например, граф на рис. 118. Порядковая функция этого графа, изображенная на рис. 119, получается «удалением потомков».

Рис. 119.

Вершинам уровня приписывается 0, вершинам уровня приписывается 1, вершинам уровня приписывается 2, так как следующим за вершинам приписаны значения 0 и 1. Вершине В уровня предшествующей вершинам следует приписать значение 1 и т. д.

УПРАЖНЕНИЯ

(см. скан)