Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 39
Текст из файла (страница 39)
3.41). Если предметная шперпретзпия задачи требует реализовать зго зквнввлентнровение не сунеиием сигнатуры, е расширением носителя, то соотвезствуюшие ребре заменяют искью; при зн>м необходимо, чтобы ие иерушился принпип четности. Зздзчз определения минимальных суиения сигнатуры илн рзсшнрения носителя графа С свалится к покрытию соответствуюшей двоичной тзблипы. В денном примере выбираем ребра 7 и, заменяя его пенью длины 3, получаем гомеоморфный граф С, зквиввлентнруюший законный граф С и облвдвюший свойством влоиимостн в булеза пространство.
Ислользуя первую раскраску, Я>(С), раскрвшивзем ребре (2, 5, 8), (1, 6, 11), (4, 7, 9), (3, 10, 12) графе С (рис. ЗА2, а). о>оо мое 5. Сопоставим >еноиествв сопвегных ребер разрядам двоичного векторе: х> = (2, 5, 8), хз = (1, 6, 11), зз = (4, 7, 9), зе ю (3, 10, 12). Кодированием вершин графе С производим фактическое влоиение графа С в булеза прострзнство (рис.
3.42, 6). Теорема 3.40. Если С вЂ” двудольныб граф и его степень равна в(С), то Н(С) = л(С). (3.23) Теорем а 3 41. Хроматический класс любого полного графа на и вершинах Н(К„) равен и, если и нечетное (и 75 1), и равен и — 1, если и чегнное. Приведем точный алгоритм минимальной раскраски вершин (ребер) графа С, т. е. алгоритм определения хроматического числа уз(С) (хроматического класса Н(С)). 1. Выделяем множество вершинно пустых (реберно пустых) подграфов графа С.
2. Строим двумерную таблицу, каждой строке которой сопоставляем взаимно однозначно пустой подграф, столбцу — вершину (ребро): в клетке (з, у) записываем 1, если у-я вершина (2-ребро) содержится в з-м пустом попграфе; в противном случае клетку оставляем пустой. 3. Определяем покрытие столбцов строками. Каждое покрытие порождает раскраску.
Покрытие минимальной мощности определяет хроматическое число (хроматический класс) графа С. В случае большого графа С = (У, Щ, когда мощность его носителя равна нескольким сотням и тысячам вершин, рассмотрим следующий алгоритм [39), использующий частотные свойства графа. 1. Производя ~Ц сравнений, определяем пару смежных вершин и и ир графа С = (У, с>'), пля которого функционал (3.24) принимает максимальное значение.
Равенство зтого функционала нулю означает, что ребро (о, ир) не входит в треугольник, и чем больше значение (3.24) > тем в педграф большей плотности зто ребро может входить 2. Найденную пару вершин раскрашиваем, и им взаимно однозначно сопоставляем столбцы в двумерной таблице, строкам которой взаимно однозначно сопоставляем вершины, смежные хотя бы с одной раскрашенной вершиной; в клетке (з, у) ставим 1, если з-я и 1'-я вершины смежны, и О в противном случае. 3. Выбираем строку с максимальным числом единиц.
4. Если для выделенной в п. 3 з-строки найдется у-й столбец, на пересечении с которым находится О, то соответствующую з-ю вершину раскрасим в 7-ю краску и произведем склеивание соцветных по у'-й краске вершин. В противном случае з-ю вершину раскрасим в новую краску, увеличивая количество столбцов в таблице на 1. б. Если осталась хотя бы одна неокрашенная вершина, то переходим к п. 3, в противном случае — к и. 6. 6. Конец. Число красок при раскраске вершин графа С = (У, (>') равно количеству столбцов в итоговой таблице. Пример З.И. Рескрасим вершины графе С = (У, с>') (рис.
3.43,а), используя рассмотренный алгоритм. Рис. 3.43 33.8. Кеазиполные модели, ик сшрркоьрра и саоасгяеа 217 216 Гл.з. Теории графов и мографое 1, 2. Максимальное аиачеиие фуикцшшала ее((о, ое)) согласно (3 24) равно О, 25 при рассмотрении вершин 1 и 4: шат р((о«, ое)) ю О, 25, о« = 1, ое = 4. «,а Получаем табл. 3.5. 3.
Выбираем первую строку. 4. Раскрашиваем вершину 2 в новую краску, в реаультате получаем новую табл. 3.6. 5. неокрашенные вершннм имеютог, следовательно, переходим к п. 3. 3. Выбираем первую строку. 4. Вершина 3, соответствуюшая первой строке, сопветна вершние 1; раскрашиваем вершину 3 и склеиваем ее с вершиной 1. Получаем табл. 3.7. Таблица 3.5 Таблица З.б Таблица 3.7 Выполняя этот алгоритм послеповательио, получаем табл. 3.8-3.10. Таблица 3.8 Таблика 3.9 Таблица 3.10 Окоичательнополученараскраска неполного графа С ю (1г, 11) в три краски (рис. ЗАЗ, 6): а = (1, 3, 6, 8), Ь = (4, 7), с ю (2, 5).
Плотность графа С равна 3. Слеловательио, полученная расвраска является минимальной. 3 3.8. Кввзиполиые модели, их структура и свойства Будем рассматривать модели Ф со свойством симметричности Ф=(М 51,52," Яо), 51СМ', (сс1,2,...,П, т. е. каждое ребро модели представляет собой подмножество множества М. В дальнейшем ребро будем называть словом, элемент носителя М вЂ” буквой. Подмоделью Ф' модели Ф называется модель Ф', полученная из молели Ф вычеркиванием хотя бы одной буквы из слова, Ф' СС Ф.
Раскраской В(Ф) модели Ф называется такое разбиение ее носителя, что ни одна из пар букв, входящих в слово, не принадлежит подмножеству этого разбиения. Обозначим множество красок минимальной мощности при рас- краске модели Ф через К(Ф): К(Ф) = (м;/ т = 1, 2, ..., Ц, а раскраску — через В„„„(Ф). Квазиполкой моделью Фч(«) называется модель, в которой при Вано(Фч) необходимо «красок, ~К(Фее) ~ = «, а при Вюьч(Ф'), Ф' СС Фм, достаточно «' красок, «' < «. Числа «(ФО) при этом называется квазиплоткостью квазиполкой модели Фм. Квазиплоткостью «(Ф) модели Ф называется число «(Ф) = шахйп(Ф1 ), гле Ф~~ С Ф лля любого е.
, Плотностью р(Ф) модели Ф = (М, 81, Я2, ..., Я ) называ- ется число р(Ф) = шаха;, 1 гле г; — степень словесного отношения Я1 (т = 1, 2, ..., т). Порядком (с(Ф) модели называется число ИФ) = «(Ф) -р(Ф). Очевидно, что к(Ф) > О. Модель Ф квазиплотности «обозначим Ф(«). Модель Ф плотно- сти р и порядка (с обозначим Ф(р, й). Краску Ж„сопоставленную бУквам тп, тап..., том обозначим 11(е(тт„т12, ..., тп;„). Частным случаем квазиполных моделей является квазиполный граф.
Квазиполкым графом ь,((«) называется граф (,1, лля минималь- ной раскраски которого необходимо «квасок, а при раскраске лю- бого собственного частичного графа Я, Я' СС Я, достаточно «' красок, «' < «. Число красок «при этом называется квазиплогп- костью квазиполкого графа Я. Квазиплотность «(б) графа С определяется выражением «(сг) = шах«;(Щ, © С сг.
(3.26) Порядок (сф) квазиполного графа Я(«) есть "((г) = «((г) — р((е). (3.26) Порядок (с((') графа С есть ~(а) = «(а) — р(с). (3.27) Условимся квазиполный граф Я плотности р и порядка (с обо- значать (~(р, (с), а граф с такими же характеристиками — С(р, к). Гл. 3, Теория грифов и могрвфоа 218 р.Пр.=р.
>иа ~ > >сна — >>иа > Квазиполные графы Я(2, 0), ьг(2, 1), Я(2, 2) и Я(2, 3) изображены на рис. 3.44. Рис. 3.44 Теорема 3.42 (основноесвойствоквазиполныхмаделей). Для любой буквы пь квазиполной модели Ф>3(й) = ~М> Яь > Ят> ...> Я,„) сущесптвует минимальная раскраска В;„(Ф ), при которой не найдетпся буквы тн Е М, не равной тп (тп ф тп ) и имеющей пту гке краску, чтпо и пь.
Доказательство. Пусть для произвольной буквы тп Е М (Фч(д) = (М, Ям Ят, ..., Я )) не существует такой минимальной раскраски В;„(Ф63(д)), т. е. при каждой минимальной раскраске В„;„,(Ф>3) найдется хотя бы одна буква тпа Е М, тн ф пьа> имеющая ту же краску, что и тп. Но тогда после удаления тп, из Ф>3 получаем выражение ~К(Ф'с) ~ = а, что противоречит определению квазиполной модели Ф'е (д). Следствие. При вычеркивании любой буквы из любого злеменпта квазиполной модели Фф(д) ее квазиплопьноспть уменьшаептся ровно на 1.
Примечание. В дальнейшем для сокращения записи формулировок лемм и определений будем записывать их на языке логики предикатов. Например, теорема 3.42 на языке логики предикатов запишется в виде (>ттп)(тп Е М(Ф (Ч) = (М> Яг> Ят» ° ° Яс>))) (ЗВааа(Фч))((Ъи„)(пь,„б М)), (тп ~ пьа) 36 1У(пь> тпо)). (3.28) $3.8.
Квазилолные модели, их си>руки>ура и свойсп>ва 219 Для изучения структуры и свойств квазиполных моделей введем алгебру Аь вида Аь = (М, П, О, '1), носителем М которой является множество слов, сигнатурой — операции алгебры Кантора: П вЂ” пересечение, 0 — объединение, 1 — разность. Каждое слово р при теоретико-графовом представлении модели Ф соответствует полному подграфу плотности, равной ~р~.
Элементом носителя этой алгебры является модель Ф = (М, Яы Ят, ..., Я„), опрепеляюшая множество подмножеств множества М, которая является 'дистрибутивной решеткой; для нее справедливы свойства идемиотентности и поглощения с>ьа П (Ра » >иь) = Ра» >иа >.т (>ба П~ Рь) = Ра.
Элементами модели Ф„Ф, = Фь о Ф„где о обозначает одну из операпий О, П, ~, являются полные подграфы, принадлежащие , графу Са(фа) > Са(Фа) = Сь(Фь) с> Сс(Фс). Проиллюстрируем введенные операции над моделями: Фь = ((а, х), (х, р), (р, о), (тн, о), (пь, а)), Ф, = ((х, о, р), (тп, о, х)), Ф = ФЬ Г1 Фс = ((Х, Р), (Р, О), (Пь, О)), Фа = Фь 0 Фс = ((х> о, р)> (тп, о, х), (тп> а, х)) > Ф, = Фь 1 Ф, = На, х), (тп, а) ).
Из определения раскраски модели Ф очевидно, что число кра- сок определяется только топологией соответствующего ей мографа СМ(Ф) а порядок модели — как топологией, так и распределением > М идентификаторов слов, взвешивающих вершины мографа С (Ф), а точнее — максимальной степенью словесного отношения. Ис- ходя из этого при определении числа красок (в пределе — хрома> М тического числа модели Ф) будем рассматривать мограф С (Ф) без учета моделизации, т. е. без учета идентификаторов слов, взве- шивающих соответствующие вершины мографа С (Ф). м Вершина о,', о,' ф СМ(Ф>3)> называется замещающей вершину о;, и< Е СМ(Ф'с), если их сечения равны друг другу: Г(щ) = Г(о,'). Подграф С';, С'; = (~', Ц), С'; (с СМ(Ф>с), называется заме- щающим подграф Сп С; = (К, Ц), С; С С~(Ф>3), если суще- ствует изоморфизм ту между их носителями 1ть ~+ $~, при котором Г(о;) = Г(и,'), о; Е У> и,' Е $т6, и; = т1(о,').
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
