Some properties of graph edge clique coverings.pdf Реберным покрытием кликами (РПК) графа G называется такой набор клик (полныхподграфов) К 1,..., Kr, что любое ребро графа G лежит хотя бы в одной из этихклик. Задача построения РПК, минимального по числу входящих в него клик, как известно,является NP-полной (см., например, [1]). Поскольку каждую из клик в набореможно дополнить произвольным образом до максимальной клики и получить такжеРПК, то будем считать, что в определении РПК и далее речь идет о максимальныхкликах.Легко выделить клики, которые обязаны содержаться в каждом РПК для данногографа. Назовем ребро e графа G собственным ребром клики K , если оно лежитв этой клике и не лежит ни в какой другой клике графа G. Соответственно клику K ,имеющую хотя бы одно собственное ребро, назовем зафиксированной.Как известно, вершина графа называется доминирующей, если она соединена ребромс каждой из остальных вершин графа.Определение 1. Конструкцией C в графе G будем называть порожденный подграфграфа G, обладающий ненулевым количеством доминирующих вершин, и такой,что граф, получающийся из графа C удалением всех доминирующих вершин и инцидентныхим рёбер, является непустым и связным.В работе доказывается, что в связном графе без собственных рёбер существуетконструкция.Конструкция C может быть пригодной или непригодной для разбиения графа, чтоопределяется свойствами рёбер, входящих в неё. Данные свойства подробно исследованыв работе. Все рёбра пригодной конструкции разбиваются на две категории: те,которые в минимальном покрытии должны покрываться кликой, содержащейся внутриконструкции (категория 1), и те, которые могут покрываться вне клики без потерисвойства минимальности (категория 2).Основным содержанием работы можно считать следующее утверждение:Теорема 1. Пусть R1, ..., Rs - минимальное РПК конструкции C , пригодной дляразбиения графа, с вычеркнутыми рёбрами категории 2. Пусть также L1, ..., Lr - минимальноеРПК оставшейся части графа G. Тогда R1, ..., R s, L1, ..., Lr - минимальноеРПК графа G.В работе приводится эвристический алгоритм поиска рёберных покрытий в графе,основанный на использовании данной теоремы и состоящий из следующих основныхшагов:1. Поиск собственных рёбер в графе. Фиксирование соответствующих клик.2. Поиск конструкции, пригодной для разбиения графа. В случае, если пригодныхконструкций в графе не существует, выбирается конструкция, наиболее приближеннаяк пригодной для разбиения. В случае, если ни одной конструкции не былонайдено, для процедуры разбиения в качестве аналога разбивающей конструкциивыбирается наименьшее по мощности окружение ребра.3. Разбиение исходного графа на два графа: в первый из графов входят те рёбра,которые относятся к конструкции, а во второй граф - все остальные рёбра.4. Рекурсивное применение данного алгоритма к обоим графам.5. Объединение полученных покрытий.Для некоторых классов графов данный алгоритм является точным. В работе представленытакие графы.

Скачать электронную версию публикации