Для графа на рис. 7.2 наибольшее независимое множество есть S3 = {х7, х9, х3, х6 }, и a(G) = 4.
7.4. Кликовое число
Если в связном графе G (Х, А) есть подмножества Fi Î Х вершин, в которых все вершины попарно связаны, то такие подмножества называются полными подграфами или кликами графа G [2].
Для графа на рис. 7.2 можно перечислить несколько клик:
F1 = {х1, х6, х10}, F2 = {х1, х7, х10}, F3 = {х2, х8, х3} и т.д.
Клика, содержащая максимальное число вершин, называется максимальной, а число вершин в этой клике – кликовым числом. Кликовое число для графа на рис. 7.2 равно трем.
Понятно, что чем “плотнее” граф, тем больше его кликовое число и меньше число независимости и, наоборот, для “разреженного” (с небольшим числом ребер) графа число независимости, вероятно, будет больше кликового числа.
7.5. Число внешней устойчивости (число доминирования)
Пусть 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.
Подмножество вершин в графе, являющееся одновременно независимым и доминирующим (внутренне и внешне устойчивым) называют ядром графа; в неориентированном графе все непополнимые (неуменьшаемые) независимые (доминирующие множества) являются ядрами.
Упражнения
7.1. Чему равно хроматическое число полного графа? Нуль графа?
7.2. Привести примеры простых циклов для графа на рис. 7.1.
7.3. Привести пример плоского графа с восемью вершинами и найти оценку его хроматического числа.
7.4. Дан неориентированный граф. а) Перечислить независимые множества графа;
б) Перечислить доминирующие множества графа;
в) Перечислить ядра графа.
7.5. Как по результатам раскраски графа в минимальное число цветов определить число независимости графа?
Библиографический список
1. Оре О. Теори графов. М.: Наука, 1980.
2. Кристофидес Н. Теория графов. Алгоритмический подход. М.:Мир, 1978.
3. Коршунов Ю.М. Математические основы кибернетики
4. Деньдобренько Б.Н., Малика А.С. Автоматизация конструирования РЭА М.: Высшая школа, 1980.
5. Морозов А.М. Основы дискретной математики. Рязань: РРТИ, 1984.
Оглавление
1. Определения, формы представления графов......................................................................................................... .1
2. Части графов.......................................................................................................... .5
3. Характеристики связности. (Путь, контур, цепь, цикл)......................................................................................................... .6
4. Типы графов......................................................................................................... .9
5. Операции над графами....................................................................................................... .13
6. Деревья........................................................................................................ .17
7. Характеристические числа графов....................................................................................................... .19
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.