Введение в прикладную комбинаторику, Кофман А. (984071), страница 25
Текст из файла (страница 25)
(30.6) г ~, 1 а Рис. 122. Рис. 121. Это можно записать так; или Беря произведение по всем вершинам графа, получаем уравнение Фа= П П(ацар -(-х1.+х)) 1"*). (30,9) )ть ~ Учитывая, что 8 Д Г 18 = Я, упростим эту формулу: Фз = Ц П (ае)+ х1 + х)) 1 (30.10) или е) Здесь и далее имеется в виду неисключающее «или», (Прин. ред.) '") П обозначает здесь и далее булево произведение (каждый член учи. тывается один раз). (Прим. перев.) 181 А 'т если Х)ен ГХ;, 1~1, то а~) — — 1; если Х) йй ГХо )Ф(, то а~) — — О. А \ \ ту '~ т е и н 1 М 1, (а~)+ а(Д -1- х~ + х) = 1 (30.7) 1Ф!, а~)а)~+ хе+ х) —— 1.
(30.8) Фз = П [х~ + Ц (а11+ х))1 1. (30.11) т 1т с В (30.11) раскроем скобки и приведем подобные члены, учитывая, что а +аЬ = а. Тогда для каждого члена совокупность всех вершин, соответствуюших переменным, отсутствуюшим в нем, дает максимальное внутренне устойчивое подмножество графа. Действительно, такой член содержит лишь переменные с отрицанием и поэтому к множеству вершин Хь соответствующих переменным хь не встречающимся в этом члене, нельзя добавить никакой другой. П р и м е р. Рассмотрим булеву матрицу (рнс, 123) графа на рис. 120.
Найдем А В с Р и к с и аив+ а+ ало+ а+ Ь=а+Ь, С=1, ало -+ а + Й = 1, але+а+е=а+е, 1=а+1, у=1, але+ а+ ало+ а+ (30.12) ахи+а+6=1, Риа 123. или Фз = Ьес1Й + аЬЙЯ + аЬсзн Б -+ аЬепЯ + + асей + ассЦЬ + ИеЦ + аедейй = 1. (30.15) Таким образом, граф обладает восемью максимальными внутренне устойчивыми подмножествами: (А, С, О, 6), (С, Е, Н), (С, Е, О), (С, В, Р), (В, Е, Н), (В, Е, 0], (А, С, Н), (В, Р). (30.16) Внешне устойчивое подмножество.
Пусть задан граф 6=(Е, Г), Подмножество Тс: Е называется внешне устойчивым, если (вХ~ Ф Т) Т Д ГХсФ О, (30.17) 182 Подставим в (30.10): Фз=(а+ Ь) (а+ е)(а +1) (Ь+ с)(Ь+ с() (с)+ е) Х ><(е+Р) У+ й)(д+ Б)(Ь+е))(Б+7) =1. (30А3) Упрощая, получаем Фз — — (а.+ Ье1) (Ь+- сс))(с(+ е)(е.+1) К Х (7' + д) (и + й) (й -+ 4) = 1, (30.14) т.
е. любая вершина Х„не принадлежащая Т, связана по крайней мере с одной вершиной из Т дугой, начало которой лежит в Š— Т. Можно записать (30.17) также в следующем виде: (ЧХс ~ Е) [(Хе) () ГХД П Т чь Я (30.18) П р и м е р (рис. 124). Подмножество ) С, О, Е, Р, Н) внешне устойчивое, что легко проверяется с помощью (30.17): Т=)С, О, Е, Р, Н), ГА=(В, Е, Р), ГВ=(А, С, О), ГО=(Н), ТЯГА=(Е, Р)МЯ, ТПГВ=(С, О)~Я, ТПГО=)Н)~Я, (30.19) или с помощью (30.18): ((А)()ГА)ПТ=(А, В, Е, Р)ПТ=)Е, Р)~Я, ()В) () ГВ) П Т = ) А, В, С, О) П Т = (С, О) Ф Я, ()С) () ГС) Д Т = )С) Д Т = (С) Ф Я, ((О) () ГО) П Т = ) О, Е) Д Т = (О, Е) чь Я, ((Е)() ГЕ)ДТ=)0, Е, Р) ПТ=(0, Е, Р)ФЯ, ()Р) Д ГР) й Т = )Е, Р, 6) Д Т =)Е, Р) М Я, ()а)()ГО)ПТ=)а, Н)ПТ=)Н) Я, ((Н)()ГН)ДТ=(0, Р, Н)ДТ=)0, Р, Н)~Я.
Очевидно, что если Т с: Т' с Е, то Т' — внешне устойчивое подмножество; и любая висячая ') вершина принадлежит каждому внешне устойчивому подмножеству. и д Рис. 124. Рнс. 12о. Минимальное внешне устойчивое подмножество. Это — внешне устойчивое подмножество, не содержащее строго никакого другого внешне устойчивого подмножества.
~) Вершина Х; висячая, если ГХ~ = Ы. 11а рис. 124 таковой является вершина С. 1ВЗ где 9 — семейство внешне устойчивых подмножеств графа О. Например, для графа на рис. 125 р(6) = 3. Отыскание семейства минимальных внешне устойчивых подмножеств (метод Магу)' ).
Из условия (30.18) следует, что такое подмножество Т должно содержать вместе с Х, по крайней мере одну из вершин ГХь Следовательно, справедливо условие (»»Х» яЕ)(Х, ен Т или (ЗХ») (Х»ен Т и Х»еи ГХ»)). (30.22) Полагая х» =1, если Х, еи Т и ап — — 1 (ан определено выше), имеем П(х, +. ~» а»»х») =1. » (30.23) Так как (»»х») х» + ~ амх» — — ~ аахм » ' I (30.24) то »»»т= П Ха»»х» — — 1.
(30.25) / Учитывая, что а+аЬ = а, разложим (30.25). Каждый член этого разложения дает минимальное внешне устойчивое подмно- жество. Действительно, такой член не содержит переменных с отрицанием, и поэтому из множества вершин Хь соответствую- щим переменным хь встречающихся в этом члене, нельзя уда- лить ни одну. Пример (рис. 120 и 123). Так как адза + ахвЬ+ алве+ ахр) = а+ Ь+ е+ 1', авва + а в в Ь + овсе + авв»1 = а + Ь + с +»(, ассе = е, арр»1 -1- авве = »» + е, авр»(+ авве.(- авД= »(+е+», арве (-аррг+ арод=е+ ~(-й», аоай+ аонЬ = й + Ь, анв»1 -1- анр» + аннЬ = »1 +»' -1- Ь, (3026) то в силу (30.25) Фт —— (а + Ь+ е+ )) (а + Ь 1- с + д) с (»(+ е) (»(+ е 1- ») Х Х (е + 1+ д) (д.+- Ь) (»1 + ) + Ь) = 1.
(30.27) ') См, сноску ка стр. 180, 184 Например, для графа на рис. 125 подмножество (С, Е, Н) внешне устойчивое и минимальное. Граф может обладать несколькими минимальными внешне устойчивыми подмножествами. Число внешней устойчивости. Это число вершин наименьшего нз внешне устойчивых подмножеств. Оно определяется так: 5(6) =пи'и ~ Т» ), (30.21) т» в Таким образом, граф обладает семью минимальными внешне устойчивыми подмножествами: (С, Е,Н), (А, С, Р, 6), (С, О, Е, 6), (С, Р, Р, 6), (С, О, Р, Н), (С, Е, Р, 6), (В, С, О, 6). (30 30) УПРАЖНЕНИЯ ЗОА. По методу Магу выписать нсе максимальные внутренне устойчивые подмножества и аычислнть сг(В) для графов: 1 д д 4 6 6 7 8 Е В с) ! 2 д 4 5 6 7 6 ,е') ГА = (В, О, Р), ГВ = (С), ГС=(В, Р), ГВ = (Е), ГЕ = (А, О, Р), ГР (В1. г) !85 Упрощая, имеем 0тт = (а + Ь + е (- () с (г(+ е) (е 1- ) .
(- д) (Аг +. Ь) (И + ) + Ь) = 1, (30.28) или гРт = сей+ асг)д+ сс(еп+ сс()д+ саг)й + се~к+ Ьсг1д = 1. (30.29) ЗВБ. По методу Кагу выписать все минимальные внешне устойчивые подмножества и вычислить р(0) для графов: 1 и 3 4 5 б 1 й 3 4 5 1 б) 5 31. Ядра графа (31.1) (31.2) Отсюда следует, что ядро содержит всякую вершину Х; с ГХ; = 8 и не содержит вершин с петлями. Очевидно, что 8 не есть ядро графа. Граф может обладать несколькими ядрами или вообще не иметь ядра. Например, подмножество (А, С, 6, 6) — ядро графа на рис.
!26, а (С, Е, Н) — ядро графа на рис. 127. Отыскание ядер графа. Метод Магу ').Полагаем хг = 1, если Х; ~ 1Ч, и рассмотрим уравнения Фз = 1 и Фт = 1 из (30!1) и (30.25) соответственно, Так как эти равенства должны выполняться, то лэи = гРЛт =- 1 (3 1.3) ') См, сноску па стр, !80. Бслн граф обладает петлями, то можно рас. смотреть соответствующий граф беа петель. Пусть задан граф 6 = (Е, Г). Подмножество М с: Е называется ядром графа 6, если й) — одновременно внутренне и внешне устойчивое множество, т. е.
(ьтгХг ен й)) й) Й ГХг = Я, (ЧХ, Ф й)) й) () ГХ; Ф а. т. е. (П (х~ .+ П (а Н + хт)1 ) (П Х а;,х,) = 1 (31.4) или Ц ~х~ ~х'.~ ацх1+ х~ Ц(а~1+- хт)~ = 1, (31 5) [ 1 1 ем Пример (рис. 120). Для этого графа Ф, и Фт вычислены ранее (см, (30.15) и (30.29)). Итак, находим а (а + Ь + е + () + а (Ье1 ) = а (Ь + е + Т) + а (Ье(), Ь (а + Ь (- с + й) + Ь (а ей) = Ь (а + с + й) + Ь (асс(), (31.6) т ч ,А й', ! Ф ',С С Рис.
127. Рис. 128. (замечая, что х,х, =О); ФзФт — — аЬ сйе1йй +- аЬсйе~йй = 1. (31.7) Итак, граф обладает двумя ядрами: Х, = (А, С, Р, 6) и Ь(з = (С, Е, Н). (31,8) Свойства ядер графа. Эти свойства будем рассматривать в виде теорем. Т е о р е м а 1. Пусть задан граф 6 = (Е, Г). Ядро Ы графа 6 есть максимальное внутренне устойчивое подмножество.
Предположим, что Ь( — собственное подмножество максимального внутренне устойчивого множества А. Тогда существует вершина Х; ен А и Х; Ф Ь(. Следовательно, Ь(() ГХ;~8 и АДГХ;ФО. Отсюда следует, что А не является внутренне устойчивым подмножеством, вопреки предположению. Итак, М совпадает с А. Т е о р е м а 1?. Пусть задан симметрический граф 6 = (Е, Г) без петель. Тогда любое максимальное внутренне устойчивое подмножество является ядром 6. Рассмотрим максимальное внутренне устойчивое подмножество Ьм. Требуется показать, что для произвольной вершины 187 Х; ф Ьм справедливо соотношение Бм П ГХ! Ф О.
Предположим противное. Тогда множество А = Ьм () (Х!) внутренне устойчивое, так как Х! ф ГХь что противоречит максимальности $м. Теорем а И1. Пусть задан граф 6 = (Е, Г) без петель. Для того чтобы подмножество й( было ядром, необходимо и достаточно, чтобь! оно было одновременно максимальнь!м внутренне устойчивым и минимальным внешне устойчивым. Пусть граф имеет ядро.
Как мы видели раньше (см. (3!.3)), условие ФзФт = 1 (31.9) необходимо, чтобы граф допускал ядро. Первая из этих функций представляет собой сумму одночленов только от переменных с отрицанием, а вторая — только от переменных без отрицания. .' г Х' ' Пусть Фз и Фт — некоторые Ы1 1И одночлены из Фз и Фт соответственно. Если выполнено (31.9), д то ! р !' г ! г Ю I !У ! ! ! ! ! ° ! ! ! 1 Ъ ! ! Ъ \ ь Ъ с ! (31.11) Это следует из определения ядра. Теорема Ч.
Если граф 6 =- (Е, Г) допускает функцию Гранди д(Х), то подмножество (Х; !д(Х!) = О) (31.!2) — ядро графа. В самом деле, вершины, для которых д(Х!) = О, удовлетворяют условиям (30.!) и (30.17). Например, подмножество (В, 6, У, К) — ядро графа на рис. 128 (функция Гранди этого графа построена ранее (см. рис. 115)). 188 !Фз"'|+!Фт" 1=! Е !. (31.!О) Р Следовательно, ядро, для которого Ф1з"1Фттм =1,— одновремен но максимальное внутренне устойчивое и минимальное внешне устойчивое подмножество. Обратно, пусть задано под- множество, являющееся одноРис. 128. временно максимальным внутрен- не устойчивым и минимальным внешне устойчивым.
Тогда для соответствующих переменных, связанных с его элементами, выполняется соотношение Ф1з"'Фтт"! = 1, т. е. это подмножество — ядро графа. Теорем а 1Ч. Для ядра й) графа 6 = (Е, Г) выполняется неравенство ()(6) (~! г!) (~а(6). Теорема И. Симметрический граф без петель всегда допускает ядро. Это — следствие теоремы П. Т е о р е м а ЧП. Рассмотоилг булеву функцию на множестве А: О , если Х, ф А, Р(А, Хг)= 1, если Х; ен А. (31.13) Условие Р(А, Х;) =1 — гпах Р(А, Х ) х «-гх, (31.! 4) деле, если А — ядро, то Необходимость.
В самом в сичу внутренней устойчивости (Р(А, Х;)=1)=)ь(Хг ~А)Ф( гпах Р(А, Хг)=0), (31.16) х гх, а в силу внешней устойчивости (Р(А, Хг)=0)~(Хг ФА)=>( шах Р(А, Хг) =1), (31.17) х гх, т. е. имеем (31.14). Достаточность. Действительно, из (31.14) для А имеем (Хг ев А) =>(Р(А, Хг) =1) >( гпах Р(А, Х ) =0)=> х ~гхг =Ф А Д ГХг = — Я, (31.18) (Х, Ф А) Ф(Р(А, Хг) =0)=,='>( гпах Р(А, Хг) =1) =)ь х гх, Ф А Й ГХ; чь О, (31.19) т. е.
А — ядро. Теорема может быть также доказана с помощью метода Магу для нахождения ядер. Теорема гГП1, Граф без контуров всегда обладает ядром. Для такого графа существует порядковая функция, а значит, функция Гранди н, следовательно, ядро (теорема гг). Теор е м а 1Х (Ричардсон).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
