Задание: Задача о вершинном покрытии минимальной мощности. Дано: число вершин в графе (n) и сам граф в виде матрицы смежности. Получить: количество вершин в найденном вершинном покрытии, а также сам список вершин.
Алгоритмы:
- Переборный;
- Приближенный;
- Жадный.
Задача заключается в том, чтобы выбрать в неориентированном графе минимальное (по количеству вершин) вершинное покрытие.
Формат входных данных: В качестве запрашиваемых входных данных у пользователя будет число вершин в графе (n) и сам граф в виде матрицы смежности. Пользователь может выбрать - вводить данные с клавиатуры, из файла либо сгенерировать автоматически.
Описание реализованных алгоритмов:
Переборный
Перебираются все 2^N наборов вершин; Для каждого набора проверяется – является ли он вершинным покрытием; Из всех покрытий выбирается то, в котором наименьшее число вершин;
Приближенный
Пока в графе есть ребра { Выбрать произвольное (u, v); Добавить вершины u и v в вершинное покрытие; Удалить из графа все ребра, инцидентные u и v; }
Жадный
U=∅. Пока в графе есть непокрытые ребра { Выбрать вершину, которой инцидентно наибольшее количество непокрытых рёбер; Добавить ее в U; }
- Назовем ребро покрытым, если хотя бы один из его концов принадлежит множеству U и непокрытым в противном случае.