Поиск алгоритма решения задачи построения графа с заданными условиями

only, попробую.

Пусть k чётно.
соединяем каждую i-ю вершину с k/2 предыдущими (разумеется, для вершины 1 считая предыдущей N), и k/2 следующими.

Теперь допустим k нечётно. Проделаем вышеописанный алгоритм для чётного k-1, теперь надо для каждой вершины по 1 ребру добавить. Пусть n чётно. Тогда соединим каждую i-ю вершину с (i+(k+1)/2)-й, если она (эта i-я вершина) ещё не была соединена на этом этапе (т.е. если не соединена с (i-(k+1)/2)-й). Пусть теперь n нечётно. Тогда проделаем вышеописанную операцию для n-1, а оставшуюся вершину соединим с любой, которой только получится.