Численный эксперимент по связности случайных графов

@Elena1993 · Регистрация: 12.06.2013

Студворк — интернет-сервис помощи студентам

Всем привет. может кто нибудь пояснить . Я вообще не поняла в чем тут дело

@Mysterious Light · 12.06.2013, 06:48

Очень размытое описание задачи.
Случайный граф — это, грубо говоря, ансамбль обычных графов с вероятностной мерой.
Понятно, что конкретный граф либо связан, либо нет. А случайный граф может быть связанным с вероятностью p, а может и не быть с вероятность 1-p. Как я понимаю, вопрос именно в определении p. Аналитически,
$https://www.cyberforum.ru/cgi-bin/latex.cgi?p=\sum_{G}P(G)$
сумма берется по всем связанным графам. P(G) — вероятность того, что случайнойный граф окажется равным G. Определяется статистикой.

Кстати, в какой статистике работаем? Самая простая — Эрдёш-Реньи, когда
$https://www.cyberforum.ru/cgi-bin/latex.cgi?P(G) =\, \textrm{Binom}(\frac{N(N-1)}2, \;M(G))\, q^{\tiny M(G)} (1-q)^{\tiny\frac{N(N-1)}2-M(G)}$
где M(G) — число рёбер в графе G, N — число вершин во всех возможных реализациях G (от G не зависит), Binom(n,k) — биномиальный коэффициент. Подробнее в википедии.

Под численным экспериментом, как я понимаю, подразумевается симмуляция (типа Монте-Карло), когда мы генерируем G в соответствии со статистикой, каждый из полученных графов G проверяем на связность, считаем число связных случаев A к числу всех сгенерированных графов B и возвращаем A/B ≈ p.

@Elena1993 · 12.06.2013, 10:31 **[ТС]**

Мда, кажись я не ту профессию выбрала

@Elena1993 · 14.06.2013, 10:10 **[ТС]**

...

Добавлено через 1 минуту
Mysterious Light, мне надо написать программу на эту тему но не знаю как. Можете помочь? Если вы не против?

@Mysterious Light · 15.06.2013, 00:28

Понимаете, либо Вы не ставите задачу корректно и полно, либо я чего-то не понял.

Если у Вас таки статистика Эрдеша-Реньи, то в Wolfram Mathematica решение выглядит так:

Matlab M
1
2
3
4
5
6
In[1]:= With[{n = 100, p = 0.1, size = 1000},
  sample = Table[RandomGraph[BernoulliGraphDistribution[n, p]], {size}];
  Length[Select[sample, ConnectedGraphQ]]/size
 ]
 
Out[1]= 249/250

Здесь рассматриваются графы с n=100 вершинами, каждое ребро может с вероятностью p=0.1 появиться и с (1-p) отсутствовать, генерируются size=1000 графов (список sample), среди них находятся все связные и считается их количество, полученное число делится на размер выборки size.

@Elena1993 · 15.06.2013, 07:02 **[ТС]**

Mysterious Light, Ну мне сказали просто написать программу и все. Скорей всего ее надо написать в паскале или дельфи используя массивы

@Mysterious Light · 15.06.2013, 08:00

Вы же понимаете, что детали Вашего задания никто, кроме Вас знать не может.
Обратитесь в раздел Delphi, Pascal или в тот, где помогают студентам, или в фриланс, в зависимости от того, насколько Вам срочно это надо.
В выбранном разделе создайте тему, в которой изложите настолько подробно, насколько можете, содержание вашего задания.

@Elena1993 · 15.06.2013, 13:02 **[ТС]**

Mysterious Light, Спасибо так и сделаю

@Elena1993 · 19.06.2013, 05:22 **[ТС]**

Mysterious Light, Снова привет. Нужна помощь. Можете создать условие задачи по этой теме?

@cmath · 20.06.2013, 17:40

Сообщение от Elena1993

Можете создать условие задачи по этой теме?

Сообщение от Mysterious Light

детали Вашего задания никто, кроме Вас знать не может.

Исходя из этого, условие к вашей задаче можете только вы задать.

Новые блоги и статьи Все статьи Все блоги /
Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .	Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .	Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .
Автозаполнение реквизитов при создании документа Maks 26.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .	Команды формы и диалоговое окно Maks 26.03.2026 1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .	Кому нужен AOT? DevAlt 26.03.2026 Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .	Отправка уведомления на почту при создании или изменении элементов справочника Maks 24.03.2026 Программная отправка письма электронной почты на примере типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной записи электронной. . .

@Elena1993 0 / 0 / 0 Регистрация: 12.06.2013 Сообщений: 10

	Численный эксперимент по связности случайных графов 12.06.2013, 06:27. Показов 1613. Ответов 9 Метки нет (Все метки) Всем привет. может кто нибудь пояснить . Я вообще не поняла в чем тут дело 0

@Mysterious Light $Эксперт по математике/физике$ 4313 / 2105 / 431 Регистрация: 19.07.2009 Сообщений: 3,205 Записей в блоге: 24
	12.06.2013, 06:48
	Очень размытое описание задачи. Случайный граф — это, грубо говоря, ансамбль обычных графов с вероятностной мерой. Понятно, что конкретный граф либо связан, либо нет. А случайный граф может быть связанным с вероятностью p, а может и не быть с вероятность 1-p. Как я понимаю, вопрос именно в определении p. Аналитически, $https://www.cyberforum.ru/cgi-bin/latex.cgi?p=\sum_{G}P(G)$ сумма берется по всем связанным графам. P(G) — вероятность того, что случайнойный граф окажется равным G. Определяется статистикой. Кстати, в какой статистике работаем? Самая простая — Эрдёш-Реньи, когда $https://www.cyberforum.ru/cgi-bin/latex.cgi?P(G) =\, \textrm{Binom}(\frac{N(N-1)}2, \;M(G))\, q^{\tiny M(G)} (1-q)^{\tiny\frac{N(N-1)}2-M(G)}$ где M(G) — число рёбер в графе G, N — число вершин во всех возможных реализациях G (от G не зависит), Binom(n,k) — биномиальный коэффициент. Подробнее в википедии. Под численным экспериментом, как я понимаю, подразумевается симмуляция (типа Монте-Карло), когда мы генерируем G в соответствии со статистикой, каждый из полученных графов G проверяем на связность, считаем число связных случаев A к числу всех сгенерированных графов B и возвращаем A/B ≈ p. 2

@Elena1993 0 / 0 / 0 Регистрация: 12.06.2013 Сообщений: 10
	12.06.2013, 10:31 [ТС]
	Мда, кажись я не ту профессию выбрала 0

@Elena1993 0 / 0 / 0 Регистрация: 12.06.2013 Сообщений: 10
	14.06.2013, 10:10 [ТС]
	... Добавлено через 1 минуту Mysterious Light, мне надо написать программу на эту тему но не знаю как. Можете помочь? Если вы не против? 0

@Elena1993 0 / 0 / 0 Регистрация: 12.06.2013 Сообщений: 10
	15.06.2013, 07:02 [ТС]
	Mysterious Light, Ну мне сказали просто написать программу и все. Скорей всего ее надо написать в паскале или дельфи используя массивы 0

@Mysterious Light $Эксперт по математике/физике$ 4313 / 2105 / 431 Регистрация: 19.07.2009 Сообщений: 3,205 Записей в блоге: 24
	15.06.2013, 08:00
	Вы же понимаете, что детали Вашего задания никто, кроме Вас знать не может. Обратитесь в раздел Delphi, Pascal или в тот, где помогают студентам, или в фриланс, в зависимости от того, насколько Вам срочно это надо. В выбранном разделе создайте тему, в которой изложите настолько подробно, насколько можете, содержание вашего задания. 0

@Elena1993 0 / 0 / 0 Регистрация: 12.06.2013 Сообщений: 10
	15.06.2013, 13:02 [ТС]
	Mysterious Light, Спасибо так и сделаю 0

@Elena1993 0 / 0 / 0 Регистрация: 12.06.2013 Сообщений: 10
	19.06.2013, 05:22 [ТС]
	Mysterious Light, Снова привет. Нужна помощь. Можете создать условие задачи по этой теме? 0