WikiSort.ru - Не сортированное

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

Определение

Рассмотрим орграф ${\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 с.