В теории графов , край крышки из графика представляет собой набор ребер таким образом, что каждая вершина графа падает , по меньшей мере , одного края набора. В информатике , то минимальная задача край крышки является проблемой нахождения краев крышки минимального размера. Это задача оптимизации, которая относится к классу задач покрытия и может быть решена за полиномиальное время .
Формально ребро крышки графа G представляет собой множество ребер C таким образом, что каждая вершина G падает с , по меньшей мере , одного края в C . Множество C называется покрыть вершины G . На следующем рисунке показаны примеры покрытий ребер в двух графах.
Минимальная кромка покрытие ребро покрытия минимально возможного размера. Номер кромочного покрытия - это размер минимального кромочного покрытия. На следующем рисунке показаны примеры минимального покрытия кромок.
Обратите внимание, что рисунок справа - это не только крайняя крышка, но и совпадение . В частности, это идеальное соответствие : комбинационные М , в котором каждая вершина падает ровно с одним ребром в M . Идеальное совпадение (если оно существует) - это всегда минимальное краевое покрытие.
Наименьшее краевое покрытие можно найти за полиномиальное время , найдя максимальное соответствие и жадно расширив его так, чтобы были покрыты все вершины. [1] [2] На следующем рисунке максимальное соответствие отмечено красным; дополнительные ребра, которые были добавлены для покрытия несогласованных узлов, отмечены синим цветом. (На рисунке справа показан граф, в котором максимальное совпадение является идеальным совпадением ; следовательно, он уже охватывает все вершины, и никаких дополнительных ребер не требовалось.)
С другой стороны, связанная с этим проблема поиска наименьшего вершинного покрытия является NP-трудной задачей. [1]