В.Н. Нефедов, В.А. Осипова - Курс дискретной математики (1127083), страница 50
Текст из файла (страница 50)
Вмутренняв устойчивость в неориентярованиых графвх Внутренне устойчнвыс множества вершин аналогично можно определить и ддя неориентированного графа С (К Х), а имшшо: множества С ш У вазывзетсн внутренне устойчивым, если Чюшб СПС[ю)=а, т. к никакие дзе шршгшы из С не «вляютсв смежными. Нструд. во внпюгь, что еслн графу б ([', Х) псстапить в соответствие орграф с множеством вершин У, эаиснни иаждое ребро (о, ю) графа б на лве д)тн (с. и). (ш. с), то в получземаи таким оф разом арграфс О совокупность внутренне усюйчнвык множеств вершин июпздаст с совокупностью внутренне устойчивых множеств вершин графа б, поскольку в этом случае Чош У б(ю) = Р[с).
Нс тогда и совокупность максимальных внутренне устойчивы» множеств вершин грифа б совпакаст с совокупностью максвмальных внутренне устойчивых множеств вершки орграфа О, а следовательно, для их стыскааня можно воспользоваться методом Магу, применяя его к орграфу О. При этом, очевидно, используемая в методе Магу матрица А (О) полностью совпалает с А (б). Таким образом, метод Магу без нэменепий переносится н на пропэвсльаые неориентярованные графы. Более того, несложно показать, что если орграф О получен из б (11, Х) введением ориентайии на ребрах [т. с, каждое рейро (ю, ю)шХ мы замвнжш вибо на [ю, гз), либо на [тз, о], но не на ойе зги дуги одновременно), то н в этом случае совокупность ввутреняе уегюйчввых (мвиснмалзных внутренне устойчивых) множеств вершин орграфа О совпадает с совокуписсшю шгутревпе уегойчввьш (максимальных внутреяве успгйчивых) множеств верины графа б.
гэ из 4.4А. Внешняя устойчивость э,ориентировазшых графах Пусть задан оргреф О = (У, Х). Множество (Г чд У называется внешне устойчивым, если Уэ УчВ ()ПО( )- а, (4.43) т. е. любая вершина вечу, не принадлежащая (7, связана, по крайней мере, с одной вершиной рл (Г дугой с началом в вершине ш Пример 4.36. Для орграфа 37 и множеств Вь ()з, (гз.()ч (см. пРимеР 4.36) множества (г» (гз н ((з (оь оэ оз) Явлаютса внешне устойчивымн, а множество (гз (а следовательно, и()з) таковым не является, поскольку озМ(сч, на при атом (оз, ез) вйХ, (оз. оз)МХ. Висзпне устойчивое множество Прну называется мимпмааьиым, если после удаления из (7 произвольной першины получаем множество, не являющееся пасшие устойчивым. Часто при решении практических задач требуема найти внешне устойчивые множества с минимальным числом вершин.
Их следует искать среди минимальных внешне устойчивых множестк Замечение 4.47. Внешне устойчивые множества, а также минимальные внешне устойчивые множества аналогично определяются к для ориснтнровзнного псевдографа. Прн этом, если в ориентированном псевдографе удалпть петли и принять кратности дуг раэнммн 1, то в полученном такам образом орграфе внешне устойчивые множества (а следовательно, и минимальные внешне устойчивые множества) совпадают с внешне устойчивымн множествами (соответственно, с минимальными внешне устойчивымн множествамн) исходного ориентированного псевдографа, и поэтому в дальнейшем будем рассматривать лишь арграфы без петель и кратных луг.
Пример 4АО. В продолжение примеров 4.36 п 4мф имеем: йи (гз — минимальные внешне устойчивые множества, а множество (гз таковым ие является, поскольку, удалив из ()з вершину пз, получаем множество (гь снова являющееся внешне устойчивым. Озозаача срез и(О) окуааость е ез маа мазь аеи у зчиазм на месте ырмаа ор раф Ш Тогда ча зо 3(О) - ш1а 1171 О 6(О) аазнааат а числом засч чы Гсгоячаэхги ер рафа О 4.4.6. Метод Магу отысканнв семейства минимальных внешне устойчивых множеств ПУсть () = (У, Х) — оРгРаф, где У = (оь ..., е ), ПУсть далее (7 — некоторое множество вершин орграфа )), т. е.
(7 ш у. Сне- дав ва [как и в равд. 4.4.2) воспользуемся булевыми переменными Уь ..., У, а также оценкой (еь ..., е,) списка переменпык (Уь ..., У ), удовлетворяющей (441). Заметим, что условие (4.48) в определении внешне устойчивого множества (7 равносильно тому, что У(ш(1, 2... а) выполняется, по крайней мере, одно «з условий: П нши! 2) 0ПР!(о~) чй)2) (т. Буш(1, 2, ..., л) гаущ(1, о~шД[ш)), что в силу (4.41) эквивалентно выполнению равенства й(гг)7 )I (аойег)1 1. (4А9) где (щ))=А (О). если при каждом фиксированном ! под записью «ао=!» понимать множество всех )ш(1, 2... гф таких, что аа=(, то условно (4.49) можно переписать в виде й(з)/ 'тl зд 1, с,г 1 ялн, обоаначнв Я(7..7.)-,й,(7)7 Ч Уг). ао 1 в виде Г(еь....
е ) 1. (4.50) Таким образом, мы показали, что справедливо Утверждение 4.52 Необходимым и достаточным условием еяешяея устойчнвости ммсашстза Оску яасштся емлоляеняе равенство (4.50), где (аь ..., е ) удовлетворяет (4.41). Из утверждения 4.52 слеаует, что внешне устойчивые множества вершин орграфа О, и только они, соответствуют оценкам списка переменных (У„..., У,), на которых выполняется равенство Р-!, что дает простой сйссоб выделения всех внешне устойчивых множеств вершин орграфа П. Опишем теперь метод Магу выделения всех минимальных внешне усшйчнвых множеств вершин орграфа Т). Применяя обобщенную днстрибутнвность й относительно )/, приводим формулу логиин высказываний Р к ДНФ. а затем сокрзщаем ее да тех пор, пока это возможна, используя равносильности (4Аб).
В результате получаем формулу Р, (равносильную Р), находящуиюя в ДНФ, кажлому юмъюнктнвному члену Уй й У), й. йуб которой соответствует минимальное внешне устойчивое множество (он, ог,, ..., пг„). Замечание 44У. Перед ариведением к ДНФ часто оказывается делессобразним упростить формулу Р, арнменяя (до тех пор, пока это возможно) заков поглощения 237 Ай (А ~с В) ам А, (4.51) справедлявый лля любых формул лопгкгг высказывннпй А, В. Кроме того, остается в снле замечание 4.4б. Обоснование метода Магу.
Покажем, что любое множество, найденное методом Магу, является мннкмальным внешне устойчивым, а также то, что методом Магу выделяются все мнннмальные внешне устойчпвые множества вершин орграфа Р Пусть О= (сй, сл, ..., ой) — некоторое множество вергпнв орграфг Р.
найденное методом Магу, (!ь - !г) = (1, 2, ... и)' (!г, ..., 5), й+ +1 л. Тогла К Уг, Й...АУ!„— лвзъюнктивный член формУлы Рь в на опенке <щ, ..., а ), УдонлетвоРЯюпгсй !4.4П, очевидно, выцсаняется равенстзо К=1, аслсдовательно. Р(еь., е ) = = М(ег, ..., е ) = 1, откуда согласно утвержденню 4.52 получаем, что Π— внешне устойчсвое множество. Покажем, что О— мннкмальнос внешне устойчивое множества Предооложв«. что зто не так. Тогда найдется вершина юсяО такая, что множество О Ох(м) также будет внешне устойчивым. Пусть алн опрсделеннастн ю = оп.
Тогда, пспользуя утверждение 4.52 и полагая в опенке <еь ..., е ), удовлетворяющей (4.4!), гн 0 !вместо ай =1), получаем, что в силу внешней устойчввоств множества О (очевндно, что теперь оценка <вг, е„> соответствует множеству О) пыпощяетсн равенство Р,(еь ..,, е ) Е(еь, а ) = -1, а скццовательно, по крайней мере, одкннзднзъюнктнвных членов К формулы Р, должен прнпнмать па оценке < ы, ....
е,) значенне1. Но тогда в К отсутствуют оеременныс Уч, 1' ., У,. а значнт, К тг' К е К, что протнворечнт определенпю Р, Это прствворечяе показывает, что наше предположение неверно, а следовательно, Π— мннпмальное внешне устойчивое множества. Покажем теперь, что методом Магу выделяются все мпннмалькые внешне !мтойчнвме множества вершин орграфа Р. Предположим, что зто не так, п О = (ся, ..., сц) — некоторое миннмальное внешне устойчивое множество, которое не удалось выделить методоы Магу.
Пусть <еь ..., е„) — оценка слпска переменных <Уь ..., У„), удовлетворяющая (44П. Согласно утверждению 4.52 пмеем Уг(вь ..., е ) = В(еь ..., е,,) = 1, а слелаватсльно, на оценке <е, ..., в ~ значение ! должен прннвмать, по крайней мере, одна цздпзъюнктквпых членов К формулы Рь Но тогда в К должны отсутствовать переменные Уг,, ..., У!«где ((ь ...,)г) (1, ..., и),(гь ..., м), й+1 л, а значпт, мннпмальнос внешне устойчивое множество О, соответствующее ззз йт, «вляегся подмможеством множества О, отличного от О (см. сделанное выше предположение отаосительво О), т.
е, собствен. ным подмножеством множества К а это противоречит тому, что Π— минимальное внешне устойчивое множество. Прпмзф йз(1. Используя метод Магу, опрш!елим совокупность мннямальнык внешне устойчнвык множеопз вершян орграфа О (см. пример 4.38), изображение которого приведено яа рнс. 4.39. Имеем й (УМ (/ Уз)= зн-! =(ут/у,т/у.т/у,)й(у г/у)й(ут/у)й( .(/у.)пн (применяем закан поглощения (4.51]) (у з/у) й (у х/у) й (у, т/ у ) (нспользуем (4.47) и он)охаем символ й) (У,з/У,У.)(У,Ч У.) (врязгюшем обобщмгяую дистрпбутнаиость й отиосвтельяо и равносильности (4.46)) з/ У !'з з/ !'зуз)з тз/ «'з)'з)'з з У,уз )/ У>уз Ч !'зуз. Таням образом, мы получилн формулу, находящуюся в Д!.!Ф.
Дальнейшее ее сонрашеняе с использованием равпосильжютей (4.46) невозможно, в следовательно, искомыми мянимальвымн гжешпе усгойчпвыии множествами вершин орграфа О являются множества (оь оз), (оь оз), (ль оз), н при этом Р(О) = 9. 4.4.6. Внешняя устойчижють в неорнемтврованных графах Впешне усгойчпвые множества вершин можно аналогично определить н длянеориентированного графа С (У, Х), а именно: множество О щ У иааывается внешне устойчивым, села У и СОС(о)~а, т. е. любая верящие и щ !'.
не принадлежащая О, смежна, по крайней мере, с одной вершиной из О. Нетрудно аадсть, что если графу С = (У, Х) поставить в соответствие орграф с множеством вершин 1', заменяя каждое ребро (о. ю» графа С из две дуги (о, ю), (ю, о). то в получаемом таким образом орграфе О совокупность внешне устойчивых множеств вершин совладает с совопупностью внешне устойчивых множеств вершин графа С (псснольку в этом случае Уощу С(о) =О(о)) Но тогда и совокупжкть мпннмальных внешне устойчивых множеств вершин графа С совпаяает с совокупжмтью мивпмальнмх внешне устойчивых множеств вершин орграфа О, а следовательно, для Вэн их отмскания можно воспользоваться методом Магу (применяя его к орграфу О).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
