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