PROBLEME I Les trois parties peuvent être traitées indépendamment.
NOTATIONS ET DEFINITIONS On dénit un graphe niGcomme la donnée dun couple(S; A)oùSest un ensemble ni appelé ensemble des sommetsdu graphe, etAune partie de lensemble (2) S=f(s; t)= s2S; t2S; s6=tg des paires de sommets deS:LensembleAest appelé ensemble desarêtesdu grapheG: Par exemple, siG= (S; A)oùS=fa; b; c; d; egetA=ffa; bg;fb; cg;fc; dg;fd; ag;fc; egg;alors G est le graphe dont les sommets sonta; b; c; d; eet pour lequel il existe une arête entreaetb; betc; cetd; deta; ceteà lexclusion de toute autre.On pourra représenter ce graphe par le schéma :LorsqueA=;;on dit que le graphe
Figure 1:Représentation du grapheG
(2) na pas darêtes et lorsqueA=S ;on dit queGest un graphe complet. On appellecoloriagedeGàkcouleurs,k2N;toute applicationc:S7! f1; ::; kg(on suppose que lon dispose dekcouleurs di¤érentes numérotées de1àkpour colorier les sommets du graphe et quec(s)donne le numéro de la couleur du sommets):On dit quecest un coloriage propre si deux sommets reliés par une arête nont pas la même couleur, cest-à-dire si pour toussettdansS; c(s)6=c(t)lorsquefs; tg 2A: On noteraPG(k)le nombre de coloriage propres distincts àkcouleurs deGet lon appeleranombre chromatique deG;noté(G)la plus petite valeur dekpour laquelle il existe un coloriage propre deGayant ce nombre de couleurs (G) = inffk2N= PG(k)6= 0g
PARTIE I 1. OnposeS=fa; b; cgexiste-t-il de graphes distincts dont les sommets sont donnés par. CombienS?
2. OnconsidèreS=fa; b; cg; A=ffa; bg;fb; cg;fc; aggetG= (S; A)
(a) Calculerle nombre chromatique(G)deG: (b) CalculerPG(k)pourk2N:
3. OnposeS=fa; b; c; dg,A=ffa; bg;fb; cg;fc; dg;fd; agget on considère le grapheG= (S; A)que lon peut représenter par le schéma
(a) Calculerle nombre chromatique(G): (b) CalculerPG(k)pourk2N:
(2) 4. Onsuppose maintenant queScontientpéléments avecp6= 0:Calculer le cardinal deS ;ensemble des paires de sommets.Combien existe-t-il de graphes distincts dont les sommets sont donnés parS?
p (a) MontrerquePG(k)6kk ;2N: p (b) Montrer,en cherchant une minoration dePG(k)pourkassez grand, quePG(k)ka une limite quand ktend vers+1et calculer cette limite.
PARTIE II Soitp2N; p>3etSp=fs1; ::; spgun ensemble depsommets distincts.On appelle graphe linéaire dordrep, le grapheGp= (Sp; Ap)oùAp=ffsi; si+1)= i2 f1; ::; p1gg: f ff On appelle graphe cyclique dordreple grapheGp= (Sp; Ap)oùAp=Ap[ fsp; s1g:
e Figure 3:Représentation du grapheG5etG4
(krk2N: 1. CalculerPGp)pou 2. OnnoteP(k)le nombre de coloriages propres deGpàkcouleurs pour lesquelsc(s1) =c(sp): Gp (a) MontrerqueP(k) =PG(k)P(k)pour toutk2N: Gp+1Gp p (b) Calculerla valeur deP(k)pour toutk2N: Gp 3. Trouverune relation très simple qui lieP(k)etP(k)= f G Gp p+1 queP(kxpression polynôm 4. Onveut montrer dans cette questionGp)est une eiale enkpour tout graphe ni G:On suppose ici queG= (S; A)est un graphe quelconque ayantpsommets(p2N)etmarêtes(m2N) (a) Sim= 0;calculer(G)etPG(k)pourk2N 0 00 On se place maintenant dans le casm >0:Il existe alors une arêtefs; sg 2A:On noteG= (S; A) 0 00 le graphe obtenu en retirant àGlarêtefs; sg;cest-à-dire pour lequelA=Anffs; sgg:On notera 00 P0(k)le nombre de coloriages proprescdeGàkcouleurs tels quec(s) =c(s): G (b) MontrerquePG(k) =PG(k)P0(k)pour toutk2N: 0 G 00 0000 (c) Montrerquil existe un grapheGayantp1sommets etmarêtes avecm6mtel queP0(k) = G PG(k): 00 (d) Endéduire par récurrence sur la valeur dep+mque, pourp>2; PG(k)est un polynôme de degrép pour lequel p p1 PG(k) =kmk+QG(k) oùQGest un polynôme de degré inférieur ou égal àp2:
3/5
PARTIE III SoitG= (S; A)un graphe ayantpsommets (p>3)etmarêtes. Pourchaques2S;on considère une variable aléatoireCsà valeurs dansf1; ::; kgaveck2N:On suppose que les variables aléatoires sont indépendantes et 1 identiquement distribuées de loi uniforme surf1; ::; kg;cest-à-direP(Cs=j) =pour toutk2 f1; ::; kgets2S: k 1. Onsuppose ques; tetusont3sommets distincts deS:CalculerP(Cs6=Ct)etP(Cs6=CtetCt6=Cu) P 2. OnnoteN= 1où1 s6=Ctla variable aléatoire qui vaut1lorsqueCs6=Ctet0sinon. G Cs6=CtCest fs;tg2A CalculerE(NG), espérance deNG;en fonction deketm: 3. Montrerque la variance deNGvaut k1 V(NG) =m : 2 k 4. Montrerque pour toutk>m; " # 2 k1km 2 P(NG6m1)6P NG( )m>( ) k k
puis montrer que pour tout" >0;il existek2Ntel que pour toutk>k, on a 0 0 1 +" P(NG6m1)6( )m k (on pourra utilisant sans démonstration linégalité suivante :siXest une variable aléatoire telle queE(jXj) E(jXj) existe, alorsP(jXj>M)6;pour tout réelMstrictement positif). M p p1p1 5. Endéduire, sans utiliser les parties précédentes, quePG(k)>kmk+f(k)k ;oùfest une fonction telle quelimf(k) = 0:Comparer ce résultat avec celui de la dernière question de la partie précédente. k!+1
PROBLEME II Dans ce problème, on considère une fonctionf: [0;1]!Rcontinue que lon supposera dérivable sur]0;1[et de dérivée bornée sur]0;1[:Soientp2[0;1],nun entier strictement positif et(Xi)16i6nune famille de variables aléatoires indépendantes et identiquement distribuées de loiBp, cest-à-dire queP(Xi= 1) = 1p(Xi= 0) =p: On pose dans la suite, n X 1 Sn=Xi n i=1 1. (a)Montrer quil existe un réel positifM0tel que 2 8(x; y)2[0;1];jf(x)f(y)j6M0 (b) Montrerquil existe un réel positifM1tel que 2 8(x; y)2[0;1];jf(x)f(y)j6M1jxyj 2 (c) Endéduire que, pour toutréel strictement positif et tout(x; y)2[0;1];on a 2 (xy) jf(x)f(y)j6M0+M1 2 2. OnnoteV(X1)la variance deX1:Montrer que SnM0V(X1) E ff(p)6+M1 2 n n
4/5
A 3. On noteg:]0;+1[!Rla fonction dénie parg(x+) =Bx, oùAetBsont deux constantes réelles 2 x strictement positives.Montrer quegatteint son minimum en un pointxque lon calculera, puis donner la valeur de ce minimum.
4. Déduireque
1=3 2 M SnM1 0p(1p) E ff(p)63 n4n
Sn 5. MontrerqueE(f=( ))Qn(p)oùQnest un polynôme de degré inférieur ou égal àn: n 6. Montrerlexistence, pour tout" >0;dun polynômeRtel que pour toutp2[0;1];jf(p)R(p)j6"et montrer que lon peut supposer 2 27 M0M1 degR <+ 1 2 16"