Pour ceux qui aiment raisonner: sujet de la rue d'ulm

[berbera]

bonjour,
si vous avez des pistes, des suggestions pour m'aider à avancer dans l'analyse de ce sujet, je vous en serai très reconnaissante car je bloque complètement.
merci d'avance
On définit un graphe fini G comme la donnée d’un couple (S , A) où S est l’ensemble fini appelé ensemble des sommets du graphe, et A est une partie de l’ensemble
S²={s,t} / s appartient à S, t appartient à S , s différent de t }
Des paires de sommets de S. L’ensemble A est appelé ensemble des arêtes du graphe G.
Par exemple, si G=(S,A) où S={a,b,c,d} et A= {{a,b},{b,c},{c,d},{d,a},{c,e}}, alors G est le graphe dont les sommets sont a,b,c,d,e et pour lequel il existe une arête entre a et b, b et c, c et d, d et a, c et e à l’exclusion de tout autre. On pourra représenter le graphe par le schéma figure 1.












Lorsque A est vide, on dit que G n’a pas d’arêtes et lorsque A=S², on dit que G est un graphe complet.
On appelle coloriage de G à k couleurs, k appartenant aux nombres naturels privés de 0, toute application c : S {1,…,k} (on suppose que l’on dispose de k couleurs différentes numérotées de 1 à k pour colorier les sommets du graphe et que c(s) donne le numéro de la couleur du sommet s). On dit que c est un coloriage propre si deux sommets reliés par une arête n’ont pas la même couleur, c’est-à-dire si pour tous s et t dans S, c(s) différent de c(t) lorsque {s,t} appartient à A.
On notera Pg(k) le nombre de coloriages propres distincts à k couleurs de G et l’on appellera nombre chromatique de G, noté X(G), la plus petite valeur de k pour laquelle il existe un coloriage propre de G ayant ce nombre de couleurs
X(G)=inf{k appartenant à l’ensemble des naturels privé de 0/ Pg(k) différent de 0}

PARTIE 1

1.on pose S={a,b,c}. Combien existe-t-il de graphes distincts dont les sommets sont donnés par S ?
2.on considère S={a,b,c}, A={{a,b},{b,c},{c,a}} et G=(S,A).
a.Calcluer le nombre chromatique X(G) de G.
b. Calculer Pg(k) pour k appartenant aux naturels privés de 0.
3. on pose S={a,b,c,d}, A={{a,b},{b,c},{c,d},{d,a}} et on considère le graphe G=(S,A) que l’on peut représenter par le schéma :









a. Calculer le nombre chromatique X(G).
b. Calculer Pg(k) pour k appartenant aux naturels privés de 0.
4.on suppose maintenant que S contient p éléments avec p différent de 0. Calculer le cardinal de S², ensemble des paires de sommets. Combien existe-t-il de graphes distincts dont les sommets sont donnés par S ?
5. soit G un graphe fini quelconque ayant p sommets, p appartenant aux naturels privés de 0.
a.Montrer que Pg(k) inférieur ou égal à k puissance p, k appartenant aux naturels privés de 0.
c. Montrer que , en cherchant une minoration de Pg(k)pour k assez grand, que Pg(k)k puissance –p a une limite lorsque q tend vers + l’infini, puis calculer cette limite.


PARTIE 2.

Soit p appartenant aux naturels privés de 0, p supérieur ou égal à 3 et Sp={s1,….,sp} un ensemble de p sommets distincts. On appelle graphe linéaire d’ordre p, le graphe Gp=(Sp,Ap) où Ap={{si,si+1}/i appartenant à {1,….,p-1}}.
On appelle graphe cyclique d’ordre p le graphe G’p={Sp,A’p) où A’p= Ap union {{sp,s1}}

















Représentation des graphes G5 et G’4.

1.Calculer PGp(k) pour tout k appartenant aux naturels privés de 0.
2. on note P*Gp(k) le nombre de coloriages propres de Gp à k couleurs pour lesquels c(s1)=c(sp).
a. Montrer que P*Gp+1(k) = PGp(k) – P* Gp (k) pour tout k appartenant aux naturels privés de 0.
b. Calculer la valeur de P*Gp(k) pour tout k appartenant aux naturels privés de 0.
3.Trouver la relation très simple qui lie PG’p(k) et P*Gp+1(k).
4. on veut montrer dans cette question que PG(k) est une expression polynomiale en k pour tout graphe fini G. On suppose donc ici que G = {S,A} est un graphe quelconque ayant p sommets (p appartenant aux naturels privés de 0) et m arêtes (m appartenant aux naturels).
a. si m=0, calculer X(G) et Pg(k) pour k appartenant aux naturels privés de 0.

pour mieux visualiser le sujet:
http://www.lyc-hoche-versailles.ac-versailles.fr/maths/upsmaths/BULLETIN/BULT1999/M99UX1E.PDF

[abcd22]

Bonjour,
Tu bloques à partir d'où ? Les premières questions ne sont pas difficiles quand même !