Основы дискретной математики В.А. Осипова (552659), страница 23
Текст из файла (страница 23)
150 Рис. 4.14, й Й Ч (гг4,ЙЪ;) (4.5) принимает значение И. Чог Е Х Аг П Гоз = 9, Чог ф Х 2У П Гог ф 6. Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ Совокупность минимальных внешне устойчивых подмножеств также можно отыскать методом К. Магу. Рассмотрим граф с вершинами о1, из, ..., ов. Пусть Т вЂ” некоторое внешне устойчивое подмножество, Определим предикаты Рз и сгб, где У4 = И тогда и только тогда, когда гч Е .Т, сг41 = И тогда и только тогда, когда о Е Гоз при 4 ф у, аи = И. Тогда формула Учитывая, что для данного графа сг; принимает значения И или Л, выражение (4.5) есть формула логики высказываний от переменных 1 "1, Ъ~, ..., $гь. Приведем ее к сокращенной дизьюнктивной нормальной форме.
Тогда каждому дизъюнктивному члену ('г41Й'г12Й . ЙЪп) этой дизъюнктивной нормальной формы соответствует минимальное внешне устойчивое подмножество вершин (он, о12, ..., ип). Описанным способом можно получить все минимальные внешне устойчивые подмножества. Применим метод К. Магу для нахождения максимальных внутренне устойчивых и минимальных внешне устойчивых подмножеств графа, изображенного на рис.
4,15 с матрицей смежности 4.4. Устойчивые подмножества графа. Ядра 01000 00110 00000 00000 00100 Рис. 4.15. Формула (4.4) для данного графа примет вид: (~ 1У1 2)Й(~2У1 2)Й(~ 2У14)Й(~ з ~~ з)' Приведя ее к сокращенной дизъюнктивной нормальной форме, получим (Р2Юз) У (71,Й71,Йр,) У (71,~Ю,). Следовательно, граф имеет три максимальных внутренне устойчивых подмножества: (о1, оз, о4), (ог, оз) и (о1, о4, оз). Формула (4.5) для данного графа примет вид: (1'1 ч гг2)Й(г2 Ч гз Ч г4)Йгзй14Й(~ 3 " Ю' Приведя ее к сокращенной дизъюнктивной нормальной форме, получим ('и"1Й 1'ЗЙ 1'4) У (г'2Й'г'ЗЙ 1'4). Следовательно, граф обладает двумя минимальными внешне устойчивыми подмножествами (о1, оз, о4) (о2, оз, о4).
4.4.2. з Ядра графа. Уровни графа В ориентированном графе С =< Ъ; Г ) подмножество Ж С 1' называется ядром графа С, если Аг одновременно внутренне и внешне устойчивое подмножество, т. е. Граф может не обладать ядром или иметь несколько ядер. Например, граф изображенный на рис. 4.1б не имеет ядра, граф изображенный на рис. 4.17 имеет два ядра Х1 = (о1, сз), Х2 = (из, о4). 132 Глава 4.
ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ 133 4.4. устойчивые подмножества графа. Ядра и, ~з и! Рис. 4.16. Рис. 4.17. Для графа, изображенного на рис. 4.15 подмножество вершин (и1, из, и4) является одновременно внешне и внутренне устойчивым и, следовательно, составляет ядро. Выполняется следующее свойство: Ъ'тверждение 4.5. Для таого, чтоб»1 подмпожество Аг вершин гра4а без петель С =< К Г > было ядром, необходимо и достаточно, 1тобы оно было одновременно максимальным внутренне устойчивь м и минимальным внешне устойчивым. Если Аг не совпадает пи с одним максимальным внутренне устойчивым подмножеством, то для некоторого максимального внутренне устойчивого подмножества А такого, что 117 С А найдется вершина и из А не принадлежащая Аг.
Следовательно, Аг П Ги ф Д откуда А П Ги ф 9, что противоречит внутренней устойчивости А. Значит Х = А. Предположим теперь, что Х не является минимальным внешне устойчивым. Тогда можно указать вершину и Е 1'«' такую, что множество Аг' = 1"»"11и) снова является внешне устойчивым Поскольку и ф Х', то найдется такая вершина у е Аг', что у е Гш Так как Х' С Х, то 1«' Г1 Ги ф 9, а это противоречит внутренней устойчивости множества 1«.
В процессе принятия решений для достижения наилучшего результата лицо, принимающее решение, руководствуется определенной целью. Одной из характеристик цели является связанная с ней структура предпочтенглй на ыножестве возможных исходов (вариантов). В дискретных задачах структуру этого предпочтения можно описать графом, вершины которого составляют множество исходов, соединенных дугами, если один из исходов предпочтительнее другого. Для выделения оптимальных вариантов в таких задачах используются методы„связанные с нахождением устойчивых множеств и ядра графа. Те вершины, которые составляют ядро графа, являются «хорошими» вариантами, и мы можем ограничиться при дальнейшем рассмотрении структуры предпочтений только ими, чем сужаем множество вариантов, из которых 11роизводится выбор.
Для иллюстрации рассмотрим следующий пример. Пример 4.14. Требуется осуществить выбор среди семи моделей телевизоров о1, ит, ..., и7,которые оцениваются по следующим четырем показателям: р1 — цена, рг — помехоустойчивость, рз — размер экрана, р4 — внешнее оформление. По цене и помехоустойчивости имеется 4 градации, по размеру экрана — 3, по внешнему оформлению — 5 градаций, Задается таблица балльных оценок модели иг по показателю рь, ь' = 1, 2, ..., 7, й = 1, 2, 3, 4.
Предположим, что система предпочтений лица, осуществляющего выбор, следующая: считается, что телевизор и предпочтительнее телевизора у, если 1) число показателей, по которым объект и строго лучше объекта у, больше, чем число показателей, по которым объект у, строго лучше объекта ьй 2) для объекта и ни один из показателей пе принимает наименьшего из возможных значений (т. е. значения 1). Структура этого предпочтения может быть описана графом, вершинами которого являются модели и1, из, ..., и7, а две вершины иг и и соединены дугой < ип о; >, если модель иг предпочтительнее модели и в соответствии с условиями 1) и 2).
Тем вершинам, которые составляют ядро графа, соответствуют, с точки зрения рассматриваемой структуры предпочтений, «хорошие» модели. Для нахолсдения ядра графа без контуров можно использовать другой метод. Уровнями Хо, Х1, ..., Агг ориентированного графа С = < К Г > не содержащего контуров, называются подмножества 1гго = (иг ~ и, а ь; Гиг = Ф), 1Ч1 = ~иг ~ гч е ~"11Уо, Ги1 ~ 1чо) ~ (4.6) г — 1 т — 1 аг 1„4 ~иг ~ ~''1 О Агы Гиг С 0 117ь), а=о ' ь=о где г — такое наименьшее число, что Г Аг, = 6. -1 135 / \ / 3 1 Ф Рис.
4.18. Рис. 4.19. 134 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ Приведем без доказательства следующее утверждение: Утверждение 4.6. 1) Уровни ориентированного графа без контуров С =< У, Г > — яепустые подмножестпва, образующие разбиение множества его вершин Ъ'. 2) Если С =< Ъ; Г > — ориентированный граф, Хо, Ат1, ..., М, — непустаые подмножества, удовлетпворяющие условиям (4.6) т и такие, что У = 0 )т';, тпо С =< $; Г > — граф без контуров. В=О Уровнями ориентированного графа, изображенного на рис. 4.18 являются подмножества Ато = (из, и4), Х1 = (из, из), )1тг = (и1). Графическая иллюстрация разбиения этого графа на уровни представлена на рис. 4.19.
Опишем алгоритм нахождения уровней графа без контуров по матрице смежности (М. Демукрон). Алгоритм 4.6, Пусть (О1, ио, ..., иа) — множество вершин графа С =< К Г >. Образовываем последовательно строки Ео, Ь1, ..., Ьт длины и, действуя по следующему правилу: 1. В строке Ео = (11), 19(), ..., 1о()) компонента 1( ) равна числу единиц в 4-ой строке матрицы смежности А1О). При этом уровень Ато образуют те вершины ид, для которых 1: ' = О. то) 2. В матрице смежности А(о) заменим нулями все единицы в столбцах с номерами, соответствующими вершинам уровня Юо. Получим матрицу А11) .
3. Образуем строку Ь1 = (11(),1~~), ..., 1п()). Для этого в строке Ео заменим все символы 0 на символ е, т. е„если Ц ' = О, (о) 4 4 устойчивые подмножества гРафа ЯдРа то Ц ' = е; Если же 1,'' ф О, то 1, равна числу единиц в ттй (1) 1о) 00 строке матрицы А11). При этом уровень 1'т'1 образует те вершины из, для которых 1~~ = О. Далее тем же способом образуем строки (1) ьз,ьз, "итд Процесс построения строк заканчивается, когда сформирована строка Ь„, элементы которой содержат лишь нули и символы е.
При этом уровень Х, образуют те вершины,ид, для которых )(т) = О Задачи н упражнения 1. Привести пример ориентированного графа с четырьмя вершинами, обладающего лишь одним минимальным внешне устойчивым множеством, причем состоящим из одной вершины. 2. Используя метод Магу, найти максимальные внутренне устойчивые и минимальные внешне устойчивые подмножества вершин следующих графов. Определить ядра. 3. Имеют ли ядра следующие графы? Если имеют, то найти их. 4. Справедливы ли следующие утверждения? 137 4те Деревьл 4.5.
Деревья Рис. 4.20. 13б Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФО — число внутренне устойчивых подмножеств меньше числа вершин графа; — граф может не иметь внешне устойчивых подмножеств. — граф, содержащий контуры нечетной длины, не имеет ядра. 5. Выберите правильный ответ. Чи 1исло уровнеи графа не изменится при смене ориентации всех дуг на противоположную — для любого графа без контуров; — только для графа, у которого число вершин совпадает с числом уровней; — только для сильно связного графа. 4.5.1. Определение и свойства деревьев Рассмотрим один простой и важный тип графов — деревья.
Понятие дерева важно не только потому, что оно находит приложения в различных областях знания, но и в силу особого положения их в самой теории графов. Последнее связано с предельной простотой строения дерева. Дерево — это связный граф С =< К Я > не имеющий циклов. На рис, 4.20 изображен граф, являющийся деревом. Можно привести несколько других эквивалентных определений дерева: 1. Дерево — это граф, любые две вершины которого можно соединить единственной цепью.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
