Независимые и покрывающие множества

· Вершина покрывает инцидентные ей рёбра, а ребро покрывает инцидентные ему вершины.

· Множество таких вершин, которые покрывают все рёбра, называется вершинным покрытием. — Наименьшее число вершин во всех вершинных покрытиях называется числом вершинного покрытия.

· Множество таких рёбер, которые покрывают все вершины, называется рёберным покрытием. —наименьшее число рёбер во всех рёберных покрытиях называется ч ислом рёберного покрытия.

· Множество вершин называется независимым, если никакие две из них не смежны. — Наибольшее число вершин в независимом множестве – вершинное числщ независимости.

· Множество рёбер называется независимым (паросочетанием), если никакие два из них не смежны. — Наибольшее число рёбер в паросочетании – рёберное число независимости.

Для любого нетривиального связного графа сумма вершинных чисел покрытия и независимости равна сумме рёберных чисел покрытия и независимости.

Отступление. Задача отыскания экстремальных независимых и покрывающих множеств возникает во многих практических случаях. Например, пусть есть множество процессов (работ), использующих неразделяемые ресурсы. Соединим рёбрами вершины, которым требуется один и тот же ресурс. Тогда вершинное число независимости будет определять количество возможных параллельных процессов.

Задача о восьми ферзях – расставить на шахматной доске 8 ферзей так, чтобы они не били друг друга – задача об отыскании максимальных независимых множеств. Доска – граф с 64 вершинами, которые смежны, если находятся на одной горизонтали, вертикали или диагонали.

Задачи отыскания независимых множеств графа принадлежат к числу трудоёмких. Трудоёмкой является также задача поиска клик – полных подграфов данного графа. Это задача поиска наиболее зависимого множества.