@sr36

Как сгенерировать направленный граф с N количеством путей?

Добрый день.

Необходимо написать алгоритм, который будет генерировать направленный граф, с точным количеством возможных вариантов перемещения между точками A и B.

То есть у нас есть 2 точки, условно назовем точку A - точкой отправки, а точку B - дочкой доставки.
В самом простейшем случае у нас есть 2 узла A и B и одно ребро между ними.
Если на вход алгоритму передаем например 4, он должен вернуть случайный направленный граф, в котором только 4 варианта перемещения между A и B.

Буду благодарен за любые подсказки
  • Вопрос задан
  • 47 просмотров
Решения вопроса 1
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Находим разбиение числа путей на простые множители. Строим между точками A и B дополнительные слои, в каждом из которых количество точек соответствует следующему множителю. Соединяем точку A со всеми точками первого слоя, каждую из точек первого слоя со всеми точками второго слоя и т.д., все точки последнего слоя с точкой B.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
BojackHorseman
@BojackHorseman
...в творческом отпуске...
очевидно, чтобы построить альтернативный путь, нужно добавить вершину C и провести ребра AC и CB.
для следующего пути добавляем вершину D, получаем альтернативные пути ADB, ADCB.
etc...
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы