Fonction de Grundy (graphes)

[aztec21]

Bonjour,

Je suis en Dut info, j'ai une Question.

On suppose qu'il existe une fonction de Grundy g associée au graphe G=(X,U),
Montrer que G ne contient aucune boucle

Merci,

[Maxmau]

Bj

Suppose qu'il existe une boucle (de 3 sommets a,b,c par exemple)
Quelles relations d'inégalité entre g(a), g(b) entre g(b) ,g(c) et entre g(c) et g(a) ?

[aztec21]

comment ça? je comprends pas ce que tu veux dire?

[Maxmau]

comment ça? je comprends pas ce que tu veux dire?

Bj
Excuses
J'ai confondu boucle et circuit.
Soit a un sommet . D'après la définition d'une fonction de Grundy g(a) est , en particulier, un entier distinct des g(x) ou x est une image quelconque de a. Conclusion a ne peut être image de a. Il ne peut y avoir de boucle en a.

Pour un circuit, je crois qu'il peut y avoir une fonction de Grundy sur un graphe orienté possédant un circuit.(graphe à 2 sommets chacun étant image de l'autre)

[aztec21]

Bonjour,

Je te remercie,

J'ai trouvé la solution ce matin. J'avais fait la même erreur que toi en confondant boucle et circuit.

Bonne journée,