double arrow

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


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

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

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

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

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

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

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




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

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







Сейчас читают про: