Например, если a является свойством связности,
то нам нужно рассмотреть все связные графы на n вершинах,
для каждого из них вычислить вероятность и найти сумму.
Тогда мы сможем обсуждать с вами вполне содержательно вопрос о том,
с какой вероятностью случайный граф является связным.
Ну, глядя на эту задачу, вот для свойства связности конкретно,
я думаю, что слушатели немножко закисают, впадают в определенное уныние,
потому что как-то, ну должно казаться, что всё совсем трудно и плохо.
Но действительно, мало ли какие на свете бывают связные графы.
Даже на данном количестве n вершин.
[ФЫРКАЕТ] Ну там, пусть, я не знаю, n = 4.
Так, для примера, чтобы понимать, насколько сложной является задача,
которую мы здесь как бы уже рассматриваем.
Задача отыскания или аппроксимации вероятности того или иного замечательного
события.
Но вот если n = 4, то понятно, что на четырех вершинах 1,
2, 3, 4 есть, в общем-то, самые разнообразные связные графы.
Например, цикл, который я сейчас нарисовал, это, конечно же, связный граф.
Но есть и вот такой вот связный граф: 1, 2, 3, 4 — вот так.
Это уже не цикл.
Это какой-то более хитрый связный граф, и, заметьте,
у этого графа четыре ребра присутствуют среди ребер полного графа
на четырех вершинах, а два потенциальных ребра отсутствуют.
Это значит, что с точки зрения нашего определения вероятность этого конкретного
графа есть p в четвертой степени, умножить на q в квадрате.
В то время как вероятность вот этого, другого, связного графа,
это уже p в пятой умножить на q в первой степени, то есть, просто на q.
То есть у них даже разные вероятности.
И вот все эти вероятности мы складываем между собой,
и получается в итоге интересующая нас, ну скажем, вероятность связности.
И конечно, уныние должно возникнуть, но уныние, как обычно у нас водится,
компенсируется катарсисом, то есть мы просто продемонстрируем силу математики,
которая позволяет вот в этом хаосе разных значений, который, казалось бы,
совершенно непонятно как упорядочить и как сложить между собой, найти некоторые
удобные закономерности, применить средства из теории вероятности для того,
чтобы сказать какие-то вполне содержательные глубокие утверждения, в том
числе (внимание!) полезные и для практики, хотя и просто красивые сами по себе,
относительно различных вероятностей свойств.
Свойство связности, с него мы начнем,
и масса других очень красивых свойств, о которых мы поговорим в дальнейших лекциях.
Вот, ну во всяком случае определение модели Эрдеша—Реньи,
вот в этом первом ее варианте, в первой ее модификации, мне кажется, я дал.
То есть, итак, мы знаем, чему равна вероятность каждого элементарного события,
коль скоро под элементарными событиями мы понимаем наши графы, и мы знаем,
как посчитать вероятность произвольного события.
Мы понимаем, что событие — это просто набор каких-то элементарных исходов, то
есть каких-то графов, и, соответственно, вероятность этого события полагаем равной,
как водится в теории вероятностей, сумме вероятностей элементарных исходов,
которые ему благоприятствуют, то есть которые ему, как множеству, принадлежат.
Таким образом мы очень много всего можем сделать.