Во многих задачах на графах требуется найти какой-нибудь максимум или минимум, например, наибольший подграф с заданным свойством, или разбиение графа на наименьшее число частей, удовлетворяющих каким-то условиям, и т.д. В оставшихся лекциях рассматриваются несколько задач такого рода, считающихся классическими в теории графов. Некоторые из них известны как NP-трудные, для них рассматриваются переборные алгоритмы, приемы рационализации, эвристики и приближенные алгоритмы. Для других задач излагаются известные эффективные алгоритмы.
(рис 9.1) Между задачами о независимом множестве и о вершинном покрытии тоже имеется простая связь благодаря следующему факту.
Теорема 1. Подмножество $$U$$ множества вершин графа $$G$$ является вершинным
покрытием тогда и только тогда, когда $$\overline{U}={VG-U}$$ -
Доказательство. Если $$U$$ - вершинное покрытие, то всякое ребро содержит хотя бы одну вершину из множества $$U$$ и, значит, нет ни одного ребра, соединяющего две вершины из множества $$\overline{U}$$. Следовательно, $$\overline{U}$$ - независимое множество. Обратно, если $$\overline{U}$$ - независимое множество, то нет ребер, соединяющих вершины из $$\overline{U}$$ и, значит, у каждого ребра одна или обе вершины принадлежат множеству $$U$$. Следовательно, $$U$$ - вершинное покрытие.
Из этой теоремы следует, что $$\alpha(G)+\beta(G)=n$$ для любого графа $$G$$ с $$n$$ вершинами.
Таким образом, все три задачи тесно связаны друг с другом, так что достаточно научиться решать одну из них, и мы будем уметь решать остальные две. Вместе с тем известно, что эти задачи NP-полны. Для таких задач не известно эффективных алгоритмов, а накопленный к настоящему времени опыт делает правдоподобным предположение о том, что таких алгоритмов и не существует. Тем не менее, алгоритмы для подобных задач разрабатывались и продолжают разрабатываться, и в некоторых случаях они могут быть полезны. Все эти алгоритмы в той или иной форме осуществляют перебор вариантов (число которых может быть очень большим). Далее рассмотрим один из способов такого перебора для задачи о независимом множестве.
Пусть $$G$$ - граф, в котором требуется найти наибольшее независимое множество. Выберем в нем произвольную вершину $$a$$. Обозначим через $$G_{1}$$ подграф, получающийся удалением из графа $$G$$ вершины $$a$$, т.е. $$G_{1} =G-a$$, а через $$G_{2}$$ - подграф, получающийся удалением из $$G$$ всех вершин, смежных с $$a$$. На рисунке 9.2 показаны графы $$G_{1}$$ и $$G_{2}$$, получающиеся из графа $$G$$, изображенного на рис. 9.1, при $$a=1$$.
(рис 9.2) Пусть $$X$$ - какое-нибудь независимое множество графа $$G$$. Если оно не содержит вершины $$a$$, то оно является независимым множеством графа $$G_{1}$$. Если же $$a\in X$$, то никакая вершина, смежная с $$a$$, не принадлежит $$X$$. В этом случае множество $$X$$ является независимым множеством графа $$G_{2}$$. Заметим, что в графе $$G_{1}$$ на одну вершину меньше, чем в исходном графе $$G$$. Если вершина $$a$$ не является изолированной, то и в графе $$G_{2}$$ вершин меньше, чем в графе $$G$$. Таким образом, задача о независимом множестве для графа $$G$$ свелась к решению той же задачи для двух графов меньшего размера. Это приводит к рекуррентному соотношению для числа независимости:
$$\alpha (G)=\max \{ \alpha (G_{1} ),\alpha (G_{2} )\} $$и к рекурсивному алгоритму для нахождения наибольшего независимого
множества графа $$G:$$ найдем наибольшее независимое
множество $$X_{1}$$ графа $$G_{1}$$, затем наибольшее
независимое множество $$X_{2}$$ графа $$G_{2}$$ и выберем
большее из этих двух множеств. В целом процесс
решения задачи при этом можно рассматривать как исчерпывающий поиск
в возникающем дереве подзадач. Чтобы не путать вершины дерева и вершины
графа, вершины дерева будем называть узлами. Узел, не являющийся листом,
называется внутренним узлом. Каждому внутреннему узлу дерева соответствует
некоторый граф $$H$$ и некоторая вершина этого графа $$x$$.
Вершину $$x$$ можно выбирать произвольно, но она не должна быть
Для нахождения наибольшего независимого множества не обязательно строить
все дерево полностью, а достаточно обойти его в том или ином порядке,
запоминая на каждом шаге только небольшую часть информации об устройстве
этого дерева. Можно, например, применить
Для одного и того же графа могут получиться разные деревья в зависимости
от того, как выбирается активная вершина $$x$$ в каждом узле
дерева. Может быть различным и число листьев в этих деревьях, а значит,
и трудоемкость алгоритма, основанного на обходе дерева. Однако в любом
случае листьев в дереве будет не меньше, чем максимальных независимых
множеств у графа, так как каждое из этих множеств будет соответствовать
некоторому листу. Так, для графа $$pK_{2}$$, т.е. графа, состоящего
из $$p$$
Одна из эвристических идей состоит в том, чтобы рассмотреть только один путь от корня до листа в дереве вариантов в надежде, что этому листу соответствует достаточно большое независимое множество. Для выбора этого единственного пути могут применяться разные соображения. В дереве вариантов, описанном выше, у каждого внутреннего узла имеются два сына. Одному из них соответствует подграф, получающийся удалением некоторой произвольно выбранной вершины $$a$$, а другому - подграф, получающийся удалением окрестности этой вершины. Чтобы вместо дерева получился один путь, достаточно каждый раз выполнять какую-нибудь одну из этих двух операций. Рассмотрим оба варианта.
Допустим, мы решили каждый раз удалять выбранную вершину. Эти удаления производятся до тех пор, пока не останется граф без ребер, т.е. независимое множество. Оно и принимается в качестве решения задачи. Для полного описания алгоритма необходимо еще сформулировать правило выбора активной вершины $$a$$. Мы хотим получить граф без ребер, в котором было бы как можно больше вершин. Чем меньше вершин будет удалено, тем больше их останется. Значит, цель - как можно быстрее удалить все ребра. Кажется, мы будем двигаться в нужном направлении, если на каждом шаге будем удалять наибольшее возможное на этом шаге число ребер. Это означает, что в качестве активной вершины всегда нужно выбирать вершину наибольшей степени. Алгоритмы такого типа называются жадными или градиентными. К сожалению, как будет показано дальше, оптимальный выбор на каждом шаге не гарантирует получения оптимального решения в конечном итоге.
Другой вариант - каждый раз удалять окрестность активной вершины $$a $$. Это повторяется до тех пор, пока оставшиеся вершины не будут образовывать независимого множества. Удаление окрестности вершины $$a$$ равносильно тому, что сама эта вершина включается в независимое множество, которое будет получено в качестве ответа. Так как мы хотим получить в итоге как можно большее независимое множество, следует стараться удалять на каждом шаге как можно меньше вершин. Это означает, что в качестве активной вершины всегда нужно выбирать вершину наименьшей степени. Получается еще один вариант жадного алгоритма.
Имеется немало графов, для которых каждая из этих эвристик дает близкое к оптимальному, а иногда и оптимальное решение. Но, как это обычно бывает с эвристическими алгоритмами, можно найти примеры графов, для которых найденные решения будут весьма далеки от оптимальных. Рассмотрим граф $$G_{k}$$, у которого множество вершин $$V$$ состоит из трех частей мощности $$k$$ каждая: $$V=A\cup B_{1} \cup B_{2}$$, причем $$A$$ является независимым множеством, каждое из множеств $$B_{1}$$, $$B_{2}$$ - кликой, и каждая вершина из множества $$A$$ смежна с каждой вершиной из множества $$B_{1} \cup B_{2}$$. С помощью операций суммы и соединения графов этот граф можно представить формулой $$G_{k} =(2K_{k})\circ O_{k} $$. Степень каждой вершины из множества $$A$$ в этом графе равна $$2k$$, а степень каждой вершины из множества $$B_{1} \cup B_{2}$$ равна $$2k-1$$. Первый алгоритм, выбирающий вершину наибольшей степени, будет удалять вершины из множества $$A$$ до тех пор, пока не удалит их все. После этого останется граф, состоящий из двух клик, и в конечном итоге будет получено независимое множество из двух вершин. Второй алгоритм на первом шаге возьмет в качестве активной одну из вершин множества $$B_{1} \cup B_{2}$$ и удалит всю ее окрестность. В результате получится граф, состоящий из этой вершины и клики, а после второго шага получится независимое множество, состоящее опять из двух вершин. Итак, при применении к этому графу любой из двух эвристик получается независимое множество из двух вершин. В то же время в графе имеется независимое множество $$A$$ мощности $$k$$.
Иногда для алгоритма, не гарантирующего точного решения, удается получить оценку степени приближения, т.е. отклонения получаемого решения от точного. В таком случае говорят о приближенном алгоритме. Рассмотрим один простой приближенный алгоритм для задачи о вершинном покрытии.
Работа алгоритма начинается с создания пустого множества $$X$$ и состоит в выполнении однотипных шагов, в результате каждого из которых к множеству $$X$$ добавляются некоторые вершины. Допустим, перед очередным шагом имеется некоторое множество вершин $$X$$. Если оно покрывает все ребра (т.е. каждое ребро инцидентно одной из этих вершин), то процесс заканчивается и множество $$X$$ принимается в качестве искомого вершинного покрытия. В противном случае выбирается какое-нибудь непокрытое ребро $$(a,b)$$, и вершины $$a$$ и $$b$$ добавляются к множеству $$X$$.
Для полного описания алгоритма нужно бы еще сформулировать правило выбора ребра $$(a,b)$$. Однако для оценки степени приближения, которая будет сейчас получена, это не имеет значения. Можно считать, что какое-то правило выбрано.
Обозначим через $$\beta'(G)$$ мощность вершинного покрытия, которое получится при применении этого алгоритма к графу $$G$$, и докажем, что $$\beta'(G)\le 2\beta (G)$$. Иначе говоря, полученное с помощью этого алгоритма решение не более чем в два раза отличается от оптимального.
Действительно, допустим, что до окончания работы алгоритм выполняет $$k$$ шагов, добавляя к множеству $$X$$ вершины ребер $$(a_{1},b_{1}),\ldots$$, $$(a_{k},b_{k})$$. Тогда $$\beta'(G)=2k$$. Никакие два из этих $$k$$ ребер не имеют общей вершины. Значит, чтобы покрыть все эти ребра, нужно не меньше $$k$$ вершин. Следовательно, $$\beta (G)\ge k$$ и $$\beta '(G)\le 2\beta (G)$$.
Основной недостаток изложенного выше способа организации перебора состоит в том, что при нем часто рассматриваются не только максимальные независимые множества. Это означает, что делается заведомо лишняя работа, так как наибольшее независимое множество находится, конечно, среди максимальных. Кроме того в некоторых случаях бывает необходимо знать все максимальные независимые множества. Рассмотрим алгоритм, который строит все максимальные и только максимальные независимые множества графа.
Предположим, что вершинами заданного графа $$G$$ являются
числа $$1,2\ldots n$$. Рассматривая любое подмножество множества
вершин, будем
выписывать его элементы в порядке возрастания.
Нетрудно найти лексикографически первое максимальное независимое
множество: нужно на каждом шаге брать наименьшую из оставшихся вершин,
добавлять ее к построенному независимому множеству, а все смежные с ней
вершины удалять из графа. Если граф задан
Допустим теперь, что $$U\subseteq VG$$, $$G'$$ - подграф графа $$G$$, порожденный множеством $$U$$, и пусть имеется список $$L$$ всех максимальных независимых множеств графа $$G$$. Тогда однократным просмотром списка $$L$$ можно получить список $$L'$$ всех максимальных независимых множеств графа $$G'$$. Это основано на следующих очевидных утверждениях:
Будем теперь рассматривать множества из $$L$$ одно за другим и пусть $$M$$ - очередное такое множество. Положим $$N=M\cap U$$. Если $$N$$ не является максимальным независимым множеством графа $$G'$$, то переходим к следующему элементу списка $$L$$. Если же $$N$$ - максимальное независимое множество в $$G'$$, то рассматриваем множество $$M-N$$. Если оно является лексикографически первым среди максимальных независимых множеств подграфа, порожденного множеством $$VG-(U\cup V(N))$$, то включаем $$N$$ в список $$L'$$.
Выберем в графе $$G$$ произвольную вершину $$a$$ и пусть $$A$$ - множество всех вершин графа, смежных с $$a$$ (окрестность вершины $$a$$ ), $$B$$ - множество всех вершин, не смежных с $$a$$ и отличных от $$a$$. Обозначим через $$G_{1}$$ подграф, получающийся удалением из графа $$G$$ вершины $$a$$, а через $$G_{2}$$ подграф, получающийся удалением из $$G$$ всех вершин множества $$A\cup \{ a\}$$. Иначе говоря, $$G_{1}$$ - подграф графа $$G$$, порожденный множеством $$A\cup B$$, а $$G_{2}$$ - подграф, порожденный множеством $$B$$.
Допустим, что имеется список $$L_{1}$$ всех максимальных независимых множеств графа $$G_{1}$$. На основании вышеизложенного можно предложить следующую процедуру получения списка $$L$$ всех максимальных независимых множеств графа $$G$$.
Начиная с одновершинного графа (у которого список максимальных независимых
множеств состоит из одного элемента), добавляя последовательно по одной
вершине, получаем последовательность графов $$G_{1} ,G_{2}\ldots G_{n}
=G$$.
Применяя для каждого $$i=1\ldots n-1$$ описанный алгоритм для
построения списка всех максимальных независимых множеств
графа $$G_{i+1}$$ по такому списку для графа $$G_{i}$$, в
конце концов получим список
всех максимальных независимых множеств графа $$G$$. По сути дела, этот
алгоритм представляет собой
Изложенный алгоритм можно применить для поиска наибольших независимых множеств в графах, про которые известно, что в них мало максимальных независимых множеств. Одним из классов графов с таким свойством является класс всех графов, не содержащих $$2K_{2}$$ в качестве порожденного подграфа. Известно, что в графе с $$m$$ ребрами из этого класса число максимальных независимых множеств не превосходит $$m+1$$$.
Во многих задачах на графах требуется найти какой-нибудь максимум или минимум, например, наибольший подграф с заданным свойством, или разбиение графа на наименьшее число частей, удовлетворяющих каким-то условиям, и т.д. В оставшихся лекциях рассматриваются несколько задач такого рода, считающихся классическими в теории графов. Некоторые из них известны как NP-трудные, для них рассматриваются переборные алгоритмы, приемы рационализации, эвристики и приближенные алгоритмы. Для других задач излагаются известные эффективные алгоритмы.
(рис 9.1) Между задачами о независимом множестве и о вершинном покрытии тоже имеется простая связь благодаря следующему факту.
Теорема 1. Подмножество $$U$$ множества вершин графа $$G$$ является вершинным
покрытием тогда и только тогда, когда $$\overline{U}={VG-U}$$ -
Доказательство. Если $$U$$ - вершинное покрытие, то всякое ребро содержит хотя бы одну вершину из множества $$U$$ и, значит, нет ни одного ребра, соединяющего две вершины из множества $$\overline{U}$$. Следовательно, $$\overline{U}$$ - независимое множество. Обратно, если $$\overline{U}$$ - независимое множество, то нет ребер, соединяющих вершины из $$\overline{U}$$ и, значит, у каждого ребра одна или обе вершины принадлежат множеству $$U$$. Следовательно, $$U$$ - вершинное покрытие.
Из этой теоремы следует, что $$\alpha(G)+\beta(G)=n$$ для любого графа $$G$$ с $$n$$ вершинами.
Таким образом, все три задачи тесно связаны друг с другом, так что достаточно научиться решать одну из них, и мы будем уметь решать остальные две. Вместе с тем известно, что эти задачи NP-полны. Для таких задач не известно эффективных алгоритмов, а накопленный к настоящему времени опыт делает правдоподобным предположение о том, что таких алгоритмов и не существует. Тем не менее, алгоритмы для подобных задач разрабатывались и продолжают разрабатываться, и в некоторых случаях они могут быть полезны. Все эти алгоритмы в той или иной форме осуществляют перебор вариантов (число которых может быть очень большим). Далее рассмотрим один из способов такого перебора для задачи о независимом множестве.
Пусть $$G$$ - граф, в котором требуется найти наибольшее независимое множество. Выберем в нем произвольную вершину $$a$$. Обозначим через $$G_{1}$$ подграф, получающийся удалением из графа $$G$$ вершины $$a$$, т.е. $$G_{1} =G-a$$, а через $$G_{2}$$ - подграф, получающийся удалением из $$G$$ всех вершин, смежных с $$a$$. На рисунке 9.2 показаны графы $$G_{1}$$ и $$G_{2}$$, получающиеся из графа $$G$$, изображенного на рис. 9.1, при $$a=1$$.
(рис 9.2) Пусть $$X$$ - какое-нибудь независимое множество графа $$G$$. Если оно не содержит вершины $$a$$, то оно является независимым множеством графа $$G_{1}$$. Если же $$a\in X$$, то никакая вершина, смежная с $$a$$, не принадлежит $$X$$. В этом случае множество $$X$$ является независимым множеством графа $$G_{2}$$. Заметим, что в графе $$G_{1}$$ на одну вершину меньше, чем в исходном графе $$G$$. Если вершина $$a$$ не является изолированной, то и в графе $$G_{2}$$ вершин меньше, чем в графе $$G$$. Таким образом, задача о независимом множестве для графа $$G$$ свелась к решению той же задачи для двух графов меньшего размера. Это приводит к рекуррентному соотношению для числа независимости:
$$\alpha (G)=\max \{ \alpha (G_{1} ),\alpha (G_{2} )\} $$и к рекурсивному алгоритму для нахождения наибольшего независимого
множества графа $$G:$$ найдем наибольшее независимое
множество $$X_{1}$$ графа $$G_{1}$$, затем наибольшее
независимое множество $$X_{2}$$ графа $$G_{2}$$ и выберем
большее из этих двух множеств. В целом процесс
решения задачи при этом можно рассматривать как исчерпывающий поиск
в возникающем дереве подзадач. Чтобы не путать вершины дерева и вершины
графа, вершины дерева будем называть узлами. Узел, не являющийся листом,
называется внутренним узлом. Каждому внутреннему узлу дерева соответствует
некоторый граф $$H$$ и некоторая вершина этого графа $$x$$.
Вершину $$x$$ можно выбирать произвольно, но она не должна быть
Для нахождения наибольшего независимого множества не обязательно строить
все дерево полностью, а достаточно обойти его в том или ином порядке,
запоминая на каждом шаге только небольшую часть информации об устройстве
этого дерева. Можно, например, применить
Для одного и того же графа могут получиться разные деревья в зависимости
от того, как выбирается активная вершина $$x$$ в каждом узле
дерева. Может быть различным и число листьев в этих деревьях, а значит,
и трудоемкость алгоритма, основанного на обходе дерева. Однако в любом
случае листьев в дереве будет не меньше, чем максимальных независимых
множеств у графа, так как каждое из этих множеств будет соответствовать
некоторому листу. Так, для графа $$pK_{2}$$, т.е. графа, состоящего
из $$p$$
Одна из эвристических идей состоит в том, чтобы рассмотреть только один путь от корня до листа в дереве вариантов в надежде, что этому листу соответствует достаточно большое независимое множество. Для выбора этого единственного пути могут применяться разные соображения. В дереве вариантов, описанном выше, у каждого внутреннего узла имеются два сына. Одному из них соответствует подграф, получающийся удалением некоторой произвольно выбранной вершины $$a$$, а другому - подграф, получающийся удалением окрестности этой вершины. Чтобы вместо дерева получился один путь, достаточно каждый раз выполнять какую-нибудь одну из этих двух операций. Рассмотрим оба варианта.
Допустим, мы решили каждый раз удалять выбранную вершину. Эти удаления производятся до тех пор, пока не останется граф без ребер, т.е. независимое множество. Оно и принимается в качестве решения задачи. Для полного описания алгоритма необходимо еще сформулировать правило выбора активной вершины $$a$$. Мы хотим получить граф без ребер, в котором было бы как можно больше вершин. Чем меньше вершин будет удалено, тем больше их останется. Значит, цель - как можно быстрее удалить все ребра. Кажется, мы будем двигаться в нужном направлении, если на каждом шаге будем удалять наибольшее возможное на этом шаге число ребер. Это означает, что в качестве активной вершины всегда нужно выбирать вершину наибольшей степени. Алгоритмы такого типа называются жадными или градиентными. К сожалению, как будет показано дальше, оптимальный выбор на каждом шаге не гарантирует получения оптимального решения в конечном итоге.
Другой вариант - каждый раз удалять окрестность активной вершины $$a $$. Это повторяется до тех пор, пока оставшиеся вершины не будут образовывать независимого множества. Удаление окрестности вершины $$a$$ равносильно тому, что сама эта вершина включается в независимое множество, которое будет получено в качестве ответа. Так как мы хотим получить в итоге как можно большее независимое множество, следует стараться удалять на каждом шаге как можно меньше вершин. Это означает, что в качестве активной вершины всегда нужно выбирать вершину наименьшей степени. Получается еще один вариант жадного алгоритма.
Имеется немало графов, для которых каждая из этих эвристик дает близкое к оптимальному, а иногда и оптимальное решение. Но, как это обычно бывает с эвристическими алгоритмами, можно найти примеры графов, для которых найденные решения будут весьма далеки от оптимальных. Рассмотрим граф $$G_{k}$$, у которого множество вершин $$V$$ состоит из трех частей мощности $$k$$ каждая: $$V=A\cup B_{1} \cup B_{2}$$, причем $$A$$ является независимым множеством, каждое из множеств $$B_{1}$$, $$B_{2}$$ - кликой, и каждая вершина из множества $$A$$ смежна с каждой вершиной из множества $$B_{1} \cup B_{2}$$. С помощью операций суммы и соединения графов этот граф можно представить формулой $$G_{k} =(2K_{k})\circ O_{k} $$. Степень каждой вершины из множества $$A$$ в этом графе равна $$2k$$, а степень каждой вершины из множества $$B_{1} \cup B_{2}$$ равна $$2k-1$$. Первый алгоритм, выбирающий вершину наибольшей степени, будет удалять вершины из множества $$A$$ до тех пор, пока не удалит их все. После этого останется граф, состоящий из двух клик, и в конечном итоге будет получено независимое множество из двух вершин. Второй алгоритм на первом шаге возьмет в качестве активной одну из вершин множества $$B_{1} \cup B_{2}$$ и удалит всю ее окрестность. В результате получится граф, состоящий из этой вершины и клики, а после второго шага получится независимое множество, состоящее опять из двух вершин. Итак, при применении к этому графу любой из двух эвристик получается независимое множество из двух вершин. В то же время в графе имеется независимое множество $$A$$ мощности $$k$$.
Иногда для алгоритма, не гарантирующего точного решения, удается получить оценку степени приближения, т.е. отклонения получаемого решения от точного. В таком случае говорят о приближенном алгоритме. Рассмотрим один простой приближенный алгоритм для задачи о вершинном покрытии.
Работа алгоритма начинается с создания пустого множества $$X$$ и состоит в выполнении однотипных шагов, в результате каждого из которых к множеству $$X$$ добавляются некоторые вершины. Допустим, перед очередным шагом имеется некоторое множество вершин $$X$$. Если оно покрывает все ребра (т.е. каждое ребро инцидентно одной из этих вершин), то процесс заканчивается и множество $$X$$ принимается в качестве искомого вершинного покрытия. В противном случае выбирается какое-нибудь непокрытое ребро $$(a,b)$$, и вершины $$a$$ и $$b$$ добавляются к множеству $$X$$.
Для полного описания алгоритма нужно бы еще сформулировать правило выбора ребра $$(a,b)$$. Однако для оценки степени приближения, которая будет сейчас получена, это не имеет значения. Можно считать, что какое-то правило выбрано.
Обозначим через $$\beta'(G)$$ мощность вершинного покрытия, которое получится при применении этого алгоритма к графу $$G$$, и докажем, что $$\beta'(G)\le 2\beta (G)$$. Иначе говоря, полученное с помощью этого алгоритма решение не более чем в два раза отличается от оптимального.
Действительно, допустим, что до окончания работы алгоритм выполняет $$k$$ шагов, добавляя к множеству $$X$$ вершины ребер $$(a_{1},b_{1}),\ldots$$, $$(a_{k},b_{k})$$. Тогда $$\beta'(G)=2k$$. Никакие два из этих $$k$$ ребер не имеют общей вершины. Значит, чтобы покрыть все эти ребра, нужно не меньше $$k$$ вершин. Следовательно, $$\beta (G)\ge k$$ и $$\beta '(G)\le 2\beta (G)$$.
Основной недостаток изложенного выше способа организации перебора состоит в том, что при нем часто рассматриваются не только максимальные независимые множества. Это означает, что делается заведомо лишняя работа, так как наибольшее независимое множество находится, конечно, среди максимальных. Кроме того в некоторых случаях бывает необходимо знать все максимальные независимые множества. Рассмотрим алгоритм, который строит все максимальные и только максимальные независимые множества графа.
Предположим, что вершинами заданного графа $$G$$ являются
числа $$1,2\ldots n$$. Рассматривая любое подмножество множества
вершин, будем
выписывать его элементы в порядке возрастания.
Нетрудно найти лексикографически первое максимальное независимое
множество: нужно на каждом шаге брать наименьшую из оставшихся вершин,
добавлять ее к построенному независимому множеству, а все смежные с ней
вершины удалять из графа. Если граф задан
Допустим теперь, что $$U\subseteq VG$$, $$G'$$ - подграф графа $$G$$, порожденный множеством $$U$$, и пусть имеется список $$L$$ всех максимальных независимых множеств графа $$G$$. Тогда однократным просмотром списка $$L$$ можно получить список $$L'$$ всех максимальных независимых множеств графа $$G'$$. Это основано на следующих очевидных утверждениях:
Будем теперь рассматривать множества из $$L$$ одно за другим и пусть $$M$$ - очередное такое множество. Положим $$N=M\cap U$$. Если $$N$$ не является максимальным независимым множеством графа $$G'$$, то переходим к следующему элементу списка $$L$$. Если же $$N$$ - максимальное независимое множество в $$G'$$, то рассматриваем множество $$M-N$$. Если оно является лексикографически первым среди максимальных независимых множеств подграфа, порожденного множеством $$VG-(U\cup V(N))$$, то включаем $$N$$ в список $$L'$$.
Выберем в графе $$G$$ произвольную вершину $$a$$ и пусть $$A$$ - множество всех вершин графа, смежных с $$a$$ (окрестность вершины $$a$$ ), $$B$$ - множество всех вершин, не смежных с $$a$$ и отличных от $$a$$. Обозначим через $$G_{1}$$ подграф, получающийся удалением из графа $$G$$ вершины $$a$$, а через $$G_{2}$$ подграф, получающийся удалением из $$G$$ всех вершин множества $$A\cup \{ a\}$$. Иначе говоря, $$G_{1}$$ - подграф графа $$G$$, порожденный множеством $$A\cup B$$, а $$G_{2}$$ - подграф, порожденный множеством $$B$$.
Допустим, что имеется список $$L_{1}$$ всех максимальных независимых множеств графа $$G_{1}$$. На основании вышеизложенного можно предложить следующую процедуру получения списка $$L$$ всех максимальных независимых множеств графа $$G$$.
Начиная с одновершинного графа (у которого список максимальных независимых
множеств состоит из одного элемента), добавляя последовательно по одной
вершине, получаем последовательность графов $$G_{1} ,G_{2}\ldots G_{n}
=G$$.
Применяя для каждого $$i=1\ldots n-1$$ описанный алгоритм для
построения списка всех максимальных независимых множеств
графа $$G_{i+1}$$ по такому списку для графа $$G_{i}$$, в
конце концов получим список
всех максимальных независимых множеств графа $$G$$. По сути дела, этот
алгоритм представляет собой
Изложенный алгоритм можно применить для поиска наибольших независимых множеств в графах, про которые известно, что в них мало максимальных независимых множеств. Одним из классов графов с таким свойством является класс всех графов, не содержащих $$2K_{2}$$ в качестве порожденного подграфа. Известно, что в графе с $$m$$ ребрами из этого класса число максимальных независимых множеств не превосходит $$m+1$$$.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.