noyau d'un graphe

bonjour tout le monde !
voila j'ai un petit souci avec un exo a rendre sur le noyau d'un graphe j'espere que vous avez un peu de temps : l'enoncé est long

voici donc THE EXO ^^

X est un ensemble fini de cardinal noté n, et T est une partie de X x X (une telle partie s'appelle un graphe de X)
pour x∈X, on note T(x)={y∈X/(x,y)∈T} : T(x)⊂X et ∀y∈X,y∈T(x)⇔(x,y)∈T

I Noyau d'un graphe

on dit qu'une partie S de X est un noyau de T si les deux conditions suivantes sont realisees
∀x∈S,T(x)∩S=∅ et ∀x∈X\S, T(x)∩S≠∅

(j'ecris aussi les questions que j'ai deja faites je sais pas ca peut tres certainement aider mais c'est la question 3 qui me fait bloquer)

1a)montrer que tout noyau de T est non vide et donnez une C.N.S. pour que X soit noyau de T
ici je raisonne par l'absurde pour montrer qu'il est non vide et ma CNS est que pour X noyau T(x) est vide (donc T vide)

1b)Ici X={a,b,c}et T={(a,b);(b,c);(c,a)} montrer que T n'a pas de noyau
1c)Ici X={a,b,c,d}et T={(a,b);(b,c);(c,d);(d,a)} Montrer que T a exactement 2 noyaux
bon la j'utilise une methode exhaustive

2)soit S une partie de X et soit Fs : X→{0,1}, x → 1 si x∈S et 0 sinon (la fonction caracteristique de S)
montrer que S est noyau de T ssi ∀x∈X,Fs(x)=1-Max({Fs(y)/y∈T(x)}) remarque : on convient ici que le " Max" vaut 0 si T(x) est vide
bon donc cette question est faite aussi mais nous arrivons a la question 3 celle qui pose probleme, il y a 4 sous questions

On supposera dans toute la suite du probleme qu'il n'existe pas de circuit dans le graphe de T, c'est a dire que pour tout entier naturel non nul p, il n'existe pas de $p-uplet(x_1$ , $x_2$ , ..., $x_p$ )∈X^p tel que $x_1$ , $x_2$ )∈T, $x_2$ , $x_3$ )∈T,..., $x_{p-1}$ , $x_p$ )∈T, $x_p$ , $x_1$ ) ∈T

on definit par recurrence, les n parties suivantes de X :
X(0)={x∈X/T(x)=∅}
∀k∈[[1;n[[,X(k)={x∈X/x∉X(0)∪X(1)∪...∪X(k-1) et T(x)⊂X(0)∪X(1)∪...∪X(k-1)}
en particulier X(1)={x∈X/x∉X(0) et T(x)⊂X(0)}

donc voila les questions tant attendues (si vous n'etes pas deja parti pour aller chercher des medicaments contre les maux de tete ^^)

a)Montrez que ces parties sont 2 a deux disjointes ( ca j'ai reussi ) et qu'elles recouvrent X (i.e. que leur reunion est X) ( ca par contre ayayaye bon je pense qu'il faut utiliser que le cardinal de X soit n mais je sais pas meme avec l'indication) Indication : pour montrer qu'elles recouvrent X, raisonnez par l'absurde et construisez par recurrence n+1 elements 2 a 2 distincts de X

b)on construit maintenant par recurrence une application g de X dans la paire {0,1} par :
∀x∈X(0),g(x)=1 et ∀p∈[[1,n[[,∀x∈X(p),g(x)=1-Max({g(y)/y∈T(x)}
montrer a l'aide d'une recurrence forte et finie que g est effectivement un application ( ca c'est bon j'ai reussi)

c)construisez un noyau de T indication : utilisez le 2 (la c'est encore ayayaye)

d)Soit S un noyau de T. montrez, a l'aide d'une recurrence forte et finie que Fs=g deuisez en que le noyau T est unique Remarque utilisez directement l'implication $F$ _A $F_B$ ⇒A=B

bon apres la suite sur les fonctions de Grundy n'est pas interessante pour cette partie du dm donc voila

merci a ceux qui arrivent a ce merci et qui ont donc eu le courage de lire jusqu'au bout (bon merci evidement a ceux qui ont essaye de le lire mais normalement vous n'etes pas arrivés ici ^^)
voila et bonne journee a tout le monde