Случайный граф

[time4party]

Задача -- сгенерировать случайный связный граф степени $n$ ($n$ вершин).

Вопрос: если сначала сгенерировать случайное дерево степени $n$, а потом с вероятностью $0.5$ соединить несоединенные вершины, будет ли вероятность получить любой связный граф степени $n$ одинаковой?

[VAL]

time4party в сообщении #929755 писал(а):

Задача -- сгенерировать случайный связный граф степени $n$ ($n$ вершин).

Вопрос: если сначала сгенерировать случайное дерево степени $n$, а потом с вероятностью $0.5$ соединить несоединенные вершины, будет ли вероятность получить любой связный граф степени $n$ одинаковой?

Во-первых, случайное дерево сгенерировать можно по-разному.
А во-вторых, независимо от "во-первых", вероятности возникновения разных графов, все равно будут разными. Например, при $n=4$ вероятность появления цикла длины 3 с "хвостиком" будет заведомо выше, чем вероятность пояления цикла длины 4.

[DMZ]

Я бы начал с генерации матрицы связности.

И нужно решить, считать ли изоморфные графы одинаковыми.

[ИСН]

Сделать "обычный" случайный граф (что бы это ни значило), если вышел несвязный - выкинуть и переделать. Дешевле выйдет.

[time4party]

DMZ в сообщении #930752 писал(а):

Я бы начал с генерации матрицы связности.
И нужно решить, считать ли изоморфные графы одинаковыми.

Граф помеченный -- то есть вершины отмечены цифрами, таким образом изоморфные считаются разными.

ИСН в сообщении #930792 писал(а):

Сделать "обычный" случайный граф (что бы это ни значило), если вышел несвязный - выкинуть и переделать. Дешевле выйдет.

Для больших $n$ наоборот выйдет.

VAL в сообщении #930747 писал(а):

А во-вторых, независимо от "во-первых", вероятности возникновения разных графов, все равно будут разными. Например, при $n=4$ вероятность появления цикла длины 3 с "хвостиком" будет заведомо выше, чем вероятность пояления цикла длины 4.

Это ведь с точностью до изоморфизма они будут иметь разные вероятности появления?

[VAL]

time4party в сообщении #931416 писал(а):

DMZ в сообщении #930752 писал(а):

Я бы начал с генерации матрицы связности.
И нужно решить, считать ли изоморфные графы одинаковыми.

Граф помеченный -- то есть вершины отмечены цифрами, таким образом изоморфные считаются разными.

А чего же Вы сразу об этом не сообщаете?

Цитата:

ИСН в сообщении #930792 писал(а):

Сделать "обычный" случайный граф (что бы это ни значило), если вышел несвязный - выкинуть и переделать. Дешевле выйдет.

Для больших $n$ наоборот выйдет.

Почему?
Для больших $n$ подавляющее большинство графов связны.

[time4party]

VAL в сообщении #931426 писал(а):

А чего же Вы сразу об этом не сообщаете?

Ну так, по умолчанию изоморфные графы не равны друг другу.

VAL в сообщении #931426 писал(а):

Почему?
Для больших $n$ подавляющее большинство графов связны.

Другими словами подавляющее меньшинство графов не связны. Да. Я не подумал об этом.

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

[VAL]

time4party в сообщении #931436 писал(а):

VAL в сообщении #931426 писал(а):

А чего же Вы сразу об этом не сообщаете?

Ну так, по умолчанию изоморфные графы не равны друг другу.

Это смотря кто умалчивает
В теме, где Вас интересует вероятность сгенерировать тот или иной граф, лучше сразу расставить эти акценты. Верятности для помеченных и непомеченных графов могут быть разными.

Цитата:

VAL в сообщении #931426 писал(а):

Почему?
Для больших $n$ подавляющее большинство графов связны.

Другими словами подавляющее меньшинство графов не связны. Да. Я не подумал об этом.

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

. Разумеется. Как и многие другие. Но вот равной с вероятностью возникновения разных графов сложнее.