Вероятность в комбинаторике

Что такое комбинаторика? Конечно, на этот вопрос можно ответить многими способами. Однако весьма типичным является следующее мнение: комбинаторика — это набор красивых, но разрозненных задач-головоломок «олимпиадного» типа; всерьез наука не развита и поэтому заниматься ею можно исключительно для развлечения или, если угодно, для тренировки мозгов. В действительности все совсем не так. Современная комбинаторика — это весьма стройная математическая дисциплина, и в ее основе лежат мощные методы, позволяющие решать самые разные задачи, которые без такой методологической базы и впрямь могли казаться разрозненными и чисто развлекательными. Особое место среди упомянутых методов занимает метод, который принято называть вероятностным. Идея его очень проста. Допустим, нам надо найти какой-либо набор объектов, обладающих определенными свойствами. Рассмотрим множество всех подобных наборов, которые могли бы служить «кандидатами» на роль искомого, и выберем из этого множества «случайный» элемент. Если мы докажем, что с положительной вероятностью такой элемент обладает нужными свойствами, то задача будет решена. Разумеется, тут еще надо аккуратно сказать, что мы понимаем и под случайностью, и под вероятностью. Ниже мы поговорим об этом. Тем не менее уже сейчас интуитивно понятно, что целый пласт комбинаторных проблем (обычно именуемых «экстремальными») может быть изучен с помощью описанной технологии.

По вероятностному методу в комбинаторике существует обширная литература (см., например, [1], [2]). В этой короткой заметке мы лишь приведем несколько изящных примеров, иллюстрирующих суть подхода.

Разобьем класс на две группы, или «Свойство В» Эрдёша

Представим себе такую ситуацию. В математическом классе учатся тридцать школьников. Из них семь человек одинаково хорошо и лучше всех остальных решают задачи по комбинаторике, еще семь человек столь же блестяще владеют геометрией, еще семь — алгеброй и т.д. Всего есть тридцать предметов, и по каждому из них имеется ровно семь ведущих специалистов в классе. Очевидно, что множества специалистов пересекаются, так что некоторые школьники в равной мере сильны сразу в нескольких дисциплинах. Хочется так разбить класс на две группы, чтобы в каждой из групп были специалисты по всем тридцати предметам. Всегда ли это возможно?

Давайте переформулируем задачу в более абстрактных терминах. Обозначим через V множество наших школьников. Ясно, что V состоит из тридцати элементов и мы можем считать, что V = {1; 2; ...; 30}. Просто 1 — это, скажем, Петя Андреев, 2 — Коля Иванов, 3 — Маша Петрова и т.д. Теперь семерки ведущих специалистов — это подмножества e₁, ..., e₃₀ в множестве V, имеющие размер семь. Как в точности устроены эти подмножества, мы не знаем; но, как бы они ни располагалась внутри V, нам нужно представить V в виде V₁ c V₂, где группы V₁ и V₂ не пересекаются и в то же время обе группы имеют непустые пересечения со всеми множествами e₁, ..., e₃₀. Назовем элементы V₁ красными, а элементы V₂ синими. В итоге исходный вопрос можно поставить так: верно ли, что, каковы бы ни были семиэлементные подмножества e₁, ..., e₃₀ в множестве V, существует раскраска V в красный и синий цвета, при которой все указанные подмножества неодноцветны (содержат как красные, так и синие элементы)?

Тупой перебор тут вряд ли поможет. В самом деле, количество способов собрать каждое множество e_i из элементов множества V равно . Поскольку множества могут пересекаться и даже совпадать, общее число вариантов выбора e₁, ..., e₃₀ есть
Это нечто запредельное: никакой компьютер не позволит проверить столько ситуаций! А с помощью вероятности задача решается почти мгновенно.

Предположим, совокупность e₁, ..., e₃₀

как-то зафиксирована. Нас интересует выбор раскраски V с известным свойством (неодноцветность каждого e_i). Всего раскрасок, очевидно, 2³⁰. Занумеруем их как-нибудь, напишем номера на карточках, поместим карточки в коробку и тщательно их перемешаем. Теперь, не глядя, запустим руку в коробку и извлечем случайную карточку. С какой вероятностью на этой карточке будет номер данной конкретной раскраски? Разумеется, с вероятностью В науке такой подход называется «классической вероятностной схемой»: в ней все возможные исходы мы считаем равновероятными.

Множества исходов образуют события. Например, событие, состоящее в том, что в случайной раскраске c, найденной по описанной выше схеме, множество e₁ целиком красное, — это, по сути, совокупность всех раскрасок, при которых элементы e₁ красные. Стало быть, при нынешнем подходе вероятность события естественно найти как отношение его размера к величине 2³⁰.

Рассмотрим события A₁, ..., A₃₀. Здесь A_i состоит в том, что в случайной раскраске множест-во e_i одноцветное. Это своего рода «вредоносное» событие. Мы-то хотим, чтобы, напротив, в e_i были элементы обоих цветов. Легко видеть, что вероятность события A_i (ее принято обозначать P(A_i)) есть (с вероятностью все элементы множества e_i красные, и с той же вероятностью все они синие). Значит,

Величина P(A₁ ∪ ... ∪ A₃₀) есть вероятность того, что в случайной раскраске хотя бы одно множество одноцветно, и эта вероятность меньше единицы. Следовательно, с положительной вероятностью каждое множество неодноцветно, и мы имеем утвердительный ответ на наш исходный вопрос: при любой фиксации совокупности e₁, ..., e₃₀ существует нужная нам раскраска. Более того, число 30 не было критичным; вполне можно было заменить его в постановке задачи на что-либо вплоть до шестидесяти трех.

В общем виде задача, которую мы только что решили, была предложена П. Эрдёшем и А. Хайналом в середине XX века. Чтобы правильно ее сформулировать, напомним некоторую терминологию. Во-первых, пара H = (V; {e₁, ..., e_m}) называется гиперграфом. Здесь V — множество вершин, а E = {e₁, ..., e_m} — множество ребер гиперграфа. Гиперграф n-равномерен, если все его ребра имеют размер n. В частности, обычный граф — это 2-равномерный гиперграф, а пара (V; {e₁, ..., e₃₀}), рассмотренная нами выше, — это 7-равномерный гиперграф с тридцатью ребрами. Гиперграф обладает свойством B, если его вершины можно так раскрасить в два цвета, чтобы все его ребра были неодноцветными. Эрдёш и Хайнал поставили следующий вопрос: каково минимальное число m = m(n), при котором все еще существует n-равномерный гиперграф с m ребрами, не обладающий свойством B? Вопрос осмысленный, так как выше мы фактически показали, что m(n)≥ 2^n – 1 (подумайте, почему!). За полвека, прошедшие с момента постановки вопроса, задача об отыскании величины m(n) сделалась одной из самых популярных в теории гиперграфов. Однако и по сей день никто не знает, как растет указанная величина. Известно лишь, что

где d(n) — некоторая функция, стремящаяся к нулю при n → ∞. Эрдёш высказывал гипотезу о том, что m(n) имеет порядок роста n∙2ⁿ, но сейчас даже нет идей, как подступиться к доказательству или опровержению этой гипотезы. Важно отметить, что все без исключения оценки основаны на вероятностном методе, и без этого метода результаты были бы гораздо слабее. Разумеется, техника доказательства передовых результатов намного сложнее той, которую мы изложили выше, и ее описание выходит далеко за рамки этой заметки. Заинтересованный читатель может обратиться, например, к книге [1].

Случайные графы

Одним из самых современных приложений вероятностного метода является наука о случайных графах. Правильное понимание того, что такое «случайность» на множестве графов, помогает решать задачи о разного рода «сетях» — в биологии, социологии, Интернете. Одна из простейших и наиболее глубоко изученных моделей случайного графа была предложена П. Эрдёшем и А. Реньи около полувека назад. Основана она на так называемой схеме испытаний Бернулли в теории вероятностей.

Представим себе, что у нас есть монета, сделанная из, вообще говоря, неоднородного материала. Иными словами, мы можем считать, что при случайном бросании на стол монета ложится кверху «решкой» с некоторой вероятностью p[0; 1]; соответственно, вероятность «орла» равна q = 1 – p (на ребро монета не становится никогда). Фиксируем натуральное число n. Сейчас мы с помощью нашей монеты построим случайный граф на n вершинах. Действительно, пусть V = {1; ...; n} — множество вершин будущего графа. На этом множестве можно провести ребер, коль скоро петли и кратные ребра в графе запрещены. Назовем эти (потенциальные) ребра e₁, ..., e_N. Возьмем нашу монету и бросим ее на стол. Если возникла «решка», проведем в графе ребро e₁; иначе — ребра e₁ в графе не будет. Снова бросим монету и по тому же принципу примем решение о проведении ребра e₂ в графе. Всего таких испытаний получается N, и в каждом из них мы проводим ребро с очередным номером или же не проводим его, смотря по тому, легла монета на стол «решкой» кверху или сверху оказался «орел». Обозначим через E случайное множество ребер, которое получится у нас по завершении всей цепочки испытаний. Через G = (V; E) мы обозначим весь итоговый случайный граф.

Давайте подумаем, какова вероятность того, что на выходе у нас получится конкретный граф G₀ = (V; E₀). Пусть Вероятность появления ребра в нашем графе есть p, такова же вероятность возникновения в нем и любого из оставшихся ребер. Более или менее очевидно, что вероятность одновременного появления ребер должна считаться как произведение отдельных вероятностей, то есть как p². Аналогичная картина наблюдается и для тройки ребер, и для любого их множества. В итоге вероятность возникновения всех s ребер есть p^s. Однако это еще не все. Ведь в нашем графе не только возникли ребра ...,
в нем также не возникли ребра из множества {e₁, ..., e_N}\E₀. Иначе говоря, при N бросаниях монеты мы s раз получили «решку» (и вероятность этого есть p^s) и N – s раз у нас выпал «орел». Очевидно, по прежним соображениям, вероятность последнего события есть q^N – s. Окончательно, P(G₀) = P(G = G₀) = p^sq^N – s.

Далее, вероятность того, что случайный граф G принадлежит данному множеству графов A, следует полагать равной сумме вероятностей всех графов из A:

Множество A называют событием или свойством случайного графа. Например, если A состоит из всех связных графов (то есть графов, в которых любые две вершины соединены хотя бы одним реберным маршрутом), то P(A) — это вероятность того, что случайный граф связен.

На самом деле, осмысленно вероятность появления ребра p делать зависящей от числа вершин n. Приведем пример соответствующего результата.

Теорема 1. Пусть Тогда вероятность того, что случайный граф связен, не меньше, чем

Прокомментируем теорему. Пусть у нас есть 10 000 компьютеров, расположенных в разных городах и попарно соединенных линиями связи. Предположим, связи между парами компьютеров по случайным причинам рвутся независимо друг от друга с вероятностью

Но это ведь ровно то же самое, как если бы связи, наоборот, возникали с вероятностью

Таким образом, мы имеем тот же случайный граф (граф связей), что и в теореме 1.
А теорема эта говорит, что с вероятностью большей 0,9999 случайный граф связен. Оказывается, в виду теоремы 1, наша сеть исключительно надежна: даже «разрешив» отдельным связям обрываться с вероятностью, крайне близкой к единице (скажем, с вероятностью 0,996), мы все-таки не утратим возможность передачи информации между любыми двумя компьютерами с вероятностью выше 0,9999. И если б компьютеров было не 10 000, а 100 000, 1 000 000 и т.д., то вероятности были бы еще более впечатляющими. Это довольно удивительно.

Теорема 1 имеет более точную формулировку.

Теорема 2. Пусть Тогда при c > 1 вероятность того, что случайный граф связен, стремится к единице, коль скоро . В то же время при c < 1 вероятность того, что случайный граф связен, стремится к нулю.

Теорема 2 означает, что имеет место своего рода скачок в проявлении свойства связности: при переходе своеобразной границы, выражаемой функцией мы от стремления вероятности данного свойства к единице резко перепрыгиваем к стремлению той же вероятности к нулю. Такой скачок зачастую называют фазовым переходом, поскольку он реально имеет некоторую физическую интерпретацию. Фазовые переходы для свойств случайных графов — явление стандартное.

Крайне любопытна совсем другая модель построения случайного графа, принадлежащая Б. Боллобашу и О. Риордану. Она дает весьма точную картину развития сети интернет. В самом деле, рассмотрим граф, вершинами которого служат сайты в интернете. Для каждой ссылки между данными сайтами S₁ и S₂ проведем ребро, соединяющее вершины S₁, S₂. Получится граф с кратными ребрами и даже кратными петлями (ссылки могут быть поставлены между страницами одного и того же сайта). Хочется описать модель динамического роста такого графа.

Прежде всего поймем, каким требованиям заведомо должна удовлетворять модель. Начнем с того, что при появлении нового сайта в сети ссылки с этого сайта с большей вероятностью пойдут на те ранее созданные сайты, которые и так уже достаточно активно цитировались: интуитивно ясно (и статистически обосновано), что новый сайт предпочтет сослаться на кого-то известного (типа Яндекса, Википедии и пр.), нежели на какого-нибудь Пупкина из Тмутаракани. Указанное явление называется предпочтительным присоединением.

Далее, есть еще один универсальный (эмпирический) закон, выражаемый словами «мир тесен». Очень многие слышали о том, что практически любые два человека знакомы между собой через пять-шесть «рукопожатий» (а то и менее). У меня есть друг, у друга есть друг и т.д., так что всегда найдется цепочка из не более пяти последовательных друзей, приводящих меня к произвольно взятому человеку. Это свойство любой «социальной сети». И интернет не является исключением. Только здесь рукопожатия следует заменить на «клики». Для любых двух сайтов существует цепочка из пяти-шести кликов (по ссылкам), переводящих с первого сайта на второй. Отметим, что число 5 не магическое. Разумеется, оно вырастет, если вырастет и население Земли (количество сайтов).

Отметим, что расстояние между вершинами (связного) графа — это количество ребер в самой короткой цепочке, соединяющей эти вершины. Диаметром связного графа G называется самое большое расстояние diam G между парами его вершин. Таким образом, свойство тесноты мира можно выразить как утверждение о том, что диаметр интернета («веб-графа») примерно равен пяти.

Опишем сперва вариант модели Боллобаша–Риордана, в котором число вершин и число ребер в случайном графе одно и то же, — скажем, t. В принципе, Интернет очень разреженный, и подобное предположение недалеко от истины. Однако позже мы построим и модель, в которой у каждого графа t вершин и kt ребер с произвольным натуральным k. Заметим, что в российском Интернете k ≈ 10.

Итак, положим  — граф, у которого одна вершина и одна петля. Пусть граф уже построен. У него, как и обещано, (t – 1 ребро). Определим величины d₁, ..., d_t – 1 как степени вершин графа , то есть, например, d₁ — это количество ребер из одним из концов которых служит вершина 1. Добавим вершину t, либо присоединяя ее ребром к одной из уже имеющихся вершин, либо образуя петлю (t; t). А именно, присоединим новую вершину к вершине i{1; ...; t – 1} с вероятностью и образуем петлю с вероятностью . Действительно, нам надо, чтобы их сумма равнялась единице, но так оно и есть, ведь

Последовательность случайных графов реализующая идею предпочтительного присоединения, построена.

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

У него kt вершин и kt ребер. Сделаем из него случайный граф с t вершинами и kt ребрами. Для этого просто представим множество {1; ...; kt} в виде объединения последовательных блоков размера k:

{1; ...; kt} = {1; ..., k} ... {k(t – 1) + 1; ...; kt}.

Назовем каждый блок вершиной нового графа и соединим вершины a и b в столькими ребрами, сколько ребер вели из блока a в блок b.
Иными словами, возникают кратные ребра в даже кратные петли, но это вполне отвечает интуиции.

Не правда ли, все просто? Так вот, имеет место

Теорема 3. Для любого k 2 и для любого

Например, при t = 10⁷ (приблизительно таков реальный размер российского веб-графа) и ε = 0,1 с большой вероятностью имеем

Полное соответствие с гипотезой о тесноте мира!

Литература

1.  Алон Н., Спенсер Дж. Вероятностный метод. — М.: Бином: Лаборатория знаний, 2007
2. Райгородский А.М. Вероятность и алгебра в комбинаторике. — М.: МЦНМО, 2008.

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