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

Question

[sr36]

Добрый день.

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

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

Буду благодарен за любые подсказки

Answer 1

[Rsa97]

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