Récréations mathématiques

Rappels de cours

Un graphe est un couple G = (X, U) où X est un ensemble fini dont les éléments sont appelés les sommets du graphe, et U est une partie du produit X x X dont les éléments sont appelés les arcs du graphe
Un arc (x, y) est généralement représenté graphiquement par une flèche qui relie x à y. Si x  est une sommet du graphe, on note Γ (x ) l'ensemble des successeurs de x, c'est-à-dire
Γ (x) := {y | (x, y) ∈ U}.
Autrement dit ce sont tous les sommets du graphe qui sont à l'extrémité d'un arc partant de x.
Une partie stable d'un graphe est un sous-ensemble S des sommets X du graphe tel qu'aucun couple de sommets de S n'est relié par un arc. Autrement dit, pour tout sommet x de S, l'intersection de S avec Γ (x ) est vide.
Une partie absorbante d'un graphe est un sous-ensemble A des sommets X du graphe tel que pour tout sommet x n'appartenant pas à A, il existe toujours un arc qui relie x à un sommet de A. Autrement dit pour tout sommet x de X \ A, l'intersection de A avec Γ (x ) est non vide.
Une partie stable et absorbante (si elle existe) d'un graphe est appelée un noyau du graphe.
On appelle fonction de Grundy d'un graphe G = (X, U) toute fonction g: X → N telle que
∀ x ∈ X, g(x) = min N \ g (Γ (x))
Autrement dit, la valeur de g(x) est le plus petit entier qui n'a pas déjà été affecté à l'un des successeurs de x.

Projet d'étude

  1. Démontrez qu'un noyau est nécessairement une partie stable maximale et une partie absorbante minimale au sens de l'inclusion.
  2. Démontrez que si un  graphe admet une fonction de Grundy g, alors la partie {x ∈ X | g(x ) = 0} est un noyau du graphe.
  3. On considère le jeu suivant: deux personnes sont faces à une rangée de 7 fleurs et doivent cueillir à tour de rôle une fleur de leur choix à condition qu'elle ne soit pas à coté d'une fleur coupée (i.e. déjà cueillie). Le gagnant est celui qui cueille la dernière fleur. Trouvez une stratégie gagnante à ce jeu en construisant un graphe du jeu, sa fonction de Grundy et le noyau associé.