Задание 5. Параметризованный алгоритм для вершинного покрытия

Реализовать для задачи о вершинном покрытии один из параметризованных алгоритмов.

В состав предоставляемых файлов должен входить файл Описание.txt, в котором указано, какой из методов реализован.

Входные данные:
1) граф - формат аналогичен заданию 2
2) параметр k (ограничение на размер покрытия).

Тестовый файл: VC2.txt

Эталонные результаты:

  • k=7: {1,2,6,8,11,12,14}
  • k=5: нет решения

Программа получает на вход 5 параметров:

1.[Вход] Файл входными данными, описанного выше формата.

2.[Вход] Число. Параметр k - требуемый размер вершинного покрытия.

3.[Выход] Файл с результатом – оптимальным покрытием. Содержит одну строку, в которой через пробел указаны номера вершин, входящих в покрытие. Нумерация – от 1.

4.[Выход] Файл с результатом – стоимостью оптимального решения (мощность минимального покрытия). Содержит 1 строку с натуральным числом.

5.[Выход] Файл с замером временной сложности. Файл с двумя строками. В первой строке – время расчёта в секундах (с точностью до 3 знаков после запятой, т.е. до миллисекунд). Во второй строке – количество операций. Операциями считаем операции присваивания и сравнения элементов массивов (массива A и вспомогательных массивов/других структур). Начиная с 3-й строки - трассировочные сообщения о выполняемых преобразованиях. Для каждого преобразования сообщение должно располагаться в отдельной строке файла. Формат сообщения зависит от применяемого метода и выполняемого преобразования (вместо многоточий надо вставлять фактические значения).

а) для древовидного перебора ограниченной глубины:

- "Помещаем в покрытие вершину ... степени 1; k=..."

- "Для вершины ... степени 2; помещаем в покрытие обоих соседей: ... и ...; k=..."
- "Для вершины ... степени 2; помещаем в покрытие всех соседей обоих соседей: ...,  ...; k=..."
- "Для вершины ... степени 3; помещаем в покрытие саму вершину; k=..."
- "Для вершины ... степени 3; помещаем в покрытие всех её соседей: ....; k=..."
б) Для параметрической редукции:
- "Удаляем изолированные вершины: ..."
- "Для вершины ... степени 1 помещаем в покрытие её соседа ...; k=..."
- "Помещаем в покрытие вершину ... степени > ...; k= ..."
- "Обрабатываем ядро из ... вершин".
в) Для итерационного сжатия:
- "Для графа, порождённого вершинами ... преобразуем покрытие ... в покрытие ..." // сообщение при выходе из процедуры Сжатие
- "Проверка разбиения: Y=..., S=..., новые вершины покрытия: ..."