Генерация случайного сильно связанного орграфа

@semashko · Регистрация: 20.12.2012

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

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

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

Буду благодарен за подробное объяснение.

@Mysterious Light · 05.07.2013, 21:29

Можете написать генератор произвольного орграфа с заданным числом вершин и ребер?
Имея этот генератор, пишите другой, в котором последовательно генерируете первым генератором орграфы, проверяете каждый (поочерёдно) на сильную связанность и первый подходящий возвращаете.

Code
1
2
3
4
5
6
7
8
ОРГРАФ(N, M) := ...
СИЛЬНО_СВЯЗАН(орграф) := ...
 
СВЯЗНЫЙ_ОРГРАФ(N,M) :=
    DO
        орграф <- ОРГРАФ(N,M)
    UNTIL СИЛЬНО_СВЯЗАН(орграф)
    RETURN орграф

Равномерность гарантируется (если первый генератор равномерен).

Такой вариант подходит?
P.S. для малых M,N работать будет. Для больших будет сильно тормозить. Зато пишется быстро.

@semashko · 05.07.2013, 21:45 **[ТС]**

Максимальное число вершин 1000, максимальное число ребер 100000. Сейчас запрогаю, но чую я, чтодолго будет.

@Mysterious Light · 06.07.2013, 18:40

Беру свои слова назад: чем меньше ребер при одном числе вершин, тем больше шанс попасть на несвязный граф, тем больше нужно будет графов генерировать.

По-быстрому набрасал код в Wolfram Mathematica, оценив число несвязных графов

Matlab M
1
2
3
4
5
6
7
8
9
n = 1000;
m = 10000;
rg := RandomGraph[{n, m}, DirectedEdges -> True];
(* Случайный граф *)
R := Block[{r = rg}, If[Length[StrongComponents[r]] == 1, r, R]];
(* Число генерируемых графов на один связный *)
H := Block[{r = rg}, If[Length[StrongComponents[r]] == 1, 1, 1 + H]];
(* среднее число промахов *)
Block[{$RecursionLimit = 1000}, Mean[Table[H, {500}]] // N]

Результат: 1.108 графов нужно сгенерировать (в среднем), чтоб получить один связный граф.

P.S. у Вас есть какие-то результаты?

Новые блоги и статьи Все статьи Все блоги /
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .

@semashko 0 / 0 / 0 Регистрация: 20.12.2012 Сообщений: 4

	Генерация случайного сильно связанного орграфа 05.07.2013, 17:44. Показов 3024. Ответов 3 Метки нет (Все метки) Здравствуйте. Необходимо, случайным образом, генерировать сильно связный орграф с заданным количеством вершин и ребер. Обязательной является вероятность выпадения любого сильно связного орграфа с заданным числом вершин и ребер. Желательно равномерное распределение. Нужно для генератора тестов к задачам спортивного программирования. В гугле найти не удалось( Буду благодарен за подробное объяснение. 0

@semashko 0 / 0 / 0 Регистрация: 20.12.2012 Сообщений: 4
	05.07.2013, 21:45 [ТС]
	Максимальное число вершин 1000, максимальное число ребер 100000. Сейчас запрогаю, но чую я, чтодолго будет. 0