16.1. Покриття iнтервалами (впорядкування лінійного масиву)

1. Впорядкувати інтервали покриття за неспаданням правого кінця, а для сталого правого кінця — за зростанням лівого.

2. За перший інтервал покриття вибирати інтервал, що містить лівий кінець відрізка й має найбільший номер після проведеного впорядкування.

3. Кожний наступний інтервал покриття вибирати таким, що містить правий кінець попереднього інтервалу і має найбільший номер після проведеного впорядкування. Інакше кажучи, використати жадібний алгоритм.

16.2. Многогранник-2 (оптимізований перебір каркасних дерев)

1. Будь-яку симетрію многогранника, в якому всі грані правильні многокутники, можна задати перестановкою (взаємно однозначним відображенням) на множині номерів граней, яка зберігає суміжність граней. Всі симетрії такого многогранника можна отримати за допомогою перебору всіх перестановок на множині номерів граней. Для ефективного алгоритму такий перебір потрібно оптимізувати перери­ванням продов­ження перебору за умови порушення суміжності граней.

2. Графом суміжності граней многогранника (розгортки многогранника) назвемо неорієнтований граф, в якому:

   • вершини — номери граней;
   • ребра — двоелементні множини номерів граней зі спільним ребром.

3. Граф суміжності граней довільного многогранника зв'язний і містить цикли. Наприклад, такі, що задають обхід навколо вершини многогранника чи по периметру грані многогранника.

4. Граф суміжності граней довільної розгортки довільного многогранника зв'язний і не містить цикли, тобто є деревом, вершини якого є вершинами графа суміжності граней многогранника. Це дерево можна отримати з графа суміжності граней многогранника двома способами:

   • вилученням «зайвих» ребер зі збереженням зв'язності, але до повного руйнування всіх циклів;

   • долученням до порожньої множини ребер разом з вершинами, що їх сполучають. Перше ребро вибирають з тих ребер, що мають вершину 1. При долученні до дерева кожного наступного ребра:

     • одна з його (ребра) вершин має бути новою (порушення цієї умови еквівалентне наявності циклу);

     • немає можливості долучити дане ребро раніше хоча б одного з уже долучених ребер з більшим номером (це забезпечує вказаний в умові порядок перебору розгорток многогранника).

   Другий алгоритм ефективніший. Саме його реалізовано в авторському розв'язанні.