На острове Скелета расположены 8 пиратских сокровищниц. Меж некоторыми из них прорыты тропы через джунгли. Карта сокровищ — это замкнутый путь по тропам, который начинается в одной сокровищнице, проходит через разные сокровищницы без повторений и

Дано

• Количество вершин (сокровищниц) $n = 8$.
• В графе должны существовать простые циклы (пути, проходящие через вершины без повторений и возвращающиеся в начало) длины $k$, где $k \in \{3, 4, 5, 6, 7, 8\}$.
• Нужно найти минимальное количество ребер (троп) $m$, при котором это условие выполняется.

Решение

1. Анализ условий: Чтобы в графе существовал цикл длины $k$, граф должен содержать хотя бы $k$ вершин и $k$ ребер. Однако нам нужно, чтобы циклы всех длин от $3$ до $8$ присутствовали одновременно.

2. Построение графа: Рассмотрим граф, состоящий из цикла длины $n=8$...