Лекция: Доминирующее множество вершин

Доминирующим множеством (вершин) графа G=(V,E) является подмножество V’ V такое, что любая вершина, не находящаяся в V', соединяется по крайней мере одним ребром в вершинами из V’.

γ(G) –доминантное число графа.Является числом вершин самого меньшего доминирующего множества графа.

Проблема нахождения наименьшего доминирующего множества относится к NP-полным, а нахождение доминирующего числа – NP-тяжелая задача.

Доминирующие множества тесно связаны с независимыми множествами: максимальное независимое множество в графе необходимо является доминирующим множеством. Однако, доминирующее множество может и не быть независимым.

Если S – связное доминирующее множество, то можно сформировать каркасное дерево графа G, в котором S формирует множество вершин дерева, не принадлежащим листьям (степени 1). Если T – каркасное дерево графа с тремя и более вершинами, то не листовые вершины дерева T формируют связное доминирующее множество. Таким образом, нахождение минимального связного доминирующего множества эквивалентно нахождению каркасного дерева с максимально возможным числом листьев.

Тропа в графе G называется эйлеровой, если она включает в себя все ребра графа G.

Замкнутая эйлерова тропа носит название эйлеров тур или эйлеров цикл.

Граф, содержащий эйлеров цикл, называется эйлеровым.

Граф G имеет эйлеров цикл тогда и только тогда, когда он является связанным и когда степени всех его вершин четны.

Нахождение циклов в эйлеровом графе:

1. Проверить, является ли данный граф эйлеровым;

2. Выбрать произвольную начальную вершину графа в качестве текущей вершины; все ребра – непомечены;

3. Выбрать любое непомеченное ребро, инцидентное текущей вершине, и пометить его (например, задав его жирной линией или присвоив ему имя). Замечания: а) выделение ребра необходимо для того, чтобы при исполнении алгоритма выбирать непомеченные ребра;

б) выбор моста (ребра разреза) в качестве текущего ребра необходимо делать только в крайнем случае, когда нет иной возможности.

4. Перейти по выбранному ребру ко второй вершине этого ребра;

5. Повторить 3-4 до тех пор, пока не будут пройдены все вершины, и алгоритм не возвратиться в начальную вершину.

Остальные шаги алгоритма очевидны. Эйлеров цикл: F,C,D,A,C,E,A,B,D,F.

Полуэйлеровым будет связный граф, который содержит открытый путь.

Связной граф будет полуэйлеровым тогда и только тогда, когда в нем имеется точно две вершины нечетной степени.

Алгоритм Флери применим и для нахождения открытого пути полуэйлерова графа.

Гамильтоновым путем является путь, проходящий каждую вершину графа G .

Гамильтонов цикл – это цикл, проходящий каждую вершину графа G только один раз.

Любой гамильтонов цикл может быть преобразован в гамильтонов путь удалением одного ребра цикла, однако обратное можно осуществить только в том случае, если конечные вершины пути инцидентны друг другу.

Граф G, который содержит гамильтонов цикл, называется гамильтоновым графом.

Граф G, содержащий гамильтонов путь, называется полугамильтоновым графом.

В отличие от эйлеровых графов, неизвестна теорема, которая бы полностью характеризовала гамильтоновы графы. Известны лишь теоремы с достаточными, но не необходимыми условиями.

Если в графе G с n вершинами (n ³ 3) для любой вершины vi выполняется неравенство

deg(vi) ³ n/2 ,

то граф G – гамильтонов.

Проблема нахождения гамильтонова цикла в графе является частным случаем проблемы путешествующего купца (см. взвешенные графы), когда расстояния между двумя вершинами, соединенных ребром, равно 1 и равно бесконечности в других случаях.

Проблемы нахождения гамильтоновых циклов и гамильтоновых путей являются NP-полными. Однако существуют типы графов, всегда содержащие гамильтонов путь (например, турнир (tournament)).

Существует огромная литература по поиску гамильтоновых путей и циклов.

2.12. Понятие “почти все” графы

Пусть G(n)- множество всех графов на множестве вершин V={1,2,…,n}.Пусть Р — некоторое свойство, которым каждый граф из G(n) может обладать или нет.

Пусть Gp(n)-множество тех графов из G(n), которые обладают свойством Р.

Говорят, что почти все графы обладают свойством Р, если

lim =1

n-∞

и почти нет графов со свойством Р, если

lim =0

n-∞