Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 34
Текст из файла (страница 34)
+". $$,$2 -,$» + ( — 1) 'и ' ~~ /$,$2..2» $ (3.12) $$$2- $» 11$ 12$ ° ° «Ьо~ ° - $1« = $111$ т2$ ° ° .$ т«$11 Ф 12$ $ 1«-1 Ж 1« Формулы (3.10)-(3.12) выведены из определения производной дС/дЯ графа С по событию 5 при рассмотрении соответственно троек, четверок и и-к элементов. Каждую модель можно задать с помощью частотной гиперма- трицы отношений. Например, модель $Р = (М, 52), М = (а, Ь, с, $(, е), Яз — †((а, Ь,ь(), (Ь, с, И), (с,ьь', е)), матрица инцидентности которой а Ь с в с 1 1 0 1 0 (ь( ) 0 1 1 1 О 0 0 1 1 1 может быть определена двумерной частотной матрицей отношений » Ь с в с 3 3.5.
Усп)оачивоспть, покрыв)ил, паросочеп)а«ил 183 182 Гж3. Теория грв ов и мографов В рассматриваемом примере Я(Ф) н Р(Ф) взаимно однозначно определяют друг друга. Другими словами, модель может быть за- дана не только с помощью перечисления ее слов, но н с помошью задания пересечений этих слов (с помощью задания частот букв в словах). При бопьшом числе нулей частотную гиперматрицу отношений удобно представлять в виде строчной записи. Например, рассма- триваемую модель Ф можно записать как Г(Ф) = а о 2Ь2 о2с обо~ ос оабоадоЬсо 2Ыо2сдосе оде.
Здесь коэффициент при а2 равен ~„при сто) — у д, а, Д = а, Ь, с, И, е; символ о является конструктивным разделителем двух частот. Строчную запись частотной гнперматрицы отношений, задаю- шую модель, в дальнейшем будем называть разложением модели по частпотпам ипн частпотпным разложением модели. Введенное понятие Ф-мерной частотной матрицы отношений Г'=(Л))т...вн) ты 22 ", щ = 1,2,. !М~, связано с понятием х-ичной формы ) (птт, тпю, тп~м~).
Действительно, поставим в соответствие каждому спову рл мо- дели Ф = (М, Яы 52, ..., Яь) линейную форму 1<: ~М~ 12=~ д;. тп, у«а 11, еслитпу бщ, где % = 1 11 в противном случае. ~М~ 1ч х тп) тп2 ...тп)м) ' У н) нт н)м~ т(тпт тп2 ° ° ) ™~м~) т)т) 1)тт т)т~м) «) ) «)т т "«)~м! где символ ,') означает взятие суммы всевозможных слагаемых вида ))т ))т 1м! т у ~у ~ ))т ~ 2 2 '' ~М~ и) ит ~м~) 1. 2" ~М~ «)) «)т - «)~м~ А12, Ф2,..., А1~м~ — произвольные неотрицательные целые числа, сумма которых равна № индексы у коэффициента у «) )«) подчиняются соотношению тп; ' = тп;, если М ф О, в противном т)т) случае индекс опускается, сам же этот коэффициент является со- ответствующей частотой.
Например, У т т « « означает вза- ~) ~т~з-.~~м~ имную частоту ~„ч,„, букв тп) ) тп2. 3 3.5. Устойчивость, покрытия, поросочетония В любом графе можно выделить совокупность некоторых множеств, объединяемых по какому-то признаку, например, подмножеств вершин таких, что никакие две вершины одного и того же подмножества не смежны. Аналогично, граф можно разбить на подмножества ребер таким образом, чтобы ребра одного подмножества были попарно не смежны. В общем случае число элементов в различных подмножествах различно и существует подмножество, где число элементов принимает максимальное значение.
Поэтому можно ввести два инварианта графа дпя попарно несмежных вершин и попарно несмежных ребер. Множество вершин называется внутренне устпойчивым, если эти вершины попарно не смежны. Внутренне устойчивое множество вершин называется пустпым подграфом, если при добавлении хотя бы одной вершины, не принадлежащей этому множеству, образуется хотя бы одно ребро (дуга). Максимальная мошность пустого подграфа графа С называЕтся числом внутпренней устпойчивоспш ипи вершинным числом независимости граФа го(С). Максимальное число попарно несмежных ребер графа С называется реберным числом независимостпи графа г)(С).
Если ребро инцидентно вершине, то говорят, что они понрываютп друг друга. Множество вершин, покрывающих все ребра графа, называется вершинным понрып)ием графа С. Минимацьяая мощность вершинного покрытия называется числом вершинного понрытпил графа хо(С). Аналогично, множество ребер, покрываюших все вершины графа С, называется реберным иоирытпием графа. Минимальная мощность реберного покрытия графа С называется числом реберного понрытпил 22 (С). Условимся считать, что любая вершина графа покрывает сама себя и две смежные вершины покрывают друг друга.
Тогда минимальная мошность множества вершин, покрывающих все вершины графа С, называется вершинным числом внешней устпойчивостпи графа До(С). Аналогично, будем считать, что каждое ребро графа покрывает себя и два смежных ребра покрывают друг друга; тогда минимальная мощность множества ребер, покрывающих все ребра графа С, называется реберным числом внешней устойчивостпи 112(С).
Вычиспение рассмотренных инвариантов графа требуется при решении многих практических задач. Пусть, например, вершины графа представляют собой технопогические модули гибкого авто- 5 3.5. Устойчивость, покрьнпия, паросочстания 185 184 Гл.з. Теория графов и могрофоа матизированного процесса, за которыми должно осуществляться непрерывное наблюдение, а две вершины графа соединены ребром, если соответствующие им модули можно наблюдать, находясь около одного из них. Требуется так расставить телекамеры, чтобы оператор, находящийся у монитора на диспетчерском пульте, мог наблюдать за всеми модулями, но ирн этом число телекамер было бы минимальным. Длн решения этой задачи надо определить вершинное число внешней устойчквости данного графа. П р им е р 3.6.
Введенные инварианты дла графа Петерсена С (см. рис. 3.4) имеют следующие аиачоииа: со(С) = 4, Ц1, 3, 9, 10)) = 4, ст(С) = 5, Яа, а, и, х, у)( = 5, ао(С)=6, ((1,3, 5, 7,8,9)(=6, отт(С)м5, ((Ь,ит, п,р, тЯ м5, ,Во(С) = 3, ((1, 4, 10)) = 3, ЩС) = 4, !(а, с, х, и)( м 4, Т е о р е м а 3.14, Для любого нетривиального связного графа С = (У, Ц го(а) + ко(а) = г1(а) + д'1(а) =!У( (3.13) Множество ребер графа, в котором никакая пара ребер не смежна, называется паросочстпанисм графа. Множество ребер паросочетания, в котором число ребер равно 61, называется наибольшим паросочстанисм графа.
Для двудольных графов справедлива следующая теорема о паросочетании. Теорема 3.15 (Кениг). Для деудольного графа С число ребер в наибольшем паросочстании равно числу вершинного покрытия, т. с. 61 —— до, Совершенным паросочстпанисм из У1, в Ут в двудольном графе О(У1, Ут) называется взаимно однозначное соответствие между вершинами из У1 и подмножеством вершин из Уэ, при котором каждая вершина из У1 соединена ребром с некоторой вершиной из Уэ. Понятие паросочетания в двудольном графе позволяет сформулировать следующую теорему. Теорем а 3.16 (Холл).
Пусть С) = 0(У1, Ут) — двудольный граф и для любого подмножсстпва А С У1 пустпь тпакжс (р(А) — множество тех вершин из Ут, котпорыс смежны по крайней мере с одной вершиной из А. Тогда совершенное паросочстанис из У1 в Ут сущесптвустп тогда и только тогда, когда число элементов )А! ( )<р(А)( для каждого подмножсстпва А 6У1.
Рассмотрим выделение пустых подграфов (Е;) в графе С. Окрсстпностпью С(ио) вершины ио графа С = (У, Г) называется подграф (Уо, ЦД, носитель которого совпадает с окрестностью единичного радиуса этой вершины, 10 — Гио, а сигнатуру сто образуют все ребра графа С, соединяющие вершины Уо. Нсокрсстностпью 6(ио) вершины оо графа 0 = (У, Г) называется подграф (Уо, ГГо), носитель которого есть Уо = (щ/ о; ~ Гоо), а сигнатура (Уо состоит из всех ребер графа О, соединяющих вершины Уо.
Теорем а 3.17. Пустпой подграф С) = (У, Г), нс содержащий вершину ио б У, содержит хотя бы одну вершину из сс окрестности. Сведем выделение пустых подграфов в заданном графе С к построению дерева, в котором каждый путь между висячей вершиной (вершиной и со степенью, равной 1) и концом дуги, исходящей из корня, состоит иэ вершин, которые образуют пустой подграф, где под корнем понимается вершина, не являющаяся концом ни одной из дуг. Согласно теореме 3.17 это дерево строим следующим образом: 1) сопоставим корню дерева заданный граф; 2) фиксируем произвольную вершину оо заданного графа О = = (У, Г) и вершины ее окрестности Уо, взаимно однозначно сопоставим концу каждой дуги, исходящей из корни дерева, вершину из множества (ио, Уо)' 3) каждый конец о построенных дуг взвесим неокрестностью с'(о ) вершины о; 4) считаем конец и построенного яруса корнем нового дерева.
Будем повторять пп. 2)-4) до тех пор, пока каждый конец построенных дуг не будет взвешен символом кт (этот символ означает отсутствие соответствующей неокрестности). Согласно теореме 3.17 путь между концом дуги, исходящей из корня построенного дерева, и висячей вершиной, взвешенной символом тст, состоит из вершин пустого графа. В случае произвольного фиксирования вершины при построении яруса дерева нельзя установить взаимно однозначное соответствие между висячими вершинами и пустыми подграфами, так как последние могут повторяться, т. е. один и тот же пустой подграф может взвешивать несколько висячих вершин. Чтобы избежать повторения пустых подграфов, введем закон поглощения поддеревьев.
3 а к он и о г л о щ ен и я. Если в й-м ярусе дерева вершины и; и и нс смежны и поддерево с корнем и; построено и если в поддереве с корнем и появляется дуга с вершиной и;, тпо соотпВстствующая ветвь нс строится. Закон справедлив, так как поддерево с корнем и. не содержит вершины о из окрестности вершины и;, и б с'(и,), и (согласно теореме 3.17) содержится в пустом подграфе уже построенного поддерева с корнем щ.
Гл. 3. Теория грофог и могра ое 186 1 й 1 й~ 3 4 5 3 4 ,6) Кз В 351 л (1,З,зу Рис. 3.11 Пример 3.7. Найти распределение пустых подграфов в графе С, изабра. некием в верхней части рис. 3.11. Сопоставим корню строящегося дерева ааданный граф С. Зафиксируем вер. шину аз. Ее окрестность состоит из четырех вершин: еп еэ, ам аз; поэтому из первого корня эьшадим пять дуг.
Каппам дуг приписываем одну из вершин и 1 взвешиваем дупг неакрестиастью этих вершин (см. рис. 3.11). Неакрестпость С(ез) содержит тольао вершину аз, воэтаму в третьем ярусе получаем висячую вершину аз. Вершина аэ имеет иеакрестпость с носителем (ез, аы ез).
Зафиксируем вершину аз. Ее неакреспюсть есть Уз = Н, поэтому в третьем ярусе получаем висячую вершину щ. Обраауем еще две дуги нз второго кариа щ: с вершююй ез и неокрестиастью, состоящей из аз, и с вершиной ез и иеокрестяостью ез. Согласна закону поглощения адно иа поддеревьев поглощается. Крест иа рисунке ааиачает, что вошь дальше ке строится и не учитывается ири подсчете пустых подгрвфов. В четвертом ярусе получаем висячую вершину аз. Для вершины второго яруса имеем иеокрестна сть из вершины аэ, и арапесс заканчивается на третьем ярусе висячей вершиной ез, Вершина аз второго яруса со своей неакрестностью усекасгся согласна авиону ваглащення.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
