5.6. Другие задачи о покрытии графов
Большое число задач теории графов можно сформулировать как ЗНП, хотя многие из них могут быть решены более эффективно с помощью иных теоретико-графовых средств, рассмотренных в других частях этой книги. В данном разделе мы хотим показать, как некоторые из этих задач связаны с ЗНП.
5.6.1. Наименьшее доминирующее множество. Как упоминалось в разд. 4 настоящей главы, задача о нахождении наименьшего доминирующего множества графа 
является ЗНП с такой матрицей 
которая получается в результате транспонирования матрицы смежности графа 
с единичными элементами на главной диагонали.
5.6.2. Наибольшее независимое множество. Один из способов нахождения наибольшего независимого множества вершин графа 
состоит в построении всех максимальных независимых множеств вершин и выборе из них множества с наиболыйей мощностью. Другой способ таков: исходная задача интерпретируется
как ЗНП, в которой столбцы матрицы 
соответствуют вершинам графа 
а строки — ребрам, причем 
если вершина 
инцидентна ребру 
в противном случае.
Тогда очевидно [23], что если 
множество столбцов в (наименьшем) решении рассматриваемой ЗНП, то множество 
является наибольшим независимым множеством графа 
Это справедливо потому, что если X — множество, покрывающее ребра графа 
то каждое ребро инцидентно по крайней мере одной вершине из X и, следовательно, никакие две вершины множества 
не могут быть смежными, т. е. 
независимое множество. Более того, если 
является независимым, то каждое ребро графа инцидентно самое большее одной вершине из 
значит, X — множество, покрывающее ребра графа 
Отсюда следует, что дополнение каждого множества вершин, покрывающего ребра графа 
является независимым множеством, а поскольку X имеет наименьшую возможную мощность, то 
есть наибольшее независимое множество.
5.6.3. Наименьшее покрытие и наибольшее паросочетание (см. гл. 12). То, что в литературе называют наименьшим «покрытием», представляет собой множество 
ребер графа 
такое, что каждая вершина графа 
инцидентна по крайней мере одному ребру из 
и мощность множества 
минимально возможная. Таким образом, поскольку 
можно рассматривать как «доминирующее над вершинами» графа 
то множество 
наименьшее из таких множеств — можно назвать, согласно терминологии, использованной в этой главе, наименьшим доминирующим множеством ребер. Известна иная задача о нахождении наименьшего покрытия: нужно отыскать «специальное» множество 
ребер графа 
в 
не должно быть смежных ребер. Множество 
называют паросочетанием, а множество 
с наибольшей мощностью — является наибольшим паросочетанием, его можно называть также наибольшим независимым множеством ребер. Эквивалентность задач о наибольшем паросочетании и о наименьшем покрытии демонстрируется в гл. 12, посвященной изучению паросочетаний. Там устанавливается, в частности, следующее утверждение: пусть в наибольшем покрытии 
степень вершины 
есть 
(рассматриваются только ребра из 
тогда, если для каждой вершины 
удалить 
ребер, инцидентных 
то оставшееся множество ребер образует наибольшее паросочетание. Обратно, если 
есть наибольшее паросочетание и для каждой вершины 
добавляется ребро, инцидентное 
то получающееся множество ребер образует наименьшее покрытие.
Рис. 3.5. Диаграмма взаимосвязей между задачами.
Наибольшие паросочетания и наименьшие покрытия можно описать на «языке» ЗНП. В случае покрытий столбцы матрицы 
представляют ребра графа 
а строки — его вершины, причем 
если вершина 
инцидентна ребру 
а иначе 
Следовательно, матрица 
в этом случае есть матрица инциденций графа 
На рис. 3.5 показана диаграмма взаимосвязей между задачами, где дуга от задачи а к задаче 
означает, что решение задачи а влечет за собой решение задачи 
[34, 39]. Связь между наибольшими независимыми множествами вершин и наибольшими кликами устанавливается с помощью дополнительных графов, а между наибольшими независимыми множествами вершин и наибольшими паросочетаниями — с помощью реберных графов. (Определение реберного графа см. в гл. 10).
5.6.4. Покрытие графа подграфами. Известно целое семейство задач, связанных с покрытием (или разбиением) множества вершин или множества ребер графа специальными подграфами (на специальные подграфы). Например, можно рассматривать порожденные подграфы или остовные подграфы графа, имеющие предписанные свойства. Тогда в матрицах 
из соответствующих ЗНП (или ЗНР) столбцы будут представлять все порожденные подграфы или остовные подграфы с заданными Свойствами, а строки матриц будут представлять вершины или ребра графа. В гл. 4,
рассматривается как ЗНП, в которой строки матрицы 
соответствуют вершинам графа 
а столбцы — максимальным независимым множествам вершин графа 
максимальным вполне несвязным подграфам графа 
[13], или «звездами» («звездными деревьями» графа), или простыми цепями и циклами [16, 42].
