Grundy funktion

Grandi- funktionen är en funktion inom grafteorin.

Definition

Tänk på en digraf . Funktionen som tilldelar ett heltal till varje vertex kallas Grandi-funktionen för digrafen om talet vid varje vertex är minimum av alla icke-negativa heltal som inte hör till mängden och för . $D=(V,X)$ $g(v)$ $v\in V$ $g(v)\geqslant 0$ $D$ $v\in V$ $g(v)$ ${\displaystyle \left\{g(w)\mid w\in D(v)\right\))$ $g(v)=0$ $D(v)=\varnothing$

Egenskaper

Om digrafen tillåter Grandi-funktionen, så finns det en vertex sådan att [1] . $D=(V,X)$ $v\in V$ $g(v)=0$
Låt vara en digraf utan konturer. Då medger dessutom en unik Grandi-funktion [2] . $D=(V,X)$ $D$
Om en digraph medger Grandi-funktionen , då är uppsättningen av hörn kärnan i denna digraph [3] . $D=(V,X)$ $g(v)$ $N=\left\{v\in V\mid g(v)=0\right\}$

Anteckningar

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

Litteratur

Nefedov V. N., Osipova V. A. Kurs i diskret matematik. - M. : MAI, 1992. - 262 sid.