помогите с задачами по графам и геометрии.

[patriarch]

Помогите пожалуйста решить
1) Графы и системы дорог.
Для заданного натурального числа n > 4 построить граф (без петель и без кратных
рёбер) с n вершинами, в котором степень каждой вершины равна 4 (Степень вершины
равна числу рёбер, инцидентных ей).
2) Геометрия.
Задано n точек на плоскости. Построить дерево с вершинами в данных точках так,
чтобы была минимальной суммарная длина его рёбер.

[AndreyXYZ]

patriarch в сообщении #193850 писал(а):

1) Графы и системы дорог.
Для заданного натурального числа n > 4 построить граф (без петель и без кратных
рёбер) с n вершинами, в котором степень каждой вершины равна 4 (Степень вершины
равна числу рёбер, инцидентных ей).

Представьте $n$ как $n=5r+q$, где $r \in \mathbb{N}_0,\, q=0,6,7,8,9$.
Тогда искомым графом будет совокупность $r$ полных графов с $5$ вершинами и одного графа с $q$ вершинами (если $q \ne 0$) (получим граф с $(r+1)$ компонентой связности). Т.о., необходимо построить графы с $6,7,8,9$ вершинами, у которых степени вершн равны $4$.

[Лиля]

patriarch в сообщении #193850 писал(а):

2) Геометрия.
Задано n точек на плоскости. Построить дерево с вершинами в данных точках так,
чтобы была минимальной суммарная длина его рёбер.

мож испоьзовать этот алгоритм : http://alglib.sources.ru/graphs/minspanningtree.php