Если в связном графе G (Х, А) есть подмножества Fi Î Х вершин, в которых все вершины попарно связаны, то такие подмножества называются полными подграфами или кликами графа G [2].
Для графа на рис. 7.2. можно перечислить несколько клик:
F1 = {х1, х6, х10}, F2 = {х1, х7, х10}, F3 = {х2, х8, х3} и т.д.
Клика, содержащая максимальное число вершин, называется максимальной, а число вершин в этой клике – кликовым числом. Кликовое число для графа на рис. 7.2. равно трем.
Понятно, что чем “плотнее” граф, тем больше его кликовое число и меньше число независимости и наоборот, для “разреженного” (с небольшим числом ребер) графа число независимости, вероятно, будет больше кликового числа.
6.4. Число внешней устойчивости (число доминирования).
Пусть G(Х,А) – ориентированный или неориентированный граф. Подмножество Fi множества Х (Fi Ì X) называется внешне устойчивым или доминирующим множеством, если каждая не принадлежащая Fi вершина является конечной вершиной некоторой дуги (ребра) от вершины, принадлежащей Fi , т.е. справедливо следующее выражение [1, 2]:
Fi È Г(Fi) = Х.
По аналогии со свойствами внутренне устойчивого множества будем считать внешне устойчивое множество неуменьшаемым, если из него нальзя удалить ни одной вершины без потери свойств доминирования.
Так, для графа рис. 7.2. следующие множества являются неуменьшаемыми доминирующими: F1 ={х7, х9, х6, х3}, F2 = {х1, х5, х8}, F3 = {х2, х4, х10}, F4 = {х10, х3} и др.
Если имеется семейство F доминирующих подмножеств, то подмножество, содержащее наименьшее число вершин, называется наименьшим, а число вершин в нем – числом доминирования или числом внешней устойчивости b(G):
b(G ) = min ½Fi½.
Fi Î F
В графе на рис. 7.2. число доминирования, определяемое наименьшим подмножеством F4, равно двум.
Важно отметить, что в неориентированном графе каждое неуменьшаемое доминирующее множество является одновременно и неполнимым независимым (для ориентированых графов это утверждение несправедливо). В этом можно убедиться, рассматривая граф рис. 7.2., для которого, например, F1 = S3, F2 = S2.
Подмножество вершин в графе, являющееся одновременно независимым и доминирующим (внутренне и внешне устойчивым) называют ядром графа; в неориентированном графе все непополнимые (неуменьшаемые) независимые (доминирующие множества) являются ядрами.
Упражнения.
6.4.1. Дан неориентированный граф
А) Перечислить независимые множества
графа
Б) Перечислить доминирующие множества графа
В) Перечислить ядра графа.
6.4.2. Как по результатам раскраски графа в минимальное число цветов определить число независимости графа?
Библиографический список
1. Оре О. Теори графов. Москва «наука» 1980
2. Кристофидес Н. Теория графов. Алгоритмический подход. Изд-во «Мир» 1978
3. Коршунов Ю.М. Математические основы кибернетики
4. Деньдобренько Б.Н., Малика А.С. Автоматизация конструирования РЭА М., «Высшая школа» 1980
5. Морозов А.М. Основы дискретной математики, Рязань, РРТИ, 1984
Оглавление .
1. Определения, формы представления графов.
2. Части графов.
3. Характеристики связности. (Путь, контур, цепь, цикл).
4. Типы графов.
5. Операции над графами
5 5.1. Объединение графов
5.2. Пересечение графов
6 5.3. Вычитание графов.
7 6. Деревья.
8 7. Характеристические числа графов
9 7.1. Цикломатическое число
10 7.2. Хроматическое число
11 7.3. Число внутренней устойчивости (независимости)
12 7.4. Кликовое число
13 7.5.
Число внешней устойчивости (доминирования).
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.