В.Н. Нефедов, В.А. Осипова - Курс дискретной математики (1127083), страница 51
Текст из файла (страница 51)
Прц этом, очевидно, используеман в методе Магу матрица А(О) полностью совладает с А(С). Таким образом, метод Магу без изменений переносится и на нсориеатнрованные графы. 4.4.7. Ядра орграфа Пусть задан орграф Р=(Р, Х). Множества г?шу называется ядром орграфа О, если Ф вЂ” олновременно внутренне и внешне устойчивое множество, т.
е. если выполвяются условия: П ьо )У )?ПО(о)=а; 2) ЧишММ )?ПО(о)тьЫ. Замечание 4.42. Аналогично определяется ядро и для неориентированного графа С, при этом н условиях 1 и 2 О(о) заменяем на С (о). Орграф может не иметь ядра, иметь одно или несколько ядер. Заметим, что если орграф О имеет ядро М то Р(О)» (Ф(» » а(О). Пример 4А2. Рассмотрим орграф. изображенный на рис.
4.40. ыг Он нс имеет ядер, поскольку любое ы множество с одной вершиной не является внешне устойчивым, а любое маожество с двумя или тремя вершянами не является внутренне устойчивым. Пример 4.43. В прололжснис примеров 4.36, 4.37, 4.39. 440 имеем: О„О,— Ртт 44О ядра орграфа О, изображенного нв рис. 4.38. Теорема 4.?. Для того чтобы множество И ш Р являлось ядром оргрофо О = (М Х), необходимо и достаточно, чтобы оно было одновременно максимальным енргренне устойчивым и ми~имальным алешке устойчивым. Достаточность очевидна.
Докаткем необходимость. Пусть Л(— ядро орграфа О. Предположим, что ЛГ не является максизгальным внутренне устойчивым множеством. Тогда найдется вершина шшР ЛГ такая, что множество Ф = ЛЧ)(ы) снова будет внутренне устойчивым. В силу внешней устойчивости тт, а также того, что юшйг, найдется вершина ошМ такая, что (м, о)шХ, а это противоречит внутршгней )ттойчивости множества Ф, поскольку и, ш ш М Предположим теперь, что )У не является минимальным внешне устойчивым множествам. Тогда найдется вершина ш шд/ такая, что множество У = Ль,(ш) снова будет высшие устойчивым. Но тогда из шшгт, испатьзуя внешнюю ус- 240 тойчнмють мможества д!.
получаем, что найдшся вершнпа ош е)сс)ц такая, что (ю, о) чпХ, а зто а снлу о, шшйг протнворечнт. внутренней устойчивости множества дг. Из теоремы 4.7 слелует, что лля выделенн» ядер арграфа О лес!а!очно, например, найтн все маннмальныс внешне устойчивые мншксства вершин орграфа О, а зашм выбрать нз ннк вну!. ренее устсйчпвыс множества, 3омечалпл 4.И. Утвержденне теоремы 4.7 остаетс» справсдлнвым и для неорнснтярованншо графа. Доказательство аналогично.
Пример 4А4. Определнм ядра орграфа О (см. пример 4.38], нзображенве ноторого приведено на рнс. 4.39. Воспользовавзпнсь примерам 4.4(, выберем из минимальных внешне устойчнвык множеств вершам арграфа О множестве, являющееся внутренне усто(чквымв. Едннсшенным такам множеством будет множество (оь о!). В салу теоремы 4.7 — зто ядро орграфа О. н другик ядер в О нет. 4.4.8. Функпнн ма вершннак прграфа. Перядкпвая функпна орграфа без контуров Рк ««р ор р р П (!', л), ш с лезмаюы юкптр а ассаезк же е!' !'ь,тл !' ~ ют)О()-И); ( м Р,(Г,Ц Гб(О( )' О.Ц Гц! (4.32) ш=(тютдц г(о()ы ц г] л — ееаьее ее о т «ае, ло Рну И (пр шюююз е т г ел агл» и язюес. о ч .
г е ед ю»). Гл и у,, !'ь, !', еез аю с ггюе г ! ст зар П. Тепрема 4.8.уроепи орерафа О ((г, Л) без конгррсе «еляюгеа лелрстмми ллохестеомм обргшрющнми розбиснне лноягестео еео ееркшн У. Пзюю з тг шзаме, р л с лтюмю г ер касаи: !) т го! 2) юл ет зе ро ГШО юю н е ш и рамн ее у,тьм,..., у а,т цг )з. »г чйс Докажем сначала справоативссп первого утверждена». Предположпм, что Уь )3. Тогда Уошр О (с) чь И. [4.33) Пусть ш — прок!вольная вершнна нз У.
Рассмотрен пссле- М! доввтельность вершнн оо пт... твную. что У/ър пгшО(п, г). В силу (4т55) ее.можно продолжать неограниченно. Поскольку «олнчество вершин в оргрвфе О конечно, обязательно пронвойдет савпаденнет ог = о/, где )ш/(у. Пусть ато будет первы» совпадением, т. и совпйданвем с наименьшим номером /. Тогда оггчы . о/ — врастай контур в О, в это противоречит уславням теоремы, согласно которым и О нет ювтуров. Д как м т нер равеьшвпп второю у ерпден я. Пу р нвв. оро )ШО в о вв нер авсюа У,ч'-И...., У чьш, Рч В У таИ. ПРедлоломнм, по Уьв И. ПУвь и — Ронзв аРаоам ю УЧ В Уь В «нлУ Уоп И нмаен О(,),В У чь И, т.
н сУв свУе в Р. а выр(з ) таая. чю о ы Рч В Уь Анааючю юя е айдыс аер. -о шю выО(о,) ю д что озву'чн у в т. л. Так н браса, мвк о т к с рв б валун с.а» таьнс ть еь ь.. арвмн нз У,В 1' ыу, стоу/шт е,ыО(ег ). Поташа а с«п од к ва ту ерюо уаркде япоуам, овос ьвнаупазо оры орые нвдноу преввшвкмшп В с у ут раде нб 1, 2. и полыуя ю во т юмеваа у, а шае пп е еюднмй ра, п У, В Уг И прн / ш ь) (4.54) воаучым, о сушеспгуег чаше г Ш О вы, то У ВУ. ! 4.55) Из (454) ° (4%) еаклвчае, ч о мнвкев а у, у, обр зу т р ь.
б е е плоше У. Донажем твнже справеллнвкть утвержденна, обратного теореме 4.8. Утверждение 4.53. Пусть О = (У, Х) — оргрвф, габ. Уе)л — мепрсгвс шюжестза, рдовлшзордюд(нл (4.52), такие, ва У (/ Уь Уаеда Π— прерпф без контуров. Првш.лоанм, во в О нвыы и ор й ковур ее .. е,»ь ло ЛШ2. Пу ь / — ма н впмй ао ер р дя О,..., ° «ой, ч о 1'15(в,..., П 'Д/И. Д Я ПРОСППМ ОбавпзЫМНй бУДЕ» т тп ВО, 1тг. тстп ыу, а 1Ш/) В сн у выуг по опрелеленм 1'1 ее О( ПЫ 1-т П у ( шутке / О в веют сане нмы О(л,) И), во ро».
л-о аУЕ та У, О О ЫО(В), Е Ы Уь /Ш/ Функпия 0(а), определенная нв множестм вершин У оргра- 242 фз без контуров О (У, Х) и ставяша» в соответствие кажаой вершине ошу номер уровня, которому она принадлежат, называется лорлдковол фулкциел орграфа О.
Пример 4.45. Разобьем орграф О, изображенный на рис. 441,а, на уровни и опредетвм порядковую функцию 0(о). Согласно (4.52) имеем ее = (о му(О(о) = !В) = (оо ов); У~ = ~ошухуе)О(о)оду ) (оь от); ШУ(уеЦ У))О( )=У;ЦУ) = (о); Уз (ошух(уеЦ У~ 0 Ут) (О(о)с УеЦ У~010 (от)! Ух(уецуеЦУгЦУз) = !В. Определив множества Уе, 1гв 1'и Уь найдем значения порядковой функции 0(о), о шУ (на рнс. 4 4!,а они указаны прн вершинах). уг тг г гв Ф/ Ри еж Зцгючокие 4.5!.
Для нагляансств после разбиения нмгсторого орграфа О на уровня имеет смысл перерисовать его, последовательно расположив вершины орграфа О на вертиюльтгых прямых, прн агом вершины одного уровня располагаются на одной вертикальной прямой (см. на рис. 4.41,5 изображение орграфа О, описанного и примере 4.45, с таким расположением вершки).
!!Риведсм простой алгоритм вылелеиия уровней орграфз без контуров, нспользуииций задание орграфа матрицей смежности. Он может бьць легко реализован на ЭВМ. Ллгориюе 4Э нахожления уровней орграфа О = (У, Х) без контуров: Шаг !. Выпигпем матрицу смежности А(О). Образуем под матрицей А (О) строку Ла, в 1.и месте которой укажеы число единиц в г-й строке натрием Я [О). Уровень Уе образуют вершины, жцоРыы з стРоке Лг соответствУет число О. Вели У Уь тп задача решена и Уп — единственный уровень арграфа О.
В противном случае переходим к шагу 2. Шоз 2. ОбРвзУем под стРокой Л, стРокУ Ль става нол каждым нулем игроки Лз сямвол Х, а на любом прутом 1-м месте— тез число едишщ в 1-9 строке матрнды А (О), нс учитывая единицы в столбиах, находящихся над символами Х в строке Л. Уровень. У~ образуют вершины, юнорым в строке Лг соответствует число О. Полагаем ) !. Шег 3. Пусть прн некшором )уж! уже построены строк«Лз. ..„Лг, по которым получены множества Уз, ., Уг.
Если сгрока Лг сошовт нз «улей н символов Х, то задача решена и при г = ( Уз..-, Ш вЂ” уровни орграфа д(. В противном случае персхо. днм к шагу 4. Шаз 4. Образуем под строкой Лг строку Лгм, ставя под каждым пулем н символом Х строк« Л, символ Х, а на любом другом 1-м месте — число ешппщ в г-й строке матрицы А(Р), не учнтыиа» единицы в столбцах, нахоляшихся над символамн Х в строке Лгм. Уровень Ум. образуют вершины, «вторым я страке Лы соответспгует число 9.
Присваиваем 1 г ! + ! и переходим к шагу 3. Пример 4АО. Применяя алгоритм 4.9, разобьем орграф (Г„ списанный в примере 449 (см. Рвс. 44),п), на уровмн. Мкгряца снежнссти оргрэфа Дд а также строки Лэ. Л, Лэ, Л„являющиеся результатом работы алгорвтма 4.9, приведены в табе. 4.! !. Иэ таблицы слслует, по Уэ = (оь оз), У = (оь о ), У* = (оз), ! = (о ). Обосиоеа«ие а«сор«тли 4.9. Заметим, что едииипы в г-й т ози«а эл! стРоке матрицы А((г) соответствуют вершинам, принадлежащим ОбРазу 19 вершины орграфа В. О, гг и, гг йрг Но тогла нули стропи лэ сош еснствуют вершинам, абразьг Г) О О О О О .
.Рык Реалы иу. «т множе- 1 Ггг О О 1 1 О 1 Стар, т. Е. ВЕРШииаМ Из Уэ Далее рассмотрим нетривиальный случай, когда Уча уь г)0. По 111 О О О О О О описанию алгоритма симвслм Х О О О О О 1 а строке л, ставятся иод аулами строка Лэ. т. е. (по уже докаэангй О О О О О О хаму] оаи соотвегствугот верши- нам «э !'ь а следовательно, поДг 1 О У О 1 О СКОЛЬКУ ИРИ ОПРЕДЕЛЕНИИ ЭЛС- ментов в Ль »с запятых симво- л, О 1 э з О " лами Х, мы нс учитмавем столб. лг х 1 О х к цы матрицы А(Р), натодяпгио ся иэд символами )( в с~роке Ль то аула строки Л, соответствуют вершинам нз У,)гь образы «старык целиком садержатс» в У, т.
е. вершинам из Уь Пу«м зер»з им«ЗЗО (ш (1, . ) л ш, ч о эгш з « .,9«г тсгл.ыш Р дгш. г н тш за ахваз эмвэт«х,» Зез ! Рч, О У О, эзчнт. ! н Р,....У, — н маетр «графа Д «в В ЭР т«ЫЭ СЭУ ЭЕ )(, Я Э Эа НЭ Ю РЮ«т Шра УЕ Г т Лг и РИ т м сэ мти Х э строке Аи, еае эегсвтшт эсрэ ю«э Уй)..О«У, (тэк как и Х. э роке Лг, иэ и ээ,г нт энн эм эн) Х е ре«э Ад Лале, «сскэ«э«т зтн эт лш чмэ ые«снюэ е А .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
