Гасников А.В., Кленов С.Л., Нурминский Е.А., Холодов Я.А., Шамрай Н.Б. Введение в математическое моделирование транспортных потоков

Подождите немного. Документ загружается.

Литература

1. Богачев В. И. Гауссовские меры. М.: Наука, 1997.

2. Зорич В. А. Математический анализ задач естествознания.

М.: МЦНМО, 2008.

3. Канторович Л. В. О перемещении масс // ДАН СССР. 1942.

Т. 37. С. 227–229.

4. Ambrosio L., Gigli N., Savar´e G. Gradient ﬂ ows in metric spaces

and in the Wasserstein spaces of probability measures. Lectures in

Math. ETH Zurich, 2008.

5. Brenier Y. Polar factorization and monotone rearrangement of

vector valued functions // Comm. Pure Appl. Math. 1991. V. 44.

P. 375–417.

6. Evans L. C. Partial diﬀerential equations and Monge-Kantorovich

mass transfer. In «Current developments in mathematics».

Cambridge, 1997; Boston: Int. Press, 1999. P. 65–126.

http://math.b erkeley.edu/

evans/

7. Gromov M. Metric structure for Riemannian and non-Riemannian

spaces. V. 152. Boston: Birkh¨auser, 1998.

8. Milman V., Schechtman G. Asymptotic theory of ﬁnite dimensional

normed vector spaces. Lect Notes in Math. V. 1200. Springer, 1986.

9. Ledoux M. The concentration of measure phenomenon. Math-

ematical Surveys and Monographs 89. Amer. Math. Soc., 2001.

10. Levy P. Probl`eme concretes d’analyse fonctionelle. Paris: Gauth ier-

Villars, 1951.

11. Lugosi G. Concentration of measures inequalities. Barcelona, 2009.

http://www.econ.upf.edu/

lugosi/anu.pdf

12. Marton K. A measure concentration inequality for contractive

Markov chains // Geom. Func. Anal. 1997. V. 6. P. 556–571.

13. Milman E. On the role of Convexity in Isoperimetry, Spectral-Gap

and Concentration // Invent. Math. 2009. V. 177. N. 1. P. 1–43.

298

14. Monge G. M´emoire sur la th´eorie des d´edlais et de remblais. Histoire

de l’Acad’emic Royale des science, 1781.

15. Talagrand M. Transportation cost for Gaussian and other product

measures // Geom. Funct. Anal. 1996. V. 6. P. 587–600.

16. Villani C. Topics in Optimal Transportation. Amer. Math. Soc.

Providence. Rhode Island, 2003.

http://math.univ-lyon1.fr/homes-www/villani/

299

А. М. Райгородский

Модели случайных графов

и их применения

В этом приложении дается обзор основных современных направ-

лений в теории случайных графов. Делается акцент на связь моделей

случайного графа с транспортной проблематикой.

1. Введение

Теория графов играет огромную роль в фундаментальной и при-

кладной математике. Ей посвящены сотни монографий и тысячи –

если не десятки тысяч – статей. Разумеется, мы не можем ставить

перед собою цель дать на этих страницах сколь-нибудь подробное из-

ложение теории графов. Нас будет интересовать лишь одно направ-

ление, которое с каждым годом становится все более актуальным.

В рамках этого направления графы изучаются с вероятностной точ-

ки зрения. Типичная постановка вопроса (говоря не совсем строго)

такова: велика ли вероятность того, что граф обладает данным

свойством? Вопрос исключительно важный, и мы в этом не раз убе-

димся ниже. Правда, в нем ни слова не сказано о том, как именно мы

понимаем термин вероятность. Всякий человек, имеющий представ-

ление об аксиоматике Колмогорова, хорошо знает, что м ожно вло-

жить множество разных смыслов в этот термин. И его можно дей-

ствительно определять по-разному. В зависимости от определения

получится та или иная модель случайного графа. С чисто математи-

ческих позиций любая такая модель имеет право на существование.

Однако для приложений – в том числе приложений к транспортной

проблематике – некоторые из этих моделей более интересны, неко-

торые – менее. Соответственно ниже мы расскажем о двух классах

моделей, каждый из которых за десятилетия, прошедшие с момента

Работа выполнена при финансовой поддержке гранта РФФИ 09-01-00294,

гранта Президента РФ МД-8390.2010.1, гранта поддержки ведущих научных

школ НШ-8784.2010.1.

300

своего появления, зарекомендовал себя плодотворным как в рамках

«чистой» математики, так и в рамках ее разнообразных приложе-

ний, среди которых надежность транспортной сети, рост Интернета

и других социальных и биологических сетей, теория алгоритмов и

пр.

Не претендуя на полноту изложения (это было бы нелепо, т.к.

и здесь наука разрослась безгранично), мы постараемся выделить

лишь самые основные и принципиальные моменты теории случай-

ных графов.

2. Модель Эрдеша—Реньи

Этот раздел мы посвятим описанию модели случайного графа,

которая возникла исторически первой. На рубеже 50-х и 60-х годов

ХХ века эту модель предложили классики современной комбинато-

рики и теории вероятностей П . Эрдеш и А. Реньи (см. [1–3]). От-

метим, что Эрдеш – это, пожалуй, одна из самых ярких фигур в

математике ХХ века. Ему принадлежат сотни статей и задач, кото-

рые оказали огромное влияние на развитие многих математиче ски х

дисциплин. Реньи также сыграл значительную роль в формировании

венгерской вероятностной школы, и его именем назван математиче-

ский институт в Будапеште.

2.1. Формальное описание модели

Пусть дано множество V

= {1, . . . , n}, элементы которого мы на-

зовем вершинами. Именно на этом множестве мы будем «строить»

случайный граф. Понятно, что с лучайным будет множество ребер

графа. Мы не хотим сейчас рассматривать графы с кратными реб-

рами (мультиграфы), графы с петлями (псевдографы) и ориентиро-

ванные графы (орграфы). Поэтому мы считаем, что потенциальных

ребер у графа не больше, чем C

штук. Будем соединять любые две

вершины i и j ребром с некоторой вероятностью p ∈ [0, 1] независимо

от всех остальных C

−1 пар вершин. Иными словами, ребра появля-

ются в соответствии со стандартной схемой Бернулли, в которой C

испытаний и «вероятность успеха» p. Обозначим через E случайное

множество ребер, которое возникает в результате реализации такой

схемы. Положим G = (V

, E). Это и есть случайный граф в модели

301

Эрдеша—Реньи. Напомним, что E также обозначает математическое

ожидание (из контекста будет ясно, какое E имеется в виду в том

или ином случае).

Если записывать приведенное только что определение в формате

аксиоматики Колмогорова, то мы имеем вероятностное пространство

G(n, p) = (Ω

, F

, P

n,p

в котором

Ω

= {G = (V

, E)}, F

= 2

Ω

, P

n,p

(G) = p

|E|

(1 − p)

−|E|

. (1)

Здесь через |A| обозначена мощность множества A (количество эле-

ментов), а 2

– это совокупность всех подмножеств множества A.

Элемент сигма-алгебры F

– это набор графов. Если нам хочется

найти вероятность, с которой граф на n вершинах обладает данным

свойством A, то мы просто берем множество A ∈ F

, состоящее из

всех графов, для которых выполнено свойство A, и вычисляем

n,p

(A) =

G∈A

n,p

(G).

Таким образом, вероятность того, например, что случайный граф

связен, – это величина, равная сумме вероятностей всех связных гра-

фов (на фиксированном множестве вершин). Казалось бы, все совсем

просто и мы вряд ли имеем шансы наткнуться здесь на нечто осо-

бенно интересное. Однако дело обстоит прямо противоположным об-

разом: специфика вероятностных методов, которые эффективно ра-

ботают в задачах о случайных графах, позволит нам пронаблюдать

весьма нетривиальные и, главное, неожиданные явления, которые

возникают даже в этой простой модели и которые влекут приятные

следствия для приложений.

Прежде чем двигаться дальше, сделаем еще ряд полезных за-

мечаний. Во-первых, если p =

, то, как видно из формулы (1),

вероятность любого графа равна 2

−C

. Иными словами, в этом спе-

циальном случае все графы равновероятны и всякое утверждение о

вероятности какого-либо свойства – это, по сути, утверждение о доле

графов данным свойством обладающих.

В действительности, мы не только не обязаны предполагать, что

p =

(хотя и этот случай очень важен), мы даже можем считать,

302

что с ростом величины n (числа вершин) вероятность p возникно-

вения ребра изменяется. Иначе говоря, p = p(n) – любая функция,

значения которой заключены между нулем и единицей. Как прави-

ло, в науке о случайных графах важны даже не сами вероятности

событий, но их предельные значения. Почему это так, мы скоро уви-

дим.

Скажем, наконец, что свойство выполнено почти всегда, если его

вероятность стремится к единице при n → ∞.

2.2. Транспортная интерпретация модели

Представим себе, что в некоторой стране есть 10 городов, кото-

рые попарно соединены дорогами. Это довольно сильное предполо-

жение, но пока сохраним его. Допустим, каждая из дорог за опреде-

ленный срок изнашивается (т.е. становится непроезжей) с известной

вероятностью q. При этом износ данной дороги никак не зависит от

совокупного износа остальных дорог. Спрашивается: какова макси-

мальная вероятность q, при которой с вероятностью больше 1/2 не

исчезнет возможность перемещения между любыми двумя города-

ми? По существу, это вопрос о надежности транспортной сети: чем

выше искомая вероятность q, тем, разумеется, сеть надежнее.

Нетрудно видеть, что вопрос о надежности сети – это в свою

очередь вопрос о связности случайного графа. В самом деле, со-

поставим каждому городу вершину i ∈ V

. Тогда «дорога» между

«городами» i и j – это ребро. Износ дороги – это исчезновение ребра.

Значит, утверждение «дорога изнашивается с вероятностью q» рав-

носильно утверждению «ребро появляется с вероятностью p = 1−q».

Таким образом, нас интересует, какова минимальная вероятность p,

при которой в модели Эрдеша—Реньи G(n, p) вероятность связности

графа больше половины (граф, скорее, связен, чем несвязен).

Понятно, что если мы заменим число 10 другим числом, то соот-

ветствующее минимальное p может измениться. Этим и обусловлено

наше желание рассматривать не только постоянные p, но и нетриви-

альные функции p = p(n).

В разделе 2.4 мы обсудим ряд строгих утверждений, касающихся

сформулированного выше вопроса. Однако есть у нас и более сроч-

ное дело: все-таки предположение о том, что города связаны дорога-

ми попарно, чересчур сильное, и в следующем разделе мы приведем

модификацию модели Эрдеша—Реньи, в рамках которой это пред-

303

положение можно будет адекватно ослабить.

2.3. Обобщения модели Эрдеша—Реньи

Пусть по-прежнему V

= {1, . . . , n}. Однако теперь вероятность

ребра между вершинами i и j мы обозначим через p

. Иными сло-

вами, мы, как и раньше, проводим ребра независимо друг от друга,

но с разными вероятностями. В формате аксиоматики Колмогорова

мы получаем вероятностное пространство

G(n, p

) = (Ω

, F

, P

n,p

в котором

Ω

= {G = (V

, E)}, F

= 2

Ω

, P

n,p

(G) =

(i,j)∈E

(i,j)6∈E

(1−p

Важный частный случай описанного пространства получается,

коль скоро мы фиксируем некоторый граф H

= (V

, E

) и полагаем



p, (i, j) ∈ E

0, (i, j) 6∈ E

Иначе говоря, ребра графа H

возникают в случайном графе неза-

висимо друг от друга с одной и той же вероятностью p = p(n) ∈ [0, 1],

а ребра, которых в графе H

нет, не возникают в случайном графе

вовсе. Этот вариант модели принято обозначать G(H

, p). В ней

n,p

(G) = p

|E|

(1 − p)

|−|E|

Ясно, что модель G(H

, p) и есть та самая модель, которая вполне

адекватна вопросу о надежности транспортной сети. На сей раз мы

не обязаны предполагать, что города попарно соединены дорогами,

мы можем с самого начала зафиксировать граф дорог H

и следить

за износом его ребер.

2.4. Некоторые математические результаты

о надежности сети

Прежде всего справедлива следующая теорема.

304

Теорема 1. Рассмотрим модель G(n, p). Пусть p =

c ln n

. Если

c > 1, то почти всегда случайный граф связен. Если c < 1, то

почти всегда случайный граф не является связным.

Этот довольно простой с точки зрения доказательства факт мы

обоснуем в разделе 2.5. Однако при всей своей формальной простоте

теорема 1 несет весьма содержательную и в каком-то смысле неожи-

данную информацию. Действительно, вернемся к вопросу о надеж-

ности сети. Пусть число n городов, попарно соединенных дорогами,

растет. Тогда, разумеется, величина p =

c ln n

довольно быстро стре-

мится к нулю. Тем не менее теорема 1 утверждает, что вероятность

сохранения связности графа при уничтожении его ребер с вероят-

ностью q = 1 − p стремится к единице. Грубо говоря, если городов

1000, то мы можем позволить дорогам разрушаться с вероятностью

≈ 0.993, так что в результате с вероятностью, близкой к единице, пе-

ремещение между любыми двумя городами останется возможным.

Поначалу это кажется противоречащим интуиции, но, по здраво-

му размышлен ию, становится понятно, в чем здесь смысл. Дорог

у нас C

= Θ(n

), вероятность износа дороги равна 1 − Θ(ln n/n).

Значит, ожидаемое количество неизношенных дорог имеет порядок

n ln n. Этого хватает для сохранения связности.

При определенной аккуратности в выкладках, которые мы ча-

стично проведем в разделе 2.5, можно доказать, например, такой

факт.

Теорема 1

′

. Рассмотрим модель G(n, p). Пусть p =

c ln n

. Если

c > 3, то при n > 100

n,p

(G связен) ≥ 1 −

Этот результат совсем замечателен своей конкретностью. Полу-

чается, что при той же тысяче городов и вероятности износа дороги

1 −

3 ln 1000

1000

≈ 0.98 вероятность сохранения связности не меньше, чем

0.999!

Теорема 1 любопытна еще и тем, что в ней наблюдается резкий

скачок от «почти всегда связности» к «почти всегда несвязности».

Функция p(n) =

ln n

служит своего рода рубежом, преодоление кото-

рого означает переход от ненадежности к надежности. Такой пере-

ход принято называть фазовым, а соответствующую функцию p( n)

– пороговой.

305

Следующая теорема с одержит в себе еще более глубокую инфор-

мацию о природе связности-надежности. Она была доказана самими

Эрдешем и Реньи (см. [1–3]).

Теорема 2. Рассмотрим модель G(n, p). Пусть p =

. Если c < 1,

то найдется такая константа β = β(c), что почти всегда раз-

мер каждой связной компоненты случайного графа не превосходит

β ln n. Если же c > 1, то найдется такая константа γ = γ(c),

что почти всегда в случайном графе есть ровно одна компонента

размера ≥ γn.

И снова мы имеем фазовый переход – резкое изменение свойств

случайного графа при преодолении некоторого порога. В данном

случае порогом служит функция p =

. Оказывается, что если веро-

ятность ребра в c > 1 раз «ниже» порога, то все связные компоненты

графа, скорее всего, крошечные – имеющие логарифмический от об-

щего числа вершин размер; если же вероятность ребра в c > 1 раз

«выше» порога, то, скорее всего, найдется компонента с числом вер-

шин порядка n. Такая компонента называется гигантской.

Теорема 2 допускает различные уточнения. Например, можно

утверждать, что при c > 1, помимо единственной гигантской ком-

поненты, в случайном графе ничего сколь-нибудь крупного почти

никогда не возникает: все остальные компоненты снова логарифми-

ческие. Можно еще аккуратнее описывать размер ги гантской ком-

поненты. В действительности, верно не только неравенство ≥ γn, но

и асимптотика ∼ γn. В. Е. Степанов доказал, что при p =

, c > 1,

размер гигантской компоненты асимптотически нормален (см. [4–6]).

В целом изменение свойств случайного графа при изменении ве-

роятности ребра p принято трактовать как эволюцию графа. Нам

кажется, что несколько правильнее говорить о своего рода ис тории

мира. Сначала (при p ≪

) имеет место «феодализм» – весь граф

поделен на несвязанные между собой логарифмические кусочки. За-

тем (при p ≫

) возникает «империя» – гигантская компонента.

Наконец, при p ≫

ln n

империя уничтожает «окраины» и добивается

мирового господства – связности.

В терминах надежности смысл теоремы 2 также очевиден: можно

еще в ln n раз уменьшить вероятность сохранности отдельной доро-

ги, и если не вся страна, то значительная ее часть окажется кон-

солидированной, т.е. не лишенной инфраструктуры – возможности

сообщения между любыми двумя городами.

306

Глубокий интерес представляет, конечно, устройство мира «внут-

ри» фазовых переходов, т.е. при p ∼

и пр и p ∼

ln n

. В первом

случае все совсем сложно, и мы отсылаем читателя к книгам [7–

9]. Во втором случае можно сформулировать, например, следующий

понятный результат.

Теорема 3. Пусть p =

ln n+c+o(1)

. Тогда P

n,p

(G связен) → e

−e

−c

. В

частности, при p =

ln n

вероятность стремится к e

−1

Здесь уже речь не идет о «почти всегда связности» или «почти

всегда несвязности». Здесь асимптотическая вероятность связности

есть, но она лежит в строгих пределах от нуля до единицы.

Все, о чем мы говорили до сих пор, касалось модели G(n, p). Есте-

ственно, модель G(H

, p), будучи более адекватной реальности, яв-

ляется и более сложной для изучения. Главный результат относи-

тельно этой модели принадлежит Г. А. Маргулису (см. [11]).

Теорема 4. Пусть {H

} – последовательность графов, реберная

связность которых стремится к бесконечности при n → ∞. Тогда

существует пороговая функция p для свойства связности случай-

ного графа в модели G(H

, p).

Теорема 4 нетривиальна, и ее доказательство (а также массу ссы-

лок на близкие результаты) можно найти в книге [8]. Разумеется,

поиск пороговой функции, существование которой доказывается в

теореме 4, – это всякий раз сложная задача, повязанная на специ-

фику графов из последовательности {H

Практический смысл теоремы 4 банален: надо строить дороги

так, чтобы связность получающегося графа неуклонно росла. К со-

жалению, в России положение, как правило, противоположное. Даже

в Москве есть много улиц, перекрытие которых означает фактиче-

скую потерю связности. Например, таковы улицы, проходящие под

железными дорогами: они крайне редки и служат единственными

лазейками с одной стороны полотна на другую.

В следующем разделе мы докажем теорему 1, а в разделе 2.6 мы

обсудим основные идеи доказательства теоремы 2. Отметим, что до-

полнительную информацию о поведении случайных графов в модели

Эрдеша—Реньи можно найти в [7–10].

307