Funcția Grundy

Funcția Grandi este o funcție în teoria grafurilor.

Definiție

Luați în considerare un digraf . Funcția care atribuie un număr întreg fiecărui vârf se numește funcția Grandi pentru digraf dacă numărul de la fiecare vârf este minimul tuturor numerelor întregi nenegative care nu aparțin mulțimii și pentru . $D=(V,X)$ $g(v)$ $v\în V$ $g(v)\geqslant 0$ $D$ $v\în V$ $g(v)$ $\stanga\{g(w)\mid w\in D(v)\dreapta\)$ $g(v)=0$ $D(v)=\varnothing$

Proprietăți

Dacă digraful admite funcția Grandi, atunci există un vârf astfel încât [1] . $D=(V,X)$ $v\în V$ $g(v)=0$
Fie un digraf fără contururi. Apoi admite, de altfel, o funcție Grandi unică [2] . $D=(V,X)$ $D$
Dacă un digraf admite funcția Grandi , atunci mulțimea de vârfuri este nucleul acestui digraf [3] . $D=(V,X)$ $g(v)$ $N=\stanga\{v\în V\mid g(v)=0\right\}$

Note

↑ Nefedov, 1992 , p. 246.
↑ Nefedov, 1992 , p. 247.
↑ Nefedov, 1992 , p. 248.

Literatură

Nefedov V. N., Osipova V. A. Curs de matematică discretă. - M. : MAI, 1992. - 262 p.