Methode probabiliste pour la coloration de graphes

Frederic Havetmascotte

Description

Methode probabiliste pour la coloration de graphes Frederic HavetMASCOTTE Seminaire Optimisation Discrete – LIRMM – 14 mai 2009 F. Havet MASCOTTE Methode probabiliste

• espace de probabilites


• variable aleatoire


• methode probabiliste


• methode probabiliste pour la coloration de graphes


• probabilites


• probabilites conditionnelles


• variable aleatoire positive

Sujets

• Variable aléatoire
• Méthode probabiliste
• Probabilité
• Probabilité conditionnelle

Informations

• Publié par: pefav
• Publié le: 01 mai 2009
• Nombre de lectures: 54
• Langue: Français

Extrait

F.Havet

M´ethodeprobabilistepourlacoloration graphes

Fre´d´ericHavet

Se´minaireOptimisationDiscre`te–LIRMM–14mai2009

e´M

de

htoedrpoabibiltse

Probabilit´es(discr`etes)

F.Hav

espace de probabilites: (Ω,Pr) ´ Ω est un ensemble fini,elbmesneonlltianch´e Pr: Ω→[0,1]borplibae´tifotincdeont. q. P ω∈Ω Pr(ω) = 1.

distribution uniforme:Pr(ω) = | 1 Ω| pour toutω∈Ω.

´ ´ nt: sous-ensembleAde Ω.Pr(A) = P ω∈A Pr(ω). eveneme

Sous-Additivit´edesProbabilite´s:Pr( S A i )≤ P Pr(A i )

etM´ethoedrpoabibiltse