В.Н. Нефедов, В.А. Осипова - Курс дискретной математики (1127083), страница 49
Текст из файла (страница 49)
прн )чь!), является лннейвой комбннаиней остальных строк матрицы В'(О). Танки образом, строки матркиы В(О] с кимврами К > авлюогся лв. ксйнымн ютмбннапиямн остальных строк юой матрнцы, а слы довательно, гапй В(О) ыл — 2, что противоречит асрвому упмрждевню. 1)з утвержаення 429 непосредственно следует, что если С— свящмй мульткграф (соотвстсгвующвй неююрой злекгрнчес. кой цепи Я) н Π— ориентированный мультнграф, полученный нэ С введением ориснтыши на ребрах мультпграфа С, то нскдюченне нз В(О)! а лгобого уравнения дает линейно независимую систему, н прк этом всключелнос уравненнс является линейной игмбанацней оставшнхся.
Задачи и упражнения 1. Показать, чю у дерева 0 с л[0) ъй найдутся, по «райней мере. две висячие вершины. 2. Похавать, что дерево, содержащее ровно две висячие вер. шины, является простой цепью. 3. Определить любое остовное дерево графа О. Найтн пикпоматическае число графа О. Варианты графа С предогавлепы на ркс. 4.35,а, б. 4. Определить минимальное остовное дерево нагруженного гра а, иэображемного на рис. 4.36. $' . Пусть 0 — мультиграф, изображемпый иа рнс. 4.29, с, н в 0 введена ориентация на ребрах (см. рис.
4.29,5). Определить вектор-аиклы, соответствующие следующим пикламг а) Ш о,хзо,хэозх,о~х,о хэо хзозхзоэхзои б) пз о,хеозх,о,х,о «зс хзе хю х е хзо,хго,. 6; Найти в мультиграфе С (см. задачу 5) циклоэой базис. Определить пикломатическую матрицу. 7. Определить цикловые базисы для графов (см. задачу 3). Введя произвольно ориентацию на ребрах, определить никломатические матрацы для этих графов. Яф г Ркс. гэа 6.
Составить базисные системы уравнений Кирхгофа для напряжений в электричесних ивняк, схемы которых ырсдстаеленм на рис. 4.37,а, б. 9. Составить систему уравнений Киркгсфэ дл» гоков а электрических цепях [см. задачу 6). г г ф Ю. В условиях задач 3, 3, испольэун закон Ома, составить системы уравнений для томов в электрических цепях. Считать внутренние сопротивления источников ЭДС разными г, где г)0.
4.4. ВНУТРЕННЯЯ И ВНЕШНЯЯ УСТОЙЧИВОСТЬ В ГРАФАХ 4.42Ь Вяугрвннян рптойчивасть в ориентированных графах Пусть задав орграф О= (У, Х). Множество ОШУ называется внутренне устойчивым, сели У. О ОПО(э) =а, (4.40) т. е. в орграфе О не сушествует дуги, связывающей какие-либо две вершины пз О.
Пример 4.36. Дпя арграфа О, изображенного нв рис. 4.3В, множества О~ = (о~), Оэ (оь оэ), Оэ = (оь в,) являютсявнут- ревие усгойчивымн; множество Оэ = (оь вэ) ые является внут- ренне устойчивым, так как в Ю имеется дуга (еь оэ). Внутренне устойчивое множество (/сдУ называется макси- мальным, если, добавляя к О любую вершину оспухО, получаем множество, не являющееся внутренне устойчивым.
Чжто при ре- шении практических задач требуете» найти внутренне устойчи. вые множества с максимальным числом вершин. Их 'следует ис- кать среди максимальных внутренне устойчивых множеств. 3алечакие 4.4Б. Внутренне устойчивые мпожества, з также максимальные вяутреннс устой швые множества аналогично сг: ределяются и для ориентированного псевдографа. При атом, ес- ли в ориеьыгроввнпом псевдографе удалить инцпдентные пстлям верюины и 2 вместе со псеыи ннцидситиыМв им дугамн и припать «ратиастк дуг равными 1, тс в полученном таким образом юрграфе внутренне устойчпвыс миожества (а следовательио, и максныальиые внутренне устойчивые множества) совпадут С внутренне устойчивыми множествами (соот- э ветствснно, с максимальиымн внутренне Рве.
еээ устойчивымп миожегхвамн) исходного ориентированного псевдографа, поэтому в датьнейыек будем рассматривать лвшь орграфы без петель н крагных дуг. Пример 4.37. Воспользуемся мпожествамн Оь Оэ, Оэ призе. деннымн в примере 4.30. Тогда множество Ог = (в,) не «влчет- ся максимальным внутренне устойчивым, так как, добавляя к И вершину оэ, получаем ыножество Оъ снова яютяюшыся витт. ронне устойчивыьь Напротп», множества Оэ, Оэ явлвютг«итк:г- мальныып внутренне устойчнвымн. ПЗ1 Обозвашм через о(О) сошятппссть всех мзпснывп пык заутревае тстсачпвык мзашссте зершвп оргрзфа О.
тогда чнгэо а(О) !пэз )О! Ошп(О) назмззеня м ыш зяргрнпмл ргтплепяосгп орзра(ы О. 4А.2. Метод Магу етмсканпн семейства максимальных внутренне устойчнвмх множеств (4.42) В О (и ! )/ с )/ ег) 1. (4А4) г э! Ззнегпя, что нрп ае О ээзс;Юно знпшшвегю! рзэевстео п>Ъ'зргр )/эз= ), а прн по ! глрвпеяшео ш!'ггы)ре. и ))зь но тогда, селя под шш!сью ао !» псппнвгь зшсшгшео есек пар (( г> гаквг что г, )ш(), т .,„я), с,г ! (зссяплыу хчьИ. зто «вмкссшо ве яшшегсв пгсгыы), го условна (4 44) назло перепн згь е виде а (е.Че» ао-! нпп, саозначне Р(Уь ..., У.) = й(ЮУУ,), аы ! Пусть О = (У, Х) — орграф, где ХчьИ, У = (о!, ..., о ). Пусть далее () — некоторос множество вершок орграфа О, т. с, Урду.
Введем булсвм переменныс Уь соответствующие нержинам оь ! 1, 2,, л. Рассмотрим оценку (еь ..., е ~ списка персыен- нмх (У!, ..., У ), где У!е Ь л) ш= (! еслн олы(Р (4.4!) (О, если о!МК Про оценку (сь ..., а ) будем говорнть, что опа соответст- вует множеству () н, наоборот, что множество () соответствует указанной онснкэ. Заметны, что условие (4АО) эпвнэалентпо то- му, что Уй )ы(1, 2, ..., л» выполняется (шИ, о! О(ог),М(), а в силу (44!) это равносильно тому, что У!. !Рж(1, 2, ..., «) (е,йоч)~эз = 1, где ан — (й /)-й элемент матрицы сыежностн А (О).
Преобразуя (4А2), получаем У(, 1!ы(1, 2, ..., л) оц'4ю24к„=!. (4АЗ) Усзоепс !4.43) можно запасать виде в впле Е(ш, ..., еп) 1. Таяны образом,мы покавалн, что справедливо тэт (4Аб) Утверждение 4.61. Необходимым я достаточным условием внутренней Устойчивости мнсжесша Ощр яаляетс» еилолление рееелстел (4.46), где щеь ..., е ) Удовлетворяет (44!). Из утверждения 4тй следует, что внутренне устойчивые множества вершин орграфа Р и толькп онн соответствуют опенпаы спнсна переменных (Уь,. У ), на историк выполняется равенство Р 1, что дает вам простой способ вмделевия всех внутренне устойчивых множеств. Онигпем теперь метод Магд вылелснвя максимальных внутренне устойчивых иножеста вершин орграфа Р.
Применяя отюб. щенную дисгрибутивность й отнсситслыю (/, приводим формулу логики высназыааннй р к дНФ, а затеч сокращаем ее да тех гор, аоки зто мгзможио, используя равносильности (см. раздл!.2) А А(/(ААВ), АтУА — Л, АЙА — Л, (446) где Я,  — праизвальнме формулы логики вмсказываний (докажите, что возможно лишь конечное число таких сокращений). В результата аолучаем формулу Р, (равносильную Р), находя. щуюся в ДНФ, каждому днзъюнкгивиому члену У, буг,'б... ...йТг, которой соответствует наксимальгюе внутренне устойчивое мн жество 1' (пг, и!.
- "г,). Замечение 446. Перед приведением и ДНФ часто аказмваетс» целесообразным «рсобразовать Р. всспользовавогись рзвноснльнсгтямн л й А — А, (А ту В) б (А (/ с) й ... б (А хуР)— Аттг (ВАСА...АР), (4Л7) где А, В, С,, Р— произвольные формулы логики высказываний.
Обоснование метода Магу. Покажем, но любое множество. найденное методом йщгу, явлнетси максимальным внутренне устойчивым, а также тс, что мщодам Мвту выделяются есе максниальвме внутренне устойчивые маожества верпшн орграфа Р. Пусть О (ое, сь, ..., ои) — «ектпорое множества вершин орграфа Р, найденное методом Магу. Пусть дзлее Ць ..., (г) (1, 2, ..., л)Х(!г, .... и), й+1 и Тагдз К= У(,б...йуг,— днзъюпктнанмй член бюрнулы рь н на опенке (зь ..., е ), удовлетворяющей (4.41), очевидао, выполняется равенство б 1, а саишвательно, Г!еь ..., е ) = р фь ..., е ) 1, откуда согласно утверждению 4.61 получаем, что Π— внутренне устойчивое множество. Понажем, что Π— маиснмальвое виутренв» устойчивое множество.
Предположим, что зю не так. Тогда найдется першина мшдчО такая, что множества О.= ОЦ (м) будет внутренне устойчивым. Пусть дли определенности и о, Тогда, испсльзУн УтвсРжденне 4.6!и иолагаа в оигикс Щег, ..., а„), УдовлегваРЯюпгей (441), ей=( !вместо ег, 6), иолУчаем. 1З вЂ” 1ЗЩ щз чте в силу внутренней усшйчивости множества О (очевидно, что теперь оценка <и... е > аюгзсмтвует мвокштву О) выполняется равенспю Р~ [еь ..., е ) Р(ег, ..., е ) = 1, а гледовательио, по крайней мере.
слин ш два ьнинпивиых членпв дт формулы рг 1!олжен принимшь на оценке <е,, а ) значение 1. Нс тогда в К отсутствуют кон'ыоиятивнме члены вида Уг,, ..., Уг„ У!г а ЭиаЧнт, К'тт'й ЗП К, ЧтО ПРОтМВОРЕЧнт ОПРЕЛЕЛЕИИЮ РЬ Это противоречие показывает, что наше предпогоженне неверно, а слеловамльно, Π— максвмальное внутренне устойчивое множество. Покажем, теперь, что методом Магу вмдевяются все макси. мальвые внутренне устойчивые множества вершин орграфа О. Предпсложвм, что это не так, и О (пг,, ..., сг„) — яекоторос максимальное внутренне устойчивое множество, которое ие удалось выделить методом Магу. Пусть <м,, а ) — оценка списка переменных <Уь ..., У ), удоалетворяйицая (4А1). Ссь гласно утверишению Яб! имею» Р~(ш, ..., е ) Р(еь ..., вп) = 1, а следоепюльигх иа оценке <еь ..., ) значение 1 должен принимать, по крайней иере, олин иэ дизъюнктивных членов )( формулы рь Но тогда в (( лслжны отсутсшовать конъюнкпмиые члены вида Уь, ., Ук, а значит, максимальное ш!утреинс устой.
чпвое множество О. аютветстеуюшее К, содержит «се «аршины множества О, стли пюго ог О (сы. сделанное вылив предпшюжение относительно О), т. е О являеюя собственным водмножесг. вом множества К а зто иршиворсчит тому, что Π— максимальное виутреене устойчивое множество. Пример 4.33. Испальэуя метод Магу, опреаелим соаокупнапь максимальных внутренне устойчивых множеств вершин орграфа О, изображенного на рис. 4.30. Выпишем матрину смежности и ~0 1 0 0 0 Р г "(О) ~1 0 0 а ~ 0 0 ! 0 п( Р . 4ЛВ Та.да «) у.)у У,) - (У Ч У*) й (У )у У ) б (У ту д) б 1 «[У Ч У ) й (У тУП) д (У, [7 У ) (вспольэуем РД47) н опускаем синвоя й) [у Ч У.) (У ч «.) [у Ч у') [у.
уу.) -[УЧ у У.ум~.т)й) [применяем обобщенную днстрибутиввость 6 относительно Ч и раююсильиостн (4АБ) ) у у ч уу чу у,у У.ча,у.у.у. Г,У ЧУ,У.ЧУ.У.Уь Таким образом, мы получ~лн формулу, накодяшуюся в ДНФ. Дажшейшее ее сокраШение с использованием рввнсснльнсстей (4АБ) нежмможнс, а следовательно, искомыми максимальными внутренне устойчивымн множсстваин вершин орграфа О «влякпся множества (юь юз), (юэ, оэ), (юД, и прн этом а(Р) 2. 4А.З.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
