У математиці випадковий граф — це загальний термін для позначення імовірнісного розподілу графів. Випадкові графи можна описати просто розподілом ймовірності або випадковим процесом, що створює ці графи. Теорія випадкових графів лежить на стику теорії графів і теорії ймовірностей. З математичної точки зору, випадкові графи необхідні для відповіді на питання про властивості типових графів. Випадкові графи знайшли практичне застосування у всіх галузях, де потрібно змоделювати складні мережі — відома велика кількість моделей випадкових графів, що відображають різноманітні типи складних мереж у різних галузях. У математичному контексті термін випадковий граф означає майже завжди модель випадкових графів Ердеша — Реньї. В інших контекстах будь-яка модель графів означає випадковий граф.
Моделі випадкових графів
Випадковий граф отримують із множини n ізольованих вершин шляхом послідовного випадкового додавання ребер, що з'єднують вершини. Метою моделювання випадкових графів є визначення того, на якому етапі з'являється певна властивість графу. Різні моделі випадкових графів дають різні розподіли ймовірностей на графі.
Найчастіше вивчається розподіл, запропонований [en], що позначається , в якому будь-яке можливе ребро з'являється незалежно з імовірністю . Ймовірність отримання графу з m ребрами дорівнює де .
Близька до нього модель Ердеша — Реньї, що позначається G(n,M), дає однакову ймовірність для всіх графів, які мають рівно M ребер. Якщо позначити з 0 ≤ M ≤ N, G(n,p) буде містити елементів і будь-який елемент випадає з імовірністю . Цю модель можна розглядати як знімок для деякого моменту часу (M) випадкового процесу на графі , який починається з n вершин без ребер і на кожному кроці додається нове ребро, що вибирається рівномірно з множини відсутніх ребер.
Якщо ж починати з нескінченної множини вершин і вибирати кожне можливе ребро незалежно з імовірністю 0 < p < 1, вийде об'єкт G, званий нескінченним випадковим графом. За винятком тривіальних випадків, коли p дорівнює 0 або 1, такий G майже напевно має такі властивості:
Якщо задано будь-які n + m елементів , існує вершина c у V, яка суміжна з кожною вершиною і не пов'язана з жодною з .
Виявляється, що якщо множина вершин зліченна, то існує, з точністю до ізоморфізму, єдиний граф з такими властивостями, а саме граф Радо. Таким чином, будь-який зліченний нескінченний граф майже напевно є графом Радо, який з цієї причини іноді називають просто випадковим графом. Однак аналогічний результат неправильний для не зліченних графів, для яких існує множина (неізоморфних) графів, які задовольняють вищезазначеній умові.
Інша модель, що узагальнює гільбертову модель випадкового графу, — це модель випадкового скалярного добутку. Граф випадкового скалярного добутку пов'язує з кожною вершиною дійсний вектор. Ймовірність ребра uv між будь-якими вершинами u і v є деякою функцією скалярного добутку u • v відповідних їм векторів.
[en] моделюють випадкові графи через імовірності ребер таким чином, що дане ребро існує в зазначений період часу. Цю модель можна поширити на орієнтовані та неорієнтовані графи, зважені і незважені, на статичні й динамічні.
Для M ≃ pN, де N — найбільше можливе число ребер, найчастіше використовуються моделі G(n,M) і G(n,p), які майже завжди взаємозамінні.
[en] утворює особливий випадок, що має властивості, які в загальному випадку можуть відрізнятися від випадкових графів.
Якщо ми маємо модель випадкових графів, будь-яка функція на графах стає випадковою величиною. Завдання вивчення цієї моделі — визначити, або, принаймні, оцінити ймовірність появи властивості.
Термінологія
Термін «майже напевно» в контексті випадкових графів стосується послідовності просторів і ймовірностей, таких що ймовірність помилки прямує до нуля.
Властивості випадкових графів
Теорія випадкових графів вивчає типові властивості випадкових графів, які виконуються з великою ймовірністю для графів, отриманих для певного розподілу. Наприклад, ми можемо запитати для заданих значень n і p, яка ймовірність, що G(n,p) зв'язний. Під час вивчення таких питань дослідники часто концентруються на асимптотичній поведінці випадкових графів — значеннях, до яких прямують різні ймовірності за зростання n. Теорія перколяції описує зв'язність випадкових графів, особливо необмежено великих.
Перколяція пов'язана зі стійкістю графу (званого також мережею). Нехай дано випадковий граф з n вершинами і середнім степенем . Видалимо випадкову 1−p частину ребер і залишимо p частину. Існує критичний поріг перколяції , нижче від якого мережа стає фрагментованою, тоді як вище pc існують величезні компоненти зв'язності .
Випадкові графи широко використовуються в імовірнісному методі, коли намагаються довести існування графів з певними властивостями. Існування властивості на випадкових графах може часто мати наслідком, за лемою регулярності Семереді, існування цієї властивості майже для всіх графів.
Для G(n,r-reg) — це множина r-регулярних графів з r = r(n), таких що n та m — натуральні числа, 3 ≤ r < n, і rn = 2m парне.
Послідовність степенів графу G в Gn залежить тільки від числа ребер у множинах
Якщо множина ребер M у випадковому графі GM достатньо велика, щоб майже всі GM мали мінімальний степінь не менше 1, то майже будь-який GM зв'язний і, для парного n, майже будь-який GM містить досконале парування. Зокрема, в момент, коли зникає остання ізольована вершина, майже у всіх випадкових графах, граф стає зв'язним.
Майже будь-який процес побудови графу з парним числом вершин за досягнення найменшого степеня 1 або випадкового графу за досягнення трохи більше, ніж (n/4)log(n) ребер з близькою до 1 імовірністю забезпечує існування повного парування, за винятком, можливо, однієї вершини.
Для деякої константи c майже кожен позначений граф з n вершинами і як мінімум cnlog(n) ребрами є гамільтоновим. З імовірністю, яка прямує до 1, додавання ребра, що збільшує мінімальний степінь графу до 2, робить його гамільтоновим.
Розфарбовування випадкових графів
Якщо задано випадковий граф G порядку n з вершинами V(G) = {1, …, n}, розфарбування можна отримати за допомогою жадібного алгоритму (вершина 1 фарбується кольором 1, вершина 2 отримує колір 1 якщо вона не суміжна 1, в іншому отримує колір 2, і так далі).
Випадкові дерева
[en] називається дерево або [en], утворене випадковим процесом. У великому діапазоні випадкових графів порядку n і розміру M(n) розподіл кількості дерев порядку k асимптотично підпорядкований закону Пуассона. Типи випадкових дерев включають , [en], [en], декартові дерева, [en], броунівські дерева і випадкові ліси.
Історія
Випадкові графи вперше визначили Ердеш і Реньї в книзі 1959 року «On Random Graphs» і незалежно у статті «Random graphs».
Див. також
Примітки
- [en]. Random Graphs. — Cambridge University Press, 2001.
- . Random Graphs. — London : Academic Press Inc, 1985.
- . Probabilistic Combinatorics and Its Applications. — Providence : American Mathematical Society, 1991.
- Mathematical results on scale-free random graphs. Handbook of Graphs and Networks. — Weinheim : Wiley VCH, 2003.
- E. N. Gilbert. Random graphs. — Annals of Mathematical Statistics. — 1959. — Т. 30. — С. 1141—1144. — DOI:10.1214/aoms/1177706098.
- M. E. J. Newman. Networks: An Introduction. — Oxford, 2010.
- Reuven Cohen, . Complex Networks: Structure, Robustness and Function. — Cambridge University Press, 2010.
- P. Erdős, A Rényi. On Random Graphs I. — Publ. Math. — 1959. — Т. 6. — С. 290—297.
Література
- А.М. Райгородский. Модели случайных графов. — М. : МЦНМО, 2011. — 136 с. — .
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U Vikipediyi ye statti pro inshi znachennya cogo termina Graf Rado U matematici vipadkovij graf ce zagalnij termin dlya poznachennya imovirnisnogo rozpodilu grafiv Vipadkovi grafi mozhna opisati prosto rozpodilom jmovirnosti abo vipadkovim procesom sho stvoryuye ci grafi Teoriya vipadkovih grafiv lezhit na stiku teoriyi grafiv i teoriyi jmovirnostej Z matematichnoyi tochki zoru vipadkovi grafi neobhidni dlya vidpovidi na pitannya pro vlastivosti tipovih grafiv Vipadkovi grafi znajshli praktichne zastosuvannya u vsih galuzyah de potribno zmodelyuvati skladni merezhi vidoma velika kilkist modelej vipadkovih grafiv sho vidobrazhayut riznomanitni tipi skladnih merezh u riznih galuzyah U matematichnomu konteksti termin vipadkovij graf oznachaye majzhe zavzhdi model vipadkovih grafiv Erdesha Renyi V inshih kontekstah bud yaka model grafiv oznachaye vipadkovij graf Modeli vipadkovih grafivVipadkovij graf otrimuyut iz mnozhini n izolovanih vershin shlyahom poslidovnogo vipadkovogo dodavannya reber sho z yednuyut vershini Metoyu modelyuvannya vipadkovih grafiv ye viznachennya togo na yakomu etapi z yavlyayetsya pevna vlastivist grafu Rizni modeli vipadkovih grafiv dayut rizni rozpodili jmovirnostej na grafi Najchastishe vivchayetsya rozpodil zaproponovanij en sho poznachayetsya G n p displaystyle G n p v yakomu bud yake mozhlive rebro z yavlyayetsya nezalezhno z imovirnistyu 0 lt p lt 1 displaystyle 0 lt p lt 1 Jmovirnist otrimannya grafu z m rebrami dorivnyuye N m displaystyle tbinom N m p m 1 p N m displaystyle p m 1 p N m de N n 2 displaystyle N tbinom n 2 Blizka do nogo model Erdesha Renyi sho poznachayetsya G n M daye odnakovu jmovirnist dlya vsih grafiv yaki mayut rivno M reber Yaksho poznachiti N n 2 displaystyle N n choose 2 z 0 M N G n p bude mistiti N M displaystyle N choose M elementiv i bud yakij element vipadaye z imovirnistyu N M 1 displaystyle N choose M 1 Cyu model mozhna rozglyadati yak znimok dlya deyakogo momentu chasu M vipadkovogo procesu na grafi G n displaystyle tilde G n yakij pochinayetsya z n vershin bez reber i na kozhnomu kroci dodayetsya nove rebro sho vibirayetsya rivnomirno z mnozhini vidsutnih reber Yaksho zh pochinati z neskinchennoyi mnozhini vershin i vibirati kozhne mozhlive rebro nezalezhno z imovirnistyu 0 lt p lt 1 vijde ob yekt G zvanij neskinchennim vipadkovim grafom Za vinyatkom trivialnih vipadkiv koli p dorivnyuye 0 abo 1 takij G majzhe napevno maye taki vlastivosti Yaksho zadano bud yaki n m elementiv a 1 a n b 1 b m V displaystyle a 1 ldots a n b 1 ldots b m in V isnuye vershina c u V yaka sumizhna z kozhnoyu vershinoyu a 1 a n displaystyle a 1 ldots a n i ne pov yazana z zhodnoyu z b 1 b m displaystyle b 1 ldots b m Viyavlyayetsya sho yaksho mnozhina vershin zlichenna to isnuye z tochnistyu do izomorfizmu yedinij graf z takimi vlastivostyami a same graf Rado Takim chinom bud yakij zlichennij neskinchennij graf majzhe napevno ye grafom Rado yakij z ciyeyi prichini inodi nazivayut prosto vipadkovim grafom Odnak analogichnij rezultat nepravilnij dlya ne zlichennih grafiv dlya yakih isnuye mnozhina neizomorfnih grafiv yaki zadovolnyayut vishezaznachenij umovi Insha model sho uzagalnyuye gilbertovu model vipadkovogo grafu ce model vipadkovogo skalyarnogo dobutku Graf vipadkovogo skalyarnogo dobutku pov yazuye z kozhnoyu vershinoyu dijsnij vektor Jmovirnist rebra uv mizh bud yakimi vershinami u i v ye deyakoyu funkciyeyu skalyarnogo dobutku u v vidpovidnih yim vektoriv en modelyuyut vipadkovi grafi cherez imovirnosti reber p i j displaystyle p i j takim chinom sho dane rebro e i j displaystyle e i j isnuye v zaznachenij period chasu Cyu model mozhna poshiriti na oriyentovani ta neoriyentovani grafi zvazheni i nezvazheni na statichni j dinamichni Dlya M pN de N najbilshe mozhlive chislo reber najchastishe vikoristovuyutsya modeli G n M i G n p yaki majzhe zavzhdi vzayemozaminni en utvoryuye osoblivij vipadok sho maye vlastivosti yaki v zagalnomu vipadku mozhut vidriznyatisya vid vipadkovih grafiv Yaksho mi mayemo model vipadkovih grafiv bud yaka funkciya na grafah staye vipadkovoyu velichinoyu Zavdannya vivchennya ciyeyi modeli viznachiti abo prinajmni ociniti jmovirnist poyavi vlastivosti TerminologiyaTermin majzhe napevno v konteksti vipadkovih grafiv stosuyetsya poslidovnosti prostoriv i jmovirnostej takih sho jmovirnist pomilki pryamuye do nulya Vlastivosti vipadkovih grafivTeoriya vipadkovih grafiv vivchaye tipovi vlastivosti vipadkovih grafiv yaki vikonuyutsya z velikoyu jmovirnistyu dlya grafiv otrimanih dlya pevnogo rozpodilu Napriklad mi mozhemo zapitati dlya zadanih znachen n i p yaka jmovirnist sho G n p zv yaznij Pid chas vivchennya takih pitan doslidniki chasto koncentruyutsya na asimptotichnij povedinci vipadkovih grafiv znachennyah do yakih pryamuyut rizni jmovirnosti za zrostannya n Teoriya perkolyaciyi opisuye zv yaznist vipadkovih grafiv osoblivo neobmezheno velikih Perkolyaciya pov yazana zi stijkistyu grafu zvanogo takozh merezheyu Nehaj dano vipadkovij graf z n vershinami i serednim stepenem k displaystyle langle k rangle Vidalimo vipadkovu 1 p chastinu reber i zalishimo p chastinu Isnuye kritichnij porig perkolyaciyi p c 1 k displaystyle p c tfrac 1 langle k rangle nizhche vid yakogo merezha staye fragmentovanoyu todi yak vishe pc isnuyut velichezni komponenti zv yaznosti Vipadkovi grafi shiroko vikoristovuyutsya v imovirnisnomu metodi koli namagayutsya dovesti isnuvannya grafiv z pevnimi vlastivostyami Isnuvannya vlastivosti na vipadkovih grafah mozhe chasto mati naslidkom za lemoyu regulyarnosti Semeredi isnuvannya ciyeyi vlastivosti majzhe dlya vsih grafiv Dlya G n r reg ce mnozhina r regulyarnih grafiv z r r n takih sho n ta m naturalni chisla 3 r lt n i rn 2m parne Poslidovnist stepeniv grafu G v Gn zalezhit tilki vid chisla reber u mnozhinah V n 2 i j 1 j n i j V 2 i 1 n displaystyle V n 2 left ij 1 leq j leq n i neq j right subset V 2 qquad i 1 cdots n Yaksho mnozhina reber M u vipadkovomu grafi GM dostatno velika shob majzhe vsi GM mali minimalnij stepin ne menshe 1 to majzhe bud yakij GM zv yaznij i dlya parnogo n majzhe bud yakij GM mistit doskonale paruvannya Zokrema v moment koli znikaye ostannya izolovana vershina majzhe u vsih vipadkovih grafah graf staye zv yaznim Majzhe bud yakij proces pobudovi grafu z parnim chislom vershin za dosyagnennya najmenshogo stepenya 1 abo vipadkovogo grafu za dosyagnennya trohi bilshe nizh n 4 log n reber z blizkoyu do 1 imovirnistyu zabezpechuye isnuvannya povnogo paruvannya za vinyatkom mozhlivo odniyeyi vershini Dlya deyakoyi konstanti c majzhe kozhen poznachenij graf z n vershinami i yak minimum cnlog n rebrami ye gamiltonovim Z imovirnistyu yaka pryamuye do 1 dodavannya rebra sho zbilshuye minimalnij stepin grafu do 2 robit jogo gamiltonovim Rozfarbovuvannya vipadkovih grafivYaksho zadano vipadkovij graf G poryadku n z vershinami V G 1 n rozfarbuvannya mozhna otrimati za dopomogoyu zhadibnogo algoritmu vershina 1 farbuyetsya kolorom 1 vershina 2 otrimuye kolir 1 yaksho vona ne sumizhna 1 v inshomu otrimuye kolir 2 i tak dali Vipadkovi dereva en nazivayetsya derevo abo en utvorene vipadkovim procesom U velikomu diapazoni vipadkovih grafiv poryadku n i rozmiru M n rozpodil kilkosti derev poryadku k asimptotichno pidporyadkovanij zakonu Puassona Tipi vipadkovih derev vklyuchayut en en dekartovi dereva en brounivski dereva i vipadkovi lisi IstoriyaVipadkovi grafi vpershe viznachili Erdesh i Renyi v knizi 1959 roku On Random Graphs i nezalezhno u statti Random graphs Div takozhGraf Rado Skladni merezhi PerkolyaciyaPrimitki en Random Graphs Cambridge University Press 2001 Random Graphs London Academic Press Inc 1985 Probabilistic Combinatorics and Its Applications Providence American Mathematical Society 1991 Mathematical results on scale free random graphs Handbook of Graphs and Networks Weinheim Wiley VCH 2003 E N Gilbert Random graphs Annals of Mathematical Statistics 1959 T 30 S 1141 1144 DOI 10 1214 aoms 1177706098 M E J Newman Networks An Introduction Oxford 2010 Reuven Cohen Complex Networks Structure Robustness and Function Cambridge University Press 2010 P Erdos A Renyi On Random Graphs I Publ Math 1959 T 6 S 290 297 LiteraturaA M Rajgorodskij Modeli sluchajnyh grafov M MCNMO 2011 136 s ISBN 978 5 94057 840 6