Главная > Математика > Теория графов. Алгоритмический подход
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

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].

6. Задачи

(см. скан)

(см. скан)

(см. скан)

(см. скан)

7. Список литературы

(см. скан)

(см. скан)

(см. скан)

(см. скан)

<< Предыдущий параграф Следующий параграф >>
Оглавление