Tilfældig graf

I matematik er en tilfældig graf en graf , der genereres ved en tilfældig proces . Den første model af tilfældige grafer blev populariseret af Paul Erdős og Alfréd Rényi i en række artikler offentliggjort mellem 1959 og 1968.

De to grundlæggende modeller af Erdős og Rényi

Erdős og Rényis model samler faktisk to modeller, formelt forskellige, men nært beslægtede. I begge modeller

Binomial tilfældig graf

I denne model er hver af n ( n –1) / 2 kanter ofte til stede med sandsynlighed p , fraværende med sandsynlighed 1- p , uanset status for de andre kanter. Tilfældet p = 0,5 blev studeret ved Erdős så tidligt som 1947. Antallet N p kanter følger binomial fordeling af parametre n ( n -1) / 2 og p .

Den ensartede tilfældige graf

I denne model, der ofte bemærkes, vælger vi ensartet en delmængde af M- kanter blandt n ( n -1) / 2 mulige kanter. Når en graf G med n hjørner har M- kanter, er sandsynligheden for G givet ved

Dette er den model , der hovedsageligt studeres i rækken af ​​sædvanlige artikler, der blev offentliggjort af Erdős og Rényi mellem 1959 og 1968.

De to tilfældige processer med grafværdier

Vi opnår således en voksende familie af tilfældige grafer, der danner en kontinuerlig tidsproces med værdier i sættet med grafer. Denne familie vokser i betydningen af ​​inkluderingen af ​​kantsættet: en kant e til stede i er også til stede i, da Hver betegnelse i familien af ​​grafer er en tilfældig tilfældig graf, der er defineret tidligere.

Metafor. Vi kan forestille os hjørnerne på grafen som n øer ved en sø, der kommunikerer ved hjælp af gangbroer (kamme e ), nedsænket på respektive dybder T e under vandoverfladen. Hvis søen gradvist tømmer sit vand, vil vi se broerne gradvist dukke op, og relaterede komponenter, der grupperer flere og flere øer, dannes.

Forbindelser mellem de to modeller

I kraft af Central Limit Theorem eller Hoeffdings ulighed er binomialoven meget koncentreret omkring dens forventning. Mere præcist antallet af kanter N p af en tilfældig lov graf er derfor meget tæt på , især hvis denne sidste mængde er stor foran n  : ja,

Desuden betingede fordeling af at vide, at N p = M er netop af denne grund, hvis M er tæt på , eller, ækvivalent, hvis

Det er generelt accepteret (og ofte demonstreret), at de to modeller og har meget lignende egenskaber.

Går længere, lad T ( k ) betegne den k 'te værdi af sekvensen , når denne sidste sekvens er anbragt i stigende rækkefølge: sekvensen kaldes sekvensen af ordens statistik af sekvensen Når p tager tilfældig værdi T ( M ) , så er det nøjagtigt For at bekræfte de tidligere observationer skal du bemærke, at T ( M ) er meget tæt på i den forstand , at sandsynligheden for , at en konsekvens af berømte resultater fra Donsker og Kolmogorov er

tilfreds

den 1 st og 4 th  vilkår bliver halerne af fordelingen af Rayleigh og Kolmogorov love henholdsvis: i Sammenfattende supremum (når M varierer) af fejlene er af størrelsesordenen 1 / n .

Orden og vækst

En graf kan ses som en del af sættet J kanter, så sandsynligheden plads er her w alle dele af J , som undertiden kan identificere {0,1} J . Denne identifikation er især nyttig, når vi vil anvende Harris ' ulighed .

Tilsvarende siges en del A af Ω at stige, hvis dens indikatorfunktion stiger. Eksempler:

Blandt egenskaberne og parametrene for en graf,

Vi har følgende ulighed:

Harris ulighed  -  inden for rammerne af den binomiale tilfældige graf ,

Bemærkninger:

Forbindelse

Forbindelsestærsklen

Sætning (Erdős, Rényi, 1960)  -  Lad a n = np ( n ) - ln n , eller igen:

Vi siger, at ln ( n ) / n er en smal tærskel for tilslutningsegenskaben, hvor snæverheden henviser til det faktum, at ejendommen er tilfreds, selvom den har tendens til uendelig strengt mindre end

Demonstration

Vi giver os selv en tilfældig graf G n med lovgivningen og en tilfældig graf med loven. Sætningen følger dobbelt-eksponentielle teorem , som selv følger af tælling af isolerede punkter udført i det følgende afsnit. Forbindelse er en voksende egenskab , så snart n er stor nok til det

vi har også

Faktisk har vi selv for at konstruere og bruge de samme ensartede iid-variabler på det samme sandsynlighedsrum Ω som beskrevet i afsnit "De to værdier til tilfældige processer" , for alle ω af Ω,

derfor

og

Hvis det følger heraf, for ethvert reelt tal c ,

eller endda

På den anden side, hvis så for n tilstrækkeligt stort, vil vi have for alle ω , og

Således for ethvert reelt tal c ,

Tælling af isolerede punkter

Det er lettere (mere sandsynligt) at lykkes med at skære n - 1 forbindelserne mellem et punkt og dets komplement end k ( n - k ) forbindelserne mellem en gruppe af k punkter og dets komplement, fordi funktionen f ( k ) = k ( n - k ) stiger meget hurtigt omkring 1, derfor, når k stiger, mange flere kanter at skære og en meget lavere sandsynlighed for at klippe dem alle med succes. Som et resultat, med valget af parameteren p, der er lavet ovenfor, vil grafen G ( n , p ) ikke være "næsten kun" forbundet, hvis den har isolerede punkter, i den forstand at sandsynligheden for at blive forbundet er meget tæt på sandsynligheden for ikke at have isolerede punkter, hvilket er omtrent lig med e –e - c Faktisk har vi følgende resultat:

Isolerede punkter (Erdős, Rényi, 1960).  -  Antag det

Derefter konvergerer antallet X n af isolerede punkter i grafen i lov mod en Poisson-fordeling af parameter e - c .

Demonstration

I det følgende forkortes vi , og vi udgør

Lad X n være antallet af isolerede punkter i Vi ved det

eller

Lad os bruge metoden til faktuelle øjeblikke. Lad jeg n , A være sættet med injektioner af i For alle

Betingelserne for det foregående beløb forekommer faktisk i udvidelsen af, men bortset fra disse vilkår bringer denne udvidelse mange andre udtryk, der tilsyneladende kolliderer. Faktisk enten

derfor

Desuden ved symmetri,

hvor r ( n -1) er antallet af kanter, der potentielt kan være resultatet af et toppunkt på E , og hvor r ( r -1) / 2 er antallet af kanter mellem to hjørner af E , dvs. dem, der tælles dobbelt i det samlede r ( n -1) . Så

Så ved metoden for øjeblikke konvergerer X n i lov til en Poisson-fordeling med parameter μ , og

Denne sætning er en slående illustration af fiskeparadigmet , at når det giver mange muligheder for at observere en sjælden begivenhed ( dvs. d. Usandsynligt), så følger det samlede antal sjældne begivenheder faktisk en Poisson-lov .

Den dobbelteksponentielle sætning

Erdős og Rényi udleder et mere præcist resultat end den smalle tærskelegenskab:

Dobbelteksponentiel sætning (Erdős, Rényi, 1960)  -  Antag det

Demonstration Hvis er uden isoleret punkt, og så er der ringe chance for, at det er andet end forbundet (jf. Spencer, 10 forelæsninger om tilfældige grafer ). Lad B faktisk være en del af og lad k være dets kardinal. Lad os betegne begivenheden "  B er en sammenhængende komponent i  ". Begivenheden kan ses som den (ikke-sammenhængende) forening af k k -2 undergrupper af sandsynligheder

hvilket fører til følgende stigning:

Her angiver antallet af mulige spændende træer for en tilsluttet graf, hvis hjørner ville være elementerne i B , eller endda på en ækvivalent måde antallet af mulige valg af en familie af k- 1 kanter, der gør sættet B relateret. Endvidere er sandsynligheden for at k -1 kanter af spanning tree betragtede faktisk er til stede, og er sandsynligheden for at nogen kant forbinde et toppunkt B til en toppunkt B c er til stede, således at B dvs. ikke kun er forbundet , men også maksimal blandt de tilsluttede dele af grafen.

Begivenheden

afkrydset

I henhold til den hypotese D n , har flere sammenhængskomponenter derfor den mindste af dem (i betydningen antallet af knuder) har højst n / 2 vertices, men dette mindste tilsluttede komponent har mindst to toppunkter, idet X n = 0 . Så

For α > 0 er

så snart

Ligesom en tilsluttet komponent med størrelse større end 2 er meget mindre sandsynlig end en tilsluttet komponent i størrelse 1, er en tilsluttet komponent med størrelse større end 3 meget mindre sandsynlig end en tilsluttet komponent i størrelse 2, hvilket resulterer i gennemgående

Ejendom  -  Når n har tendens til uendelig

Nogle lidt smertefulde beregninger uden at være ærligt vanskelige fører til dette resultat.

Demonstration

Ovenstående grænse for u 2 ( n ) er ikke kun en øvre grænse , men giver faktisk størrelsesorden u 2 ( n ) . Hvad angår resten af ​​summen, skal vi skære den i to, før hver af de to stykker øges:

eller

For og

så snart

Derfor falder for n stort nok hurtigere end en eksponentiel rækkefølge af grund når og

Desuden for vi kan finde c og ρ positive, således at det for alle

For og

så snart n er stort nok. Derfor for og tæt nok på 0,5, tæt nok på 1,

og

Derfor

Lad os ved T n angive det første øjeblik t, hvor grafen er forbundet:

så det

Vi kan så se den dobbeltstrengede eksponentiel teorem som følge på den asymptotiske ekspansion af T n  : hvis Z n er defineret ved det følgende forhold:

derefter hævder den dobbelteksponentielle sætning , at Z n konvergerer i loven mod distributionen af ​​Gumbel , som i en sandsynlig version af noteringen af ​​Landau kunne oversættes med:

Den uendelige tilfældige graf

Erdős og Rényi generaliserede binomialmodellen til tilfældet med en tællbar uendelig graf , hvilket viser, at vi derefter ( næsten sikkert ) opnåede en graf med universalitetsegenskaber (der især indeholder en hvilken som helst endelig eller tællbar graf som en undergraf ); denne graf er blevet genopdaget flere gange og er oftest kendt som Rado-grafen .

Se også

Bemærkninger

  1. Den første artikel, der blev offentliggjort i 1959 , er "On Random Graphs I", Publ. Matematik. Debrecen 6, 290.
  2. (in) P. Erdős , "  Nogle bemærkninger til teorien om grafer  " , Bull. Bitter. Matematik. Soc. , Vol.  53, nr .  4,1947, s.  292-294 ( læs online ). Denne artikel anses ofte for at markere fødslen af ​​den "probabilistiske metode" til undersøgelse af ikke-tilfældige grafer, især for Ramsey-teorien .
  3. For baggrund, se (in) Mr. Karoński Ruciński og A., "Oprindelsen til teorien om tilfældige grafer" , i The Mathematics of Paul Erdős , Berlin, Springer al.  “Algoritmer kombineres. "( Nr .  13),1997, s.  311-336.
  4. For flere detaljer, se Janson, Łuczak og Ruciński 2000 , kap. 2, "Eksponentielt små sandsynligheder".
  5. Se Janson, Łuczak og Ruciński 2000 , afsnit 1.4, “Asymptotisk ækvivalens”, s. 14.
  6. Se (in) Galen R. Shorack og Jon A. Wellner , Empiriske processer med applikationer til statistik , SIAM ,september 2009, 998  s. ( ISBN  978-0-89871-684-9 , læs online ), afsnit 3.8, “Begrænsning af distributioner under nulhypotesen”, s. 142 og kap. 18, “Den standardiserede kvantilproces”, s. 637.
  7. Janson, Łuczak og Ruciński 2000 , Th. 6.7, s. 144.
  8. Se artiklen ”  bijection de Joyal  ”, eller Martin Aigner og Günter M. Ziegler, Guddommelige ræsonnementer , 2 nd  edition, 2006, s. 195-201, Cayleys formel for antallet af træer .

Bibliografi

Relateret artikel

Introduktion af sandsynligheder i grafteori

Eksternt link

Laurent Massoulié, Networks: distribueret kontrol og nye fænomener , 2015

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">