Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 40
Текст из файла (страница 40)
18,8. Квазиполкые модели, ик стпруктау а и своастпва 221 Гл.3. Теорил графов и мов афов 220 Факт замещения будем записывать в виде С; '= Б(С;). Замещающим слоем Б(Фсв) квазиполной модели Фсв = (М, Яд, Ят, Яз, ..., Я„) называется объединение (,с Б(Ф;) замещающих подс графов Б(Ф;), при котором носители подграфов См(фд), См(фс) = = (М;, Ц), образуют разбиение носителя М модели Фсс: д..с М; = М, (У;.л;,дв, дд)(М;. с д Мд, = сст). При предельном рассмотрении квазиполная модель Фсв .н ее замешающий слой Б(Фч) могут совпадать: Фсв = Б(Фсе).
Теорема 3.43. (1тЛ д„(Ф0(д) с.с Б(Фсд(д))(Б(Ф0(д)) = (М, Зд, Я, ...,,д )))), (дуФ; Е К(Ф~(д))), (Ьв Е М)(Ж(т) = ддт;). (3.29) Доказательство получаем, основываясь на определениях опера- ций над моделями квазиполной модели. Содержательно замешаюшнй слой Б(Фсд(д)) своими буквами "замещает" все буквы модели Фсв(д), имеющие различные краски при любой минимальной раскраске В „; "замещает" в том смы- СЛЕ, Чта Каждая КраСКа Прн Лвбай Вы;„(ФСЗ(д) СС Б(Ф0(д))) Саат- ветствует как букве т Е Фч(д), так и букве тд Е Б(Фсв(д)), т.
е. при любой минимальной раскраске Фч(д) дс Б(Фч(д)) имеется д различных пар букв (т„, тпр) таких, что „. б Фд(д),, б Б(ФО(д)), У(т ) = М(тр) = Ид(тп, тдт), т = 1, 2, ..., д. В дальнейшем буквы, окрашенные одной и той же краской, при минимальной раскраске будем называть соиеетяыми. Замыкающим замещающий слой Б(Ф0(д)) слоем й(Б(Фс2(д))) называется совокупность вершин Ъсдд, обладающая следующими свойствами: 0 Г(и;) = У(Б(Фс2(д))), и; Е й(Б(Ф (д))), (сб)(а(о;) ) д), (3.30) в(и;) — степень вершины и;; т'(Б(Фьс®Ц — носитель гамешадс- шего слоя; при минимальной раскраске вершин Ьсдд необходимо д + 1 красок, а при удалении хотя бы одного ребра (и, идт), и Е Е тт(Б(Фсе(д))), идт Е 1тдд, достаточно д красок.
Для иллюстрации (3.30) построим замещающий Б(Фсв(3)) и замыкающий слои й(Б(Фсс(3))) для квазиполного графа Фсд(3): Фст(3) = ((а, Ь, с, Н, е); ((а, Ь), (Ь, с), (с, Н), (Н, е), (а, е))), Б(Ф0(3)) = ((а, Ьс, сс, сд~, ес, а, Ь, с, сд, е); ((а', е), (а', Ь), (а, Ь'), (Ь', с), (Ь, с ), (сс, И), (с, Н'), (сд', е), (а', е), (Н, е'))), й(Б(Фсд(3))) = ((т' ас Ьс сс И~ е ((а', Л, (Ь', Л, ( ', Л, И', Л, (е', Л)). Построенный замыкающий слой имеет минимальную мощность (добавилась одна буква — вершина) у; будем говорить, что вершина у кояусируетп вершины замещаюшего слоя. Максимальная мощность этого слоя будет равна числу сочетаний из множества букв в замешающем слое (а', Ь', У, с', е') по д элементов, д = 3.
В нашем случае имеем (з) = 10, в замыкающем слое добавятся (Ь/ д = 1, 2, ..., 10), и он будет иметь следующий вид: й(Б(Фсс(3))) = ((Лс Ь,, Ло, а', Ь', с', с1с, е'); ((Л, а) (Л, Ь') (Л, с'), (Ь а'), (Ь Ь') (Ь сЦ Узс а'), Уз, Ь') с Уз, с'), (Ьс а') (Ьс с'), (Ь, ~')с (Ь, а'), (Ьс с')с ЕЬ, Е), (Ь, а'), Ивс г) с (Ьс е'), У7\ Ь )с Утс с'), (Iч, с~') (Ув Ь ) Ув с') (се, е')! (Ь, Ь'), Ие, И'), (Ь е') (Ло, С), (Ло, с1')с (Ло, е')))- Граф с минимальной мощностью замыкающего слоя представлен на рис. 3.44, а, с максимальной мощностью — на рис. 3.45. Рис.
Зла Гл.з. Теория графов и маграфав Теорема 3.44. Ф = Фд(д+1) н Ф = Фс1(д) 0Е(Фе1(д)) 0Й(Б(Фд(д))). (3.31) Доказательство. Необходимость. Дано: Ф = Фй(д+ 1). Требуется доказать, что Ф = Фч(д) ЩФЧ (д)) Ой(Б(Ф'2(д))). Для доказательства (3.31) необходимо показать, что: а) Ф = Фч(д+1) ЭЭ Фч(д); б) Ф = Ф'(д+ 1) ~~ =-(Ф'(д)); в) Ф = Фч(д+ 1) ЭЭ й(Б(ФсУ(д))); г) Ф"с(д+ 1) ~ (ФС1(д) и Е(Ф 1(д)) О й(=(ФС1(д))) = а.
Докажем а)-г) по очереди. а) Предварительно заметим очевидное утверждение, что при вычеркивании одной буквы из модели Ф число красок (К(Ф)( максимально может уменьшиться только на 1. Вычеркиваем произвольную букву яь, в одном из элементов (слов) ьг, из Ф'г(д+ 1); тогда согласно определению квазиполной модели и вышеприведенному утверждению имеем д((Ф. = Ф~(д+1)) ~ Ф (Ф = И. ~ .)) = д. Вычеркиваем в оставшейся модели Ф,(д) еше одну произвольную букву ть из любого элемента ась' тогда д((Фь = Фв ~ ФР(ФР = Иь)) 0 Ьь ~ гяь)) равняется д — 1 либо д. Если д(Фь) = д-1, то букву яьь снова приписываем к элементу ць и ее отмечаем. Если д(Фь) = д, то букву не приписываем к ась.
Продолжаем этот процесс, т.'е. вычеркиваем в оставшейся модели произвольную неотмеченную букву из любого элемента. Если при этом квазиплотность равна д, то букву не приписываем, и так далее до тех пор, пока все оставшиеся буквы не будут отмечены. Полученная модель и есть Ф'е(д); действительно, ее квавиплотность равна д, а при вычеркивании любой буквы равна д — 1, так как все буквы отмечены. б), в) Согласно определению квазиполной модели ~К(Фч(д+ +1))~ = д+ 1, и чтобы это равенство было выполнено, очевидно, необходимо, чтобы при любой В;„(Фс1(д+ 1)) существовала буква ш, которая была бы смежна с д буквами (входила с ними в слово), среди которых нет хотя бы двух соцветных букв пь, и гоь (пьв ~ яьь); в противном случае (ФО(д+1)) ~ д+1 13 8. Кваеипалиме модели, их сюруитиу а и своосоьва 223 Если эти д букв при любой минимальной раскраске принадле- жат одной и той же модели хипа Ф'е(д), то буквы типа ш, обра- зующие множество М, во-первых, таковы, что ('Ульи б Ми)(пью ~ М(Ф (д) = (М, ~1, Яю ", Ящ))), так как противное утверждение противоречило бы определению квазиполной модели; во-вторых, ФФ(д) можно рассматривать в качестве Н(Ф'е(д)) по определению замещаюшей модели и выше- приведенному утверждению (в начале б), в)) Ф (Ф = (М, Я „ Я,г, ..., Я )) образует замыкающий слой Й(Е(Ф'2(д))) согласно (3.30).
Если д букв рассмотренного типа принадлежат различным мо- делям типа Фч(д), которые, кстати, могут быть выделены с ис- пользованием процедуры, приведенной в а), то согласно (3.28) и определению Фч(д+ 1) среди квазиполиых моделей квазиплотно- сти д существует модель Фо (д) = (Мо Яо„Яо„, ° Яо ) такая, 9 что Рпьи б Мо)((Фо = (Мо до~ 'дог1 ' 'до )) 8с(Фо С Фо (д))) ((~Ф(Ф =Я(Ф;)ЮФ;), ИФ =Ф.)- ( ...) Фа.))), так как в противном случае согласно (3.28) РВвие(Фо (д))) (~Ятоо)((год б Мо) бс (та гЕ пьр) ЙФ(пьс год))) и У(гя ) = Ж(гя ) = М(гя, гя,„) и д(Ф~Ь(д+ 1)) = д, что проти- воречит заданию.
Следовательно, согласно определениям замещающего и замы- кающего слоев имеем Е(Фи(д), Й(Б(Ф'г(д))), и при любом Ввц (Фи(д) 0 Е(Ф~(д)) 0 й(Б(Ф'в(д))) необходимо д+ 1 красок. г) Фз(д+ 1) ~ ФФ(д) 0 Е(Фсг(д)) 0 й(Б(Ф'у(д))) = Я справед- ливо, так как в противном случае после вычеркивания хотя бы одной произвольной буквы, входящей в любой элемент разности, минимальное число красок равнялось бы д+1 согласно доказатель- ству б), в), но это противоречит определению квазиполной модели квазиплотности д+ 1, которая задана. Достаточность Дано: Ф = Фс1(д) ц Н(Ф'1(д)) и й(=(Ч4(д))), Требуется доказать, что Ф = Ф~1(д+ 1).
Согласно определениям замещающего и замыкающего слоев и определению квазиполной модели имеем ~К(Ф)~ = д+ 1, т. е. Ф = Ф(д+ ц, Ф = Фс1(д) о Н(Феу(д)) о й(Н(Ф'2(дН). Покажем, что теперь Ф(д+ 1) = Ф~(д+ 1). Гл. 3. Теории графов и моердфов 224 д» д с Рис. 3.4б б Е. Ь Горба»» Это справедливо, так как нельзя вычеркнуть ни одной буквы та, из какого-нибудь элемента ..
= Ф'. С Ф0(д), =-(Фр(д)), а(=-(ФЯ(д))), так, чтобы квазиплотность осталась равной д+ 1. Действительно, если мы вычеркиваем тна б Зб (тба Е Ф'б(д)), то согласно (3.28) для В тв((ФФ(д)~Фе)0(р '1тн)) достаточно д — 1 Краеаи, И Прн Вопд(зб(Е(фбб(д)))) ПОтрЕбуЕтея данапинтЕЛЬНЫй д-й порядковый номер н д(Ф) = д, что несправедливо, так как д(Ф) = = д+1. Аналогично показывается справедливость этого утверждения ттрн ™а Е»»ба(»аа = Фа» Ра С (Ф (д))» Зт'( (Ф (д))))' Для иллюстрации (3.31) рассмотрим увеличение квазиплотности на 1, взяв в качестве основания квазиполный граф Я(3) (рис.
3.46,а). Замещающий слой Б(фЗ)) и замыкающий слой Й(БЯ(3))) представлены на рис. 3.46, б, е соответственно, результат Я(3) 0 Б(Я(3)) 0 й(Е(Я(3))) = Я(4) — на рис. 3 46 г. Рассмотрим некоторые свойства, характеризующие структуру квазиполных моделей. 13.8. Квозиполные модели, их еотрунотурв и свобсотвд 225 Согласно (3.31) для квазнполных моделей справедливо свой- ство енлюиаемостни Ф (Р,К) ЭФ (т,у), в=2,3,...,р, т'=0,1,..ай.
(3.32) Проиллюстрируем это свойство рассмотрением квазиполной мо- дели Я(3, 2) (см. рис. 3.46, г). Для этой модели имеем Я(3,2) ЭЗ Я(3, 1) ЭЭ Я(3, О), Я(3,2) ЭЭ Я(2, 2) ЭЭ Я(2, 1) ЭЗ ф2, О), Я(З, 1) ЭЭ ((а, Ь), (Ь, у), (а, у), (Ь, с), (с, у), (с, Ц, (бт', У), (б1, е), (е, т'), (а, е)), Я(3, О) Э.л ((а, Ь), (Ь, т), (а, т)), Щ2, 2) = На, Ь), (Ь, с), (с, И), (Ы, е), (а, е), (а', Ь), (а', е), (а, Ь~), (Ь', с), (Ь, сс), (с~, Ы), (с, б1'), (Н', е), (Ы, е~), (а, е ), (а, Д, (Ь,т'), (с,т'), (Ы,,т'), (е, Я, Я(2, 1) = ((а, Ь), (Ь, с), (с, бб), (И, е), (а, е)), Я(2, О) = (а, Ь). При одной и той же структуре замещаюшего и закрывающего ч9зт,~м.~-з чфзт,щ~-з чейз+0,1м.~-б ч)ттз+в,~мр-б порот = ч»о ~м ~ = т Рис. 3,47 слоев согласно (3.28) н (3.31) для квазиполных моделей имеет место свойство монотонности (М.'(Ф~(д) = (М.', Я.'„Я.'„..., Я,',)) ~ > > ~Мт(ФЯ( ) = (Мт, ~т„~т„..
а ~т,)) ~ 4-т (М (Ф~~(д+ 1) = (М, Я „Я „..., Я„)) ~ > > (М,(Ффд+ 1) = (и,, З,„Я „..., Я,,)) ~. (З.ЗЗ) Пронллюстрируем выражение (3.33) на рнс. 3.47. Гл.3. Теория графов и маграфов 226 Г)Я(зза(4))) х,(2, , 4,5) х)(з, 6) Хз(5) Х (4) (3. 5) Х)( хз(6) х)(5, 6) Рис. 3,49 Рис. Зла Рис. 5.50 При рассмотрении замещаюшего и замыкающего слоев как результата применения операции соответственно замещения Б и замыкания Й над квазиполной моделью Ф(2(д) нетрудно показать свойства идемпотентности операции замещения К(Б(Б...(Б(Ф()(д))...))) = К(Б(Ф9(9))) (3.34) и отсутствие такого у операции замыкания Й.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
