В случайном графе G(n,2) случайным образом (независимо от проведения ребер в случайном графе) выбирают [n/2] вершин и красят их в красный цвет, а остальные - в синий. С какой асимптотической вероятностью эта раскраска является правильной (любые две вершины одного цвета не соединены ребром)?

задан 4 Май 19:18

@worker: непонятно обозначение. Раньше было G(n,p) для случайного графа на n вершинах, где ребро проводится с вероятностью p. Может, там второй параметр равен 1/2?

(4 Май 19:38) falcao
1

@falcao, G(n,2) - это равномерная модель графа. Т.е., это граф на n вершинах с двумя ребрами. Всего способов построить такой граф равно C(C(n,2),2), где C(a,b) - это число сочетаний из a по b. Т.е. вероятность выпадения такого графа равна 1/C(C(n,2),2).

(4 Май 19:56) worker
1

@worker: тут без особых подсчётов ясно, что вероятность стремится к 1/4. Есть два ребра, про которые можно считать, что они дизъюнктны (вероятность того, что они имеют общую вершину, стремится к нулю). Примерно половина вершин раскрашивается в тот и другой цвет, поэтому для данного ребра вероятность разноцветных концов стремится к 1/2. Для двух рёбер будет в пределе 1/4.

(4 Май 20:09) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×1,122
×480

задан
4 Май 19:18

показан
64 раза

обновлен
4 Май 20:09

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

по почте:

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

по RSS:

Ответы

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

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