Найти предел при n стремящемся к бесконечности математического ожидания числа унициклических компонент на не более 4 вершинах в случайном графе G(n,1/(2n)).

Где n - число ребер, 1/(2n) - вероятность ребра

задан 10 Мар 19:40

@worker: предлагаю небольшой шуточный тест.

Термин "унициклическая компонента" должен знать

1) каждый уважающий себя человек

2) каждый профессиональный математик

3) каждый специалист по теории графов

4) каждый слушатель читаемого Вам спецкурса? :)

(10 Мар 20:29) falcao

@falcao: Прошу прощения! Унициклический граф - это граф в котором число вершин равно числу ребер.

(10 Мар 20:37) worker
10|600 символов нужно символов осталось
1

Рассмотрим одну фиксированную компоненту с одним циклом на 3 вершинах. При этом три вершины попарно соединены, и ни одна из них не соединена ни с одной из $%n-3$% оставшихся. Вероятность такого события $%(\frac1{2n})^3(1-\frac1{2n})^{3(n-3)},$% что эквивалентно $%\frac{e^{-3/2}}{8n^3}$%. Для каждой тройки вершин рассматриваем случайную величину со значениями 1 или 0 в зависимости от того, даёт ли она компоненту с одним циклом. Матожидание равно вероятности того, что такая компонента есть. Оно было найдено выше. Далее мы складываем $%C_n^3$% таких случайных величин. Матожидание умножается на эту величину, эквивалентную $%\frac{n^3}6$%. Итого предел равен $%\frac1{48e^{3/2}}$%.

Далее аналогично считаем число компонент на 4 вершинах. Фиксируем 4 такие вершины, и там получается или один цикл длиной 4, или цикл длиной 3 с "ножкой" (то есть одна из трёх его вершин соединена ребром с четвёртой). Как и выше, здесь ни одна из 4 вершин не соединена ни с какой из $%n-4$% оставшихся.

Циклов длиной 4 (циклических подграфов) имеется ровно 3; если мы выбираем цикл длиной 3, а потом к нему "ножку", то это 12 вариантов -- итого 15. В каждом из случаев у нас присутствует по 4 ребра в подграфе, по 2 отсутствует, и ещё есть $%4(n-4)$% отсутствующих "внешних" соединений. Поэтому для фиксированной четвёрки вершин получается $%\frac{15}{(2n)^4}(1-\frac1{2n})^{4n-14}\sim\frac{15e^{-2}}{16n^4}$%. После умножения на $%C_n^4\sim\frac{n^4}{24}$% мы в пределе получим $%\frac5{128e^2}$%. Итого в сумме будет примерно $%0,01$%.

ссылка

отвечен 11 Мар 17:00

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

@falcao: чем не верен такой способ решения? alt text

@falcao: правильно ребер n*(n-1)/2 - тогда получаем предел:

alt text

Он равен нулю, что не верно. В чем ошибка?

ссылка

отвечен 11 Мар 9:35

изменен 11 Мар 15:25

@worker: а что это за выражения в степени? Это же огромные числа! Подозреваю, что там имелось в виду 1-1/(2n). Но, даже если так, то нужны какие-то словесные пояснения смысла рассматриваемых оценок.

(11 Мар 13:03) falcao

@falcao: Из n вершин выбираем 3 ребра - число способов = число сочетаний из n по 3, с учетом способов выбора получаем множитель (1/2)*(3-1)! Далее поскольку 3 ребра существует, то домножаем на их вероятность (1/(2n))^3, далее т.к. других ребер нет, то домножаем на их отсутствие, оно равно = (1-(1/(2n)))^(n-3). Для компонент размерности 4 - аналогично.

(11 Мар 13:44) worker

@worker: самую первую фразу я уже не понимаю. Для меня она звучит примерно как "из n мальчиков выбираем трёх девочек" :)

(11 Мар 13:52) falcao

@falcao: Из n ребер выбираем 3 ребра

(11 Мар 14:43) worker

@worker: видимо, это то, что называется "методом последовательного приближения к истине" :)

Теперь следующий вопрос: у нас n вершин, а возможных рёбер n(n-1)/2. Если мы выбираем 3 ребра из n, то из каких именно рёбер?

(11 Мар 15:08) falcao

@worker: сейчас у Вас получается бессмыслица. Если Вы выбираете три случайных ребра, то они между собой никак не связаны, и никакой компоненты в общем случае не задают.

(11 Мар 16:14) falcao
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×2,229
×413
×37

задан
10 Мар 19:40

показан
207 раз

обновлен
11 Мар 17:00

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

по почте:

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

по RSS:

Ответы

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

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