Есть подграф H графа G(n,n,1/2). И из подграфа H (выбор осуществляется равновероятно) удаляется 90% всех его ребер.

С какой предельной вероятностью полученный граф будет связным?

Здесь G(n,n,1/2) - полный двудольный граф с n вершинами первой доли и n вершинами второй доли и 1/2 - вероятность проведения ребра.

задан 29 Июн '19 17:59

10|600 символов нужно символов осталось
0

После удаления 90% вершин вероятность ребра в H будет равна 1/2 * 1/10 = 1/20. Теперь проще всего посмотреть на вероятность того, что хотя бы одна вершина в верхней доле H будет изолированной:

P(хотя бы одна вершина изолирована)= ((1 - 1/20)^n)^n = (19/20)^(n^2)

Эта вероятность асимптотически стремится к 0. Тогда P(граф H связен) асимптотически стремится к 1.

ссылка

отвечен 29 Июн '19 21:22

1

@navacho: я поначалу рассуждал так же, но этих соображений не достаточно. Изолированных вершин может не быть, но при этом граф может оказаться не связным. Хотя я думаю, что можно чуть усилить предыдущее рассуждение, рассматривая связные компоненты и оценивая вероятности.

(29 Июн '19 22:54) falcao

@falcao Да, действительно, здесь больше работы чем я думал. Для завершения доказательства, я думаю, можно дополнительно использовать тот факт, что при условии отсутствия изолированных вершин нам нужна для связности только одна вершина в верхней доле, соединенная со всеми вершинами из нижней. Асимптотически такая вершина существует, осталось только аккуратно все это оформить.

(29 Июн '19 23:41) navacho

@navacho: наверное, там какой-то другой аргумент надо искать. Вероятность того, что одна вершина соединена со всеми из другой доли, совсем маленькая.

(30 Июн '19 1:48) falcao
1

@falcao Попробуем с помощью Маркова. Если для каждой пары в нижней доле найдется хотя бы одна вершина в верхней доле, соединенная с обеими из этой пары, то тогда граф связен. Рассмотрим сл.величину X - количество пар из нижней доли у которых нет таких вершин в верхней доле. Тогда по Маркову:

P(такие пары есть) = P(X>=1) <= Е(X)

Дальше введем индикаторы X(i) для i-й пары:

X(i) = 1, если i-я пара не имеет общей вершины в верхней доле, иначе 0.

E(X(i)) = P(X(i) = 1) = (1-(19/20)^2)^n

E(X) = n * (n-1) * 39/400^n -> 0

Т.е. таких пар нет а.п.н., тогда граф а.п.н. связен.

(30 Июн '19 6:08) navacho
1

И конечно, я был неправ, используя Маркова можно показать, что количество вершин соединенных со всеми вершинами другой доли а.п.н. стремится к 0.

(30 Июн '19 6:24) navacho
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×624

задан
29 Июн '19 17:59

показан
296 раз

обновлен
30 Июн '19 6:26

Отслеживать вопрос

по почте:

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

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru