CM5

c.f le cm2

Fonction de Grundy

Soit un graphe \(G = (V, E)\) orienté. \(g\) est une fonction de Grundy de G si \(g\) est une application de \(V\) dans \(N\) telle que \(g(v)\) est le plus petit entier non attribué aux successeurs de \(v\)

• En gros pour chaque sommet on essaye de mettre un nombre différent à son successeur (souvent 0 ou 1, on ajoute un nouveau numéro seulement si son successeur et son prédécesseur est le même !
• Les entier qui ont un 0 c'est le noyau.

En fait il faut que chaque prédécesseur et successeur n'ont pas le même nombre

Ensemble répulseur

Ensemble de sommets de \(R\) de \(G\) tel que tout sommet de \(G, R\) à au moins un prédécesseur dans \(R\).