Лекция: Доминирующее множество вершин
Доминирующим множеством (вершин) графа G=(V,E) является подмножество V’ V такое, что любая вершина, не находящаяся в V', соединяется по крайней мере одним ребром в вершинами из V’.
γ(G) –доминантное число графа.Является числом вершин самого меньшего доминирующего множества графа.
Проблема нахождения наименьшего доминирующего множества относится к NP-полным, а нахождение доминирующего числа – NP-тяжелая задача.
Доминирующие множества тесно связаны с независимыми множествами: максимальное независимое множество в графе необходимо является доминирующим множеством. Однако, доминирующее множество может и не быть независимым.
Если S – связное доминирующее множество, то можно сформировать каркасное дерево графа G, в котором S формирует множество вершин дерева, не принадлежащим листьям (степени 1). Если T – каркасное дерево графа с тремя и более вершинами, то не листовые вершины дерева T формируют связное доминирующее множество. Таким образом, нахождение минимального связного доминирующего множества эквивалентно нахождению каркасного дерева с максимально возможным числом листьев.
2.10. Эйлеровы графыОпределения
Тропа в графе G называется эйлеровой, если она включает в себя все ребра графа G.
Замкнутая эйлерова тропа носит название эйлеров тур или эйлеров цикл.
Граф, содержащий эйлеров цикл, называется эйлеровым.
| |||
Граф G имеет эйлеров цикл тогда и только тогда, когда он является связанным и когда степени всех его вершин четны.
| |||||
|
Нахождение циклов в эйлеровом графе:
1. Проверить, является ли данный граф эйлеровым;
2. Выбрать произвольную начальную вершину графа в качестве текущей вершины; все ребра – непомечены;
3. Выбрать любое непомеченное ребро, инцидентное текущей вершине, и пометить его (например, задав его жирной линией или присвоив ему имя). Замечания: а) выделение ребра необходимо для того, чтобы при исполнении алгоритма выбирать непомеченные ребра;
б) выбор моста (ребра разреза) в качестве текущего ребра необходимо делать только в крайнем случае, когда нет иной возможности.
4. Перейти по выбранному ребру ко второй вершине этого ребра;
5. Повторить 3-4 до тех пор, пока не будут пройдены все вершины, и алгоритм не возвратиться в начальную вершину.
Остальные шаги алгоритма очевидны. Эйлеров цикл: F,C,D,A,C,E,A,B,D,F.
| |||
Полуэйлеровым будет связный граф, который содержит открытый путь.
Связной граф будет полуэйлеровым тогда и только тогда, когда в нем имеется точно две вершины нечетной степени.
Алгоритм Флери применим и для нахождения открытого пути полуэйлерова графа.
2.11. Гамильтоновы графыОпределения
Гамильтоновым путем является путь, проходящий каждую вершину графа 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-∞
| |||