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

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

338

 

lnp c n n

. Покажите, что при

1c 

граф

 

,G n p

почти наверное

связен

, а при

1c 

– почти наверное не связен.

в)** Пусть

 

2lnp n n

, причем длина (вес)

каждого появив-

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

нены ребрами и какие длины у этих ребер – случайная величина,

имеющая равномерное распределение на отрезке

 

0, 2r

. Покажите, что

тогда почти наверное граф

 

,G n p

имеет гамильтонов цикл, причѐм

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

плотная концентрация) около

Литература

1. Перепелица В. А. Асимптотический подход к решению некоторых

экстремальных задач на графах // Проблемы кибернетики. 1973.

Т. 26. С. 291–314.

2. Колчин В. Ф. Случайные графы. М.: Физматлит, 2004.

3. Алон Н., Спенсер Дж. Вероятностный метод. М.: Бином, 2007.

Задача к приложениям А. В. Колесникова, Е. В. Гасниковой

(принцип концентрации площади сферы; А. Пуанкаре, 1911). Пока-

жите, что если в многомерном шаре задано равномерное распределение

вероятностей и согласно этому распределению вероятностей сгенериро-

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

концы этих векторов будут лежать почти на границе шара и эти два

случайных вектора будут почти ортогональны.

Указание. Нетривиально второе утверждение (про ортогональ-

ность). Для того чтобы его установить, покажите, что доля от площади

всей сферы

(радиуса

) в



(

3n 

), которую занимает площадь

сегмента, проектирующегося в отрезок

 

,ab

, скажем, оси

, равна

 

 

x r dx

P a b

x r dx









Фиксируя

1r 

и устремляя

к бесконечности, получите

Из любой вершины можно добраться в любую другую по ребрам. Словосочетание «поч-

ти наверное» означает, что вероятностная мера тех графов, для которых это не так, стре-

мится к нулю с ростом

339

 

 

, ~1 2exp 2Pn

   

  

В статистической физике







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

распределен по поверхности постоянной энергии,

то для того чтобы

найти (следуя Максвеллу) распределение компонент вектора скорости,

скажем,

, нужно осуществить термодинамический скейлинг (термо-

динамический предельный переход)

n 



  

 

exp

, exp

exp

P a b dx





















  















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

в статистической физике.

Литература

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

М.: МЦНМО, 2008. С. 48–56.

Задача к приложениям Е. В. Гасниковой, А. В. Колесникова,

А. М. Райгородского (изопериметрическое неравенство и принцип

концентрации меры; П. Леви, 1919). Число



называют медианой

функции

, если

 

: 1 2

x S f x



  



 

: 1 2

x S f x



  



где

 





– равномерное мера на единичной сфере



. Пусть

– измеримое (борелевское) множество на сфере

. Через



будем

обозначать



-окрестность множества

на сфере

. Предположим

теперь, что в некотором царстве, расположенном на

, царь предло-

Равномерное распределение на поверхности постоянной энергии возникло из-за того, что

инвариантной (и предельной по эргодической гипотезе) мерой для гамильтоновой систе-

мы будет как раз равномерная мера Лиувилля (фазовый объем сохраняется). Поскольку

выполняется закон сохранения энергии, то система «живет» на поверхности постоянной

энергии. Следовательно, носитель инвариантной меры сосредоточен именно на этой по-

верхности.

340

жил царице Дидоне построить «огород с заданной длиной забора». Ца-

рица хочет, чтобы еѐ огород при заданном периметре имел наибольшую

площадь. Таким образом, царице надо решить изопериметрическую

задачу (такие задачи обычно рассматриваются в курсах вариационного

исчисления). Решение этой задачи хорошо известно – «круглый ого-

род». Для нас же полезно рассмотрение двойственной задачи, имеющей

такое же решение: при заданной площади огорода спроектировать его

так, чтобы он имел наименьшую длину забора, его ограждающего. Ис-

пользуя решение обобщения двойственной задачи на случай

3n 

, по-

кажите, что если

 

12A





, то

 

1 2exp 2An



  

  

Пусть теперь на

задана функция с модулем непрерывности

       

 

sup : , , ,

f x f y x y x y S

   

   

     

Тогда

   

 

: 2exp 2

x S f x n

     

    



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

птотически близка к среднему значению (математическому ожиданию).

Аналогичное неравенство можно получить (М. Талагран, 1996), напри-

мер, для модели случайных графов (Эрдѐша–Реньи). И исследовать

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

на случайных графах: число независимости, хроматическое число и т.п.

Литература

1. Ledoux M. Concentration of measure phenomenon. Providence, RI,

Amer. Math. Soc., 2001 (Math. Surveys Monogr. V. 89).

2. Алон Н., Спенсер Дж. Вероятностный метод. М.: Бином, 2007.

Задача к приложениям Е. В. Гасниковой, А. В. Колесникова,

А. М. Райгородского (изопериметрическое неравенство Талаграна и

его приложения; М. Талагран, 1996). а)* Пусть заданы множества



1,...,in

элементарных исходов. На этих множествах заданы вероят-

ностные меры

1,...,in

. Положим

i

  







Введѐм взвешенную метрику Хэмминга:

341

 

x y i

d x y













и определим

   

, min ,

d x A d x y









  

   

, sup ,

x A d x A















. Пусть

A

. Определим t-окрестность (

0t 

) множества

по формуле

 

 

A x x A t



  



Покажите, что тогда справедливо следующее неравенство:

   

 

1 exp 4

P A P A t  

б)** Пусть в сельском районе, имеющем форму квадрата со сторо-

ной 1, находится

домов (

1n 

), размерами которых можно пренеб-

речь по сравнению с линейным размером района. Будем считать, что

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

распределению

 

0,1R

) и независимо выбирал их местоположения.

Почтальону необходимо обойти все

домов ровно по одному разу (от

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

мой). Обозначим через

TSP

длину наикратчайшего из таких путей

(кратчайший гамильтонов путь). Используя п. а), покажите, что найдут-

ся такие постоянные

0c 





, не зависящие от

, что

 

 

exp 4P TSP E TSP t t c   

, где

 

E TSP n





в)*** Пусть в условиях п. б) требуется построить систему дорог ми-

нимальной суммарной длины

SteinerTree

, по которой можно было бы

добраться из любого дома в любой другой (дерево Штейнера с мини-

мальной суммарной длиной ребер). Получите неравенство о плотной

концентрации с.в.

SteinerTree

в окрестности своего математического

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

дѐт

 

E SteinerTree

при

n 

Литература

1. Ledoux M. Concentration of measure phenomenon. Providence, RI,

Amer. Math. Soc., 2001 (Math. Surveys Monogr. V. 89).

2. Алон Н., Спенсер Дж. Вероятностный метод. М.: Бином, 2007.

3. Dubhashi D. P., Panconesi A. Concentration of measure for the analysis

of randomized algorithms. Cambridge University Press, 2009.

4. Gromov M. Metric Structures for Riemannian and Non-Riemannian

Spaces. With Appendices by M. Katz, P. Pansu, and S. Semmes. Mod-

ern Birkhäuser Classics, 2001; Chapter



342

Задача Штейнера

и задачи на графах транспортных сетей

Е. Г. Молчанов

(при участии Р. А. Гимадеева, Ю. В. Дорна,

С. П. Тарасова, П. А. Шишкина)

Приведенные задачи разделяются на два типа: задачи, связанные

с задачей Штейнера на плоскости, и задачи на транспортных графах.

Последние обычно являются (возможно, нетривиальными) случаями,

разновидностями и усложнениями нескольких

стандартных задач: зада-

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

мального потока, а также транспортной задачи. Этот задачный раздел

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

одна из таких «стандартных» задач, далее – задачи, которые связаны с

первоначальной «стандартной» задачей.

Если в задачах требуется оценить время работы программы, бу-

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

ка 10

операций с плавающей точкой в секунду. Остальные параметры

этого компьютера (например, оперативную память) будем считать неог-

раниченными.

Часть 1. Минимальная сумма расстояний

Задача 1. Согласно плану в районе строятся несколько домов, в

каждом из которых будет проживать определенное количество человек.

Нужно построить парковку, чтобы сумма расстояний, пройденных каж-

дым человеком до парковки, была минимальной.

а) Где нужно построить парковку, если есть три одинаковых дома?

б) Докажите, что если все дома не лежат на одной прямой, то у зада-

чи ровно одно решение.

Задача 2. Для решения задачи 1 о минимальной сумме расстоя-

ний можно воспользоваться следующей гамильтоновой системой: на

плоский фанерный лист кладется карта района и в центрах домов про-

сверливаются маленькие дырочки. Через дырочки продеты нерастяжи-

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

количеству жителей в соответствующем доме. Начала всех нитей завя-

заны в один узел. Будем считать узел достаточно большим: он не будет

пролезать в дырочки.

343

а) Докажите, что (при условии, что все точки не лежат на одной

прямой), если «отпустить» все грузики, узел застрянет в точке с мини-

мальной суммой.

б) Может ли узел застрять в вершине?

в) На основе описанной гамильтоновой системы предложите итера-

ционный процесс решения задачи о минимальной сумме расстояний и

оцените его скорость сходимости.

Задача 3. Предположим теперь в задаче 1, что от домов до пар-

ковки можно строить только «вертикальные» и «горизонтальные» до-

рожки (т.е. дорожки направления юг–север и запад–восток).

а) Где теперь нужно строить парковку, чтобы сумма расстояний до

домов по дорожкам была минимальная.

б) Может ли у пункта а) быть не единственное решение? Как в об-

щем случае выглядит область с минимальной суммой расстояний?

Указание. Сведите эту задачу к задаче о поиске минимального

расстояния в одномерном случае (все дома лежат на одной прямой)

Часть 2. Минимальное остовное дерево

Задача 4. N точек-пунктов (вершин графа) соединены между со-

бой дорогами. Каждая дорога соединяет две точки и имеет некоторую

длину. Известно, что из любой такой точки до любой другой можно

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

дорог, так чтобы от любой точки можно было добраться до любой дру-

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

была минимальной.

Иными словами, в графе со взвешенными ребрами нужно найти

минимальное остовное дерево.

а) Покажите, что при решении этой задачи можно считать, что про-

извольные две точки соединены дорогой (т.е. граф полный).

б) Какую сложность имеют стандартные алгоритмы Прима и Крас-

кала; как эта сложность зависит от способов хранения информации,

нужной для алгоритмов (например, матрицы расстояний).

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

точек-вершин – 1000.

Задача 5.

а) В задаче 4 проектировщик решил искать нужные дороги среди га-

мильтоновых циклов, т.е. среди маршрутов, выходящих из какой-то

344

вершины и последовательно проходящих через все остальные вершины.

Покажите, что найденное проектировщиком решение может в любое

количество раз по длине превосходить минимальное (уточнить, что

вкладывается в слово «минимальное»).

б) Оцените время поиска гамильтонова цикла. Примите количество

вершин равным 1000 (100, 10). Сравните его с временем поиска мини-

мального остовного дерева.

Задача 6. Дорожная сеть города была построена следующим об-

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

предусмотренной генпланом, и он соединялся дорогой с тем микрорай-

оном, до которого расстояние было наименьшим. После постройки го-

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

зующей дерево. Будем считать, что расстояния между каждыми двумя

микрорайонами известно до постройки и никаких географических огра-

ничений на эти расстояния нет.

Сумма длин всех построенных дорог зависит от того, в каком по-

рядке были построены микрорайоны. Докажите, что отношение макси-

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

угодно большим числом.

Задача 7. В некоторых местах построены несколько микрорай-

онов и несколько станций метро. Будем считать, что от любой станции

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

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

Нужно построить минимальную по суммарной длине систему дорог так,

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

можно, воспользовавшись метро.

Как свести эту задачу к задаче 4 о минимальном остовном дере-

ве?

Указание. Будем считать, что от любой станции метро до любой

другой можно добраться за нулевое время. Тогда, считая все станции

метро одной вершиной, определите расстояния от метро до микрорай-

онов нужным образом.

Часть 3. Задача Штейнера

Задача 8. Несколько городов на плоскости нужно соединить до-

рогами так, чтобы из любого города можно было бы доехать до любого

другого по построенным дорогам, и суммарная длина построенных до-

345

рог была бы минимальна. Расстояния считаются по обычной, Евклидо-

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

узлы – пересечения нескольких дорог.

а) Решите задачу для четырѐх городов, расположенных в вершине

квадрата. Объясните, почему найденное решение не обладает всеми

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

б) Докажите, что в оптимальной системе дорог в любом «вспомога-

тельном» узле должны сходиться ровно три дороги под углами в 120°

друг к другу.

в) Решите задачу для десяти городов, расположенных в вершинах

правильного 10-угольника.

Задача 9. Сетью Штейнера называется систем прямых дорог, та-

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

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

следующими свойствами:

1. В каждом вспомогательном узле сходятся ровно три дороги под

углами в 120° друг к другу.

2. Из каждого города должно выходить не более трех дорог; если

из города выходят две дороги – они должны образовывать угол

не менее 120°, если три – все образованные ими углы должны

быть по 120°.

а) Обязана ли такая сеть обладать минимальной суммой расстояний

среди всех возможных сетей дорог (таких, что из любого города можно

доехать до любого другого)?

б) Покажите, что сеть с минимальной суммой расстояний нужно ис-

кать среди возможных сетей Штейнера.

Задача 10. Проектировщик соединил некоторые пары городов на

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

другой можно было бы доехать по построенным дорогам, и суммарная

длина построенных дорог при этом была бы минимальной. Будем счи-

тать, что все дороги пересекаются вне города на разных уровнях – съе-

хать с одной дороги на другую можно только в городах.

а) Докажите, что в оптимальном решении задачи 9 не будет дорог,

пересекающихся вне городов.

б) Докажите, что решение задачи 9 по суммарной длине построен-

ных дорог не более чем в два раза превосходит решение задачи 8.

Замечание. Отношение минимального остовного дерева (веса

ребер – расстояния на плоскости) к минимальной сети Штейнера назы-

346

вается числом Джильберта–Поллака. В п. б) предстоит доказать, что это

отношение не превосходит числа 2. Это грубая оценка сверху, точная

оценка –

в) Приведите пример, когда оценка

достигается.

Замечание. Построение минимальной сети Штейнера является

NP-трудной задачей, поэтому нахождение минимального остовного де-

рева среди графа городов (вершины – города, расстояния между парами

вершин считаются по обычной, Евклидовой метрике) является полино-

миальным приближенным решением задачи Штейнера с коэффициен-

том приближения

(найденная длина дорог минимального остов-

ного дерева не более чем в

превосходит оптимальное решение).

Часть 4. Кратчайший путь

Задача 11. Пусть есть некоторая система дорог, каждая из кото-

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

время движения по этой дороге. Требуется доехать из пункта А в пункт

Б за минимальное время. Иными словами в графе со взвешенными реб-

рами требуется найти кратчайший путь из одной вершины в другую.

а) Оцените сложность алгоритма Дейкстры и время его работы, если

количество вершин-пунктов равно 1000.

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

зависит от направления (т.е. граф – ориентированный). Как изменится

время решения пункта а)?

Замечание. Разумеется, при поиске кратчайшего расстояния на

реальной сети дорог всегда рассматривают ориентированные графы. В

последующих задачах этого параграфа, если неуказанно обратное, гра-

фы будут ориентированными.

Задача 12. В задаче 11 будем считать, что время проезда по оп-

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

этот участок. Для упрощения время проезда каждого участка мы будем

считать целым неотрицательным числом

 

0ij

: мы движемся от i-го

перекрестка к j-му, начиная движение в момент времени

(очевидно,

также целое неотрицательное).

Хотя и принято считать, что «точность» этой оценки доказана около 20 лет назад, в

известном нам оригинальном доказательстве имеются «лакуны».

347

Как свести эту задачу к задаче 11 о кратчайшем пути в графе, ве-

са ребер которого не изменяются со временем?

Указание. Постройте новый граф, сопоставив одной вершине ис-

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

времени.

Задача 13. M автомобилям, первоначально находящимся в каких-

то пунктах (вершинах графа), необходимо встретиться в одном месте

(может быть, на дороге, соединяющей две вершины) и передать друг

другу важную информацию. К сожалению, машинам негде припарко-

ваться, поэтому останавливаться не разрешено, но разрешено поворачи-

вать или разворачиваться в любом направлении в каждой вершине. Бу-

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

все дороги, соединяющие некоторые пары перекрестков, требуют еди-

ницу времени для их прохождения.

Найдите минимальное время, необходимое для встречи.

Задача 14. Из пункта А в пункт Б (вершин транспортного графа)

нужно добраться с помощью общественного транспорта, возможно, с

пересадками. Каждый вид общественного транспорта ходит от какого-

то одного пункта-вершины до какого-то другого строго по расписанию;

расписание представляет собой таблицу времен отправлений из началь-

ного пункта и соответствующих им времен прибытий в конечный. Пе-

ресадка на другой вид транспорта в промежуточном пункте возможна,

если время отправления превосходит время прибытия в этот пункт на

предыдущем виде транспорта. Будем считать, что ровно в 12:00 мы ока-

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

сможем добраться до пункта Б, пользуясь общественным транспортом.

Приведите алгоритм решений этой задачи (например, метод вет-

вей и границ) и оцените сложность его работы.

Задача 15. В задаче 11 будем считать, что на некоторых верши-

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

ной дороги на другую в этой вершине.

Как свести эту задачу к задаче 11 о минимальном графе, в кото-

ром не существует запрещенных поворотов.

Указание. Как и в задаче 12, нужно превратить одну исходную

вершину в несколько.

Замечание. См. ниже задачу «Преобразования запрещенных ма-

невров», являющуюся обобщением этой задачи.