Mikhail Nikitkov
Гуру
(4589)
1 месяц назад
Задача здесь уже была:
В случайном графе с четырьмя вершинами вероятность проведения ребра равна=1/3. Найдём вероятность того, что граф связный.
1.Найдите вероятность того, что граф связный и в нём не больше двух рёбер.
2.Найдите вероятность того, что граф связный и в нём четыре рёбра.
3.Найдите вероятность того, что граф связный и в нём пять рёбер.
4.Найдите вероятность того, что граф связный.
Будем считать, что в графе нет кратных рёбер и петель - граф простой. Изоморфизм графов также не будем учитывать. Тогда с четырьмя вершинами можно построить 64 различных графов.
Причём, 38 из них будут связными и 26 будут несвязными.
Если рёбер не больше двух, то граф связным быть не может. И вероятность этого равна нулю.
Всё графы с четырьмя рёбрами будут связными и всего их будет 15. Вероятность этого будет равна 15*p^4*q^2. Здесь p = 1/3 (вероятность того, что ребро проведено), а q = 1 - p = 2/3 (вероятность того, что ребро не проведено). Степень при р будет 4 - всего проведено 4 ребра, степень при q будет 2 - всего не проведено 2 ребра. Подставляя значения, получим для вероятности 20/(3^5).
Все графы с пятью рёбрами будут связными, всего их будет 6. Тогда вероятность равна 6*p^5*q. Вычисляя эту вероятность , получим 4/(3^5).
Связных графов всего 38, причём 16 будут иметь 3 рёбра, 15 будут иметь 4 рёбра, 6 будут иметь 5 рёбер и 1 будет с 6 рёбрами. Тогда вероятность будет выражаться суммой: 16*p^3 *q^3 + 15*p^4*q^2 + 6*p^5*q + 1*p^6. И вычисляя, получим вероятность 67/(3^5).
Найти вероятность того, что граф связный.