Noyau d'un graphe

[darkontes]

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(x1,x2, ...,xp);)X^p tel que (x1,x2);)T,(x2,x3);)T,..., (xp-1,xp);)T, (xp,x1) ;)T

3) 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 FA=FB;)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

[Nightmare]

Salut !

Tout est une question disons de relation.

Autrement que de dire que (x,y) est dans T, on pourrait dire que x et y sont en relation.

X(0) correspond aux éléments qui ne sont en relation avec aucun autre.
X(1), les éléments qui sont en relation avec certains autres (au moins un) mais qui eux ne sont en relation avec aucun autre.
X(2), les éléments qui sont en relation avec certains autres, qui eux même sont en relation avec certains autres mais qui eux ne sont en relation avec personne.

etc...
Il y a une idée de hiérarchie, par exemple X(0) est l'ensemble des laveurs de carreaux, X(1), les livreurs de courrier, X(2) le personnel, X(3) les cadres, ..., X(n) le big boss, X(n+1) le big big boss, etc... et la relation serait "être mieux payé que". (Désolé pour l'exemple, il y en a surement d'autres plus pédagogiques :lol3: )

On voit bien que forcément en les prenant tous on a toute l'entreprise. Essaye de montrer pourquoi par l'absurde comme c'est proposé avec ce que je viens de dire en tête, ça permettra peut être de mieux visualiser la chose.

[darkontes]

euh je suis désolé mais n'arrive pas vraiment bien a voir le lien entre :s

[Ben314]

Bonjour,

Je ne sait pas si tu as vu "naivement" ce dont parle l'énoncé :
Tu peut représenter X comme un ensemble de n points et le fait que (x,y) est dans T par une flèche (orientée) du point x vers le point y.
T(x) est l'ensemble des points qui sont "au bout" d'une flèche qui part de x.
X(0) est l'ensemble des points desquels il ne part aucune flèche c'est à dire tels que, partant de x on ne puisse rien faire (en suivant les flèches)
X(1) est l'ensemble des points tel que, partant de x, on peut faire au moins un "chemin" de longueur 1 en suivant les flèches (si x est dans X(1) il ne doit pas être dans X(0)) mais que l'on ne puisse faire aucun chemin de longueur 2 (car, si x est dans X(1) et que (x,y) est dans T alors y est dans T(0)
etc....

L'exemple que te donne nightmare est celui où les points sont les membres d'une entreprise et les flèches signifient "x gagne strictement plus que y".
Cet exemple à le petit inconvéniant de vérifier : (x,y) et (y,z) dans T implique (x,z) dans T
alors qu'en général, ce n'est pas forcément vrai.
Par contre, il a le gros avantage de vérifier trivialement "il n'y a pas de circuit dans le graphe T"

Ce qui ressort surtout de ce point de vue est que, pour montrer que les X(i) recouvrent X, l'hypothèse qu'il n'y a pas de cycles est indispensable : si ton graphe était constitué d'un unique cycle, alors tout les X(i) seraient vides....

Je ne sait pas si tout cela t'aidera à voir la démarche de la preuve du a)....

[darkontes]

au moins je me represente mieux la chose comme ca avec les fleches maintenant ya plus qu'a trouver comment expliquer ca mathematiquement ^^ bon au moins la avec ces deux exemples combinés J'ARRIVE ENFIN A ME REPRESENTER ce qui pour moi etait une bouillie de formule la au moins je vois a peu pres
(bon apres c'est pas pour autant que j'ai repondu a la question mais je vais continuer de chercher et au moins j'ai une vague idee de ce que je dois chercher maintenant ^^ si vous avez 2 ou 3 tuyaux n'hesitez surtout pas a les poster ;p )

[Ben314]

Avec le point de vue "visuel", il semble assez clair que, si un élément n'était dans aucun des X(i), cela signifierait que, partant de x, on peut faire des chemins "aussi long que l'on veut" (en suivant les flèches) or X est fini et il n'y a pas de cycles, c'est à dire qu'on sait qu'il est impossible de tourner en rond...
(c'est là qu'on voit "l'indication" : raisonner par l'absurde va impliquer l'existence d'un chemin de longueur n+1 sans boucle alors que X est de cardinal n !!!)

Visuellement, c'est donc assez simple, MAIS A ECRIRE PROPREMENT c'est une autre affaire....

[Ben314]

Une petite remarque pour la fin de l'exo. (les fonctions de grundy) au cas ou la fin soit aussi "opaque" que le début :
Je ne connais personnellement (et je suis loin d'être super cultivé) qu'une seule application des fonctions de grundy dans les graphes : pour étudier les statégies gagnantes dans un jeu type echec ou dames ou othello-reversi...

Les "points" (i.e. les éléments de X) représentent les différentes configurations possible du jeu (qui doivent être finie, mais aux echecs, le nombre est trés,trés grand...) et les "flèches" (i.e. les éléments de T) représentent les coups autorisés. L'hypothèse de "non existence de circuit" dit que le jeu ne peut pas tourner en rond. C'est par exemple évident dans le cas de l'othello-reversi.