Etude des graphes aléatoires - Jean-Benoît Rossel
35 pages
Français

Etude des graphes aléatoires - Jean-Benoît Rossel

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Description

ÉC O L E P O L Y T E C H N I Q U EFÉ DÉR A L E D E L A U S A N N EEtude des graphes al´eatoiresJean-Benoˆıt RosselProjet de semestreProfesseur responsable : Thomas MountfordChaire de Processus stochastiques6 f´evrier 2006R´esum´eCe projet de semestre a pour but d’´etudier quelques probl`emes li´es aux graphes al´eatoires.C’est une th´eorie qui fut initialement d´evelopp´ee par deux Hongrois, Paul Erd¨ os (1913−1996) et Alfr´ed R´enyi (1921− 1970). Nous allons tout d’abord rappeler quelques fondementsde la th´eorie des graphes et des probabilit´es, puis pr´esenter quelques r´esultats. Nous nousint´eresserons par exemple `a la probabilit´e qu’un graphe al´eatoire contienne une copie d’ungraphe donn´e, ou encore au comportement de ce graphe al´eatoire lorsque son nombre desommets tend vers l’infini. Nous ´evoquerons enfin un probl`eme qui n’est pas encore r´esolu a`l’heure actuelle.Table des mati`eres1 Introduction 21.1 Rappels et notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2 Pr´esentation des mod`eles de base . . . . . . . . . . . . . . . . . . . . . . . . . 62 Outils math´ematiques 82.1 La m´ethode des moments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.2 La m´ethode de Stein . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.3 Le concept des valeurs critiques . . . . . . . . . . . . . . . . . . . . . . . . . . 133 Le probl`eme de l’existence d’une copie d’un graphe donn´e 153.1 ...

Sujets

Informations

Publié par
Nombre de lectures 38
Langue Français

Exrait

Etudedesgraphesale´atoires
Jean-Benoˆıt Rossel
Projet de semestre
Professeur responsable : Thomas Mountford Chaire de Processus stochastiques
6fe´vrier2006
Resum´e ´
Ceprojetdesemestreapourbutd´etudierquelquesproble`meslie´sauxgraphesale´atoires. Cestunethe´oriequifutinitialementd´eveloppe´epardeuxHongrois,PaulErd¨os(19131996)etAlfre´dR´enyi(19211970). Nous allons tout d’abord rappeler quelques fondements delathe´oriedesgraphesetdesprobabilite´s,puispre´senterquelquesre´sultats.Nousnous inte´resseronsparexemple`alaprobabilite´quungrapheale´atoirecontienneunecopiedun graphedonne´,ouencoreaucomportementdecegrapheale´atoirelorsquesonnombrede sommetstendverslinni.N´eronsennunproble`mequinestpasencorer´esolu`a ous evoqu l’heure actuelle.
Tabledesmati`eres
1 Introduction 1.1 Rappels et notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2Pre´sentationdesmod`elesdebase......................... 2Outilsmathe´matiques 2.1Lame´thodedesmoments............................. 2.2Lam´ethodedeStein................................ 2.3 Le concept des valeurs critiques . . . . . . . . . . . . . . . . . . . . . . . . . . 3Leprobl`emedelexistencedunecopiedungraphedonne´ 3.1 Exemple fondamental . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2Lethe´or`emedeBolloba´s.............................. 3.3Casinterm´ediaire.................................. 4 Le probl`me du recouvrement e 4.1 L’enracinement d’un graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2Notationsetth´eore`me............................... 5 Couplages etG-facteurs 5.1Lethe´ore`medeHall................................ 5.2 Etude des couplages parfaits . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Quelques mots sur lesG. . . . . . . . . . . . . . . . . . . . . . . . -facteurs . Bibliographie
1
2 2 6 8 8 10 13 15 15 16 18 22 22 23 27 27 29 31 33
Chapitre 1
Introduction
Lanotiondegrapheale´atoireestapparuepourlapremi`erefoisdansunarticledErd¨osdat´e de1947.Sonmod`lconsistaita`choisir´equitablementungrapheparmiles2(n2qseuaphe)gr e e lonpeutformer`apartirdensurlespsebasaitmndoe`elreem,sosecadnE.stemtsertuaoms deprobabilite´(Ω,F,PsposapheesgrouslnettnoitelcΩesbm`l)tnade´snsommets, la , ou en tribuFustossles-ouseenelbmΩedslte,orpababilit´entientcoPceestd´eneiedamine`era` que pour toutωΩ, on ait P(ω) = 2(2n).(1.1) Aujourdhuionconside`reessentiellementdeuxmod`elesdegraphesale´atoires,quisontle mod`elebinomialetlemode`leuniforme.Nousallonslespr´esenter`alasuitedequelquesrappels et notations.
1.1 Rappels et notations Th´eoriedesgraphes Ond´enitungrapheGapdrueexsnmelbset´noesVetE. Le premier est l’ensemble des sommets deGeplomrcnied´uroP.seteˆrasesediceludestecontlese,rgpaehlietemtnnu ` faudraitencoreconside´rerlafonctiondincidenceϕ:E→ P2(V)qcisoasuiuqahca`eeteˆrae uncoupledesommets.Maisdansceprojetonneconsid´ereraquedesgraphesnonorient´eset simples,etdonconpourrane´gligercettefonctionϕ, car il n’y aura pas de risque de confusion. En effet, pour tous sommetsietjmuxamimuliayruaaarˆete(uneseuletiistsncdi, j). Soit alorsG= (V, Etout´eesilisntutpaehuqle)nurgsetnoresssnoaviunoestitanqco.Lue au long de ce projet : vG=v(G) =|V|=|V(G)|est le nombre de sommets deG. eG=e(G) =|E|=|E(G)|sdteeeeltsbmondereˆraG, eteG(A, B) est le nombre dareˆtesdeGauneeyanttime´rtxsnade´AVet l’autre dansBV. d(G) =eG/vGest lae´edtisndeG. m(G) = maxHGd(H) est laeal´tmexamidneisdeG. N(v) =NG(v) ={wV|(v, w)E}est levoisinage du sommetv. N(S) =NG(S) =SvSN(v)\Sest le voisinage deSV. N(v) =N(v)∪ {v}etN(S) =N(S)Ssont lesvoisinages closrespectifs devetS. deg(v) =degG(v) =|N(v)|etsomms´teldeudegerv. On note aussiδG= minvGdeg(v) ledegre´minimaldeG, et ΔG= maxvGdeg(vixamdleedrge´am)leG.
2
On note parG= (V,P2(V)\E) leocehpargeneml´mpeirtadeG. Knseltgearhppeoss´edantnmetsesomsommetva,snuceˆraeeeterentaqchpaueedir distincts. On l’appellegraphe complet surnsommetsntaireesompl´emetcehpargnoS. alors un graphevideanedt,ps´osndeetmmsolpeD.eteeuqahcsusonucuˆraetemmates Knegndaugela´r´ea`n1. Gestbipartilonsitueprce´eriV=V1V2, avecV1etV2non vides et disjoints, et toutearˆetecontientuneextre´mite´dansV1et l’autre dansV2. Km,nest le graphe biparti avec|V1|=m,|V2|=neˆraneete,enutesommettrechaqu deV1et chaque sommet deV2. C’est ungraphe biparti complet. On appelle´iote`alen branchesle grapheK1,n. • ∅e,temmosnucuatnataenqu´enscoartpselts´edeposphenegraucunearˆete. Cknglouruede´isnguecncyeledk, avec donckateˆrteseksommets. Pkurigned´esmeninuhcgneuedolk, avec donckteseterˆak sommets.+ 1 PourWV, on noteG[W] = (W, E∩ P2(W)) lesous-graphe deGinduit parW. PourFE, on noteG[F] = (V, F) legraphe partiel deGinduit parF. On dit qu’un grapheG0contient une copie induite du grapheGs’il existe un sous-graphe deG0qsotiesui`aherpmoG. Et on dira queG0contient une copie deGs’il existe un sous-graphe partiel deG0e`aorphisomG. On note enfin aut(G) le nombre d’automorphismes deG. L’ensemble des automorphismes deGest un groupe, dont la loi est la composition d’appli-cations,not´eeecetensembleestuenpalpcitaoibnjitiecdevet,ene.Ee´euqahcdtneme´lG danslui-meˆme,etdonctoute´le´mentposse`deuninverse.Lidentit´efaitoced´el´ementneutre, et enfin la composition d’applications est toujours associative. Elle l’est donc en particulier dans cet ensemble. Pour un grapheGpaencilpoitajibnisphesmenftetuaiectivee´u,odnnmoroantuσ:VV telle que pour toute paire de sommets voisinsietjon aσ(i) voisin deσ(j). Ainsi un automorphisme deGedtecha´esdommequesesvrrpe´edrgleseG. Par exemple, dans la figure 1.1,unautomorphismedugrapheconside´re´doitenvoyerlasommetavers un autre sommet de degr´e3,cest-a`-direleaou lecissoilibse´txedleermmsoetpxuedtnemelage´alyeiitsuEn. b. Et une fois que les sommetsaetbont´et´expeuoil´trnli,se´uqsulpayulseneubisiosep fixer les deux autres. Au final on obtient dans ce cas aut(G) = 4.
Fig.1.1 –Exemple de graphe.
3