Горбатов В.А. Фундаментальные Основы Дискретной Математики. Информационная Математика

Подождите немного. Документ загружается.

§3.4. Дифференцирование графов и мографов

__________

181

Производная dG/dS графа G по событию S на четверках эле

ментов:

9G.

— (тпа, ть, тс, md) -

OS J1

Е л -

2 '^ 2 fij + ^ fijkl\, (3-11)

i,j i,j,k i,j,k,l J

i, j, k,l — ma, Ш5, mc, mj, i ^ j, i ^ k, i ф I, j Ф k, j ^ l, к 'Ф 1.

Производная dG/dS графа G по событию S на п элементах:

— ( т т т 1

а с (^11 1 • • •) тп) — г У 1/п 2 • У . /»1>2 +

*1,»2

+ (-1 )"+1 'О! • ^ /»м2..ла + ...

\П+1

•••+ (-1)"

filii— »nj) (3.12)

>*2v»*n /

*11 *2i • • •) *ai • • •) *n — ^ 11 TO2i ■ • •) m ni *1 7^ *2i • • ■) *n—1 ^ *n-

Формулы (3.10)-(3.12) выведены из определения производной

dG/dS графа G по событию 5 при рассмотрении соответственно

троек, четверок и п-к элементов.

Каждую модель можно задать с помощью частотной гиперма

трицы отношений. Например, модель

Ф = (М, S3),

М = {а, Ь, с, d, е}, 53 = {{а, Ь, d}, {Ь, с, d], {с, d, е}},

матрица инцидентности которой

d е

1 1 0 1

1 1 1 0

0 1 1

Q(9) =

может быть определена двумерной частотной матрицей отношений

F(9) =

1 1 0

1 0

1 2 1 2 0 Ь

0 1 2 2

1 2 2

3 1

0 0

1 1

182

Гл. 3. Теория графов и мографов

В рассматриваемом примере ф(Ф) и ^(Ф) взаимно однозначно

определяют друг друга. Другими словами, модель может быть за

дана не только с помощью перечисления ее слов, но и с помощью

задания пересечений этих слов (с помощью задания частот букв в

словах).

При большом числе нулей частотную гиперматрицу отношений

удобно представлять в виде строчной записи. Например, рассма

триваемую модель Ф можно записать как

F(Ф) = а2 о 2Ь2 о 2с2 о 3d2 о е2 о ab о ad о Ьс о 2bd о 2cd осе о de.

Здесь коэффициент при а2 равен / а, при а/З — fap; a,j3 = а, b,

с, d, е; символ о является конструктивным разделителем двух

частот.

Строчную запись частотной гиперматрицы отношений, задаю

щую модель, в дальнейшем будем называть разложением модели

по частотам или частотным разложением модели.

Введенное понятие iV-мерной частотной матрицы отношений

F = [/»! 12... Ijv]> *1> *2» • • •! tJV = 1) 2, ..., \М\,

связано с понятием iV-ичной формы J(mi, m2, ..., тП|лг|)•

Действительно, поставим в соответствие каждому слову /х,- мо

дели Ф = (М , Si, S2, • •., Sk) линейную форму U:

|М|

j= l

/ 1, если mi ^

где q, — | q в ПрОТИВНОМ случае.

Р Р /\Щ \ N

¥/=Ш*гт’) = E w . . ^ x

X TOj 1 TTlj *. . -ТП\м\ ' f N1 N2 -^IMI = m2i • • •)

I I rn , m 2 ...m |Af|

где символ ^2 означает взятие суммы всевозможных слагаемых

вида

■W!

JV, N

N\M\ е

Ж т Г . j w 1 т* " ' га|м| — Д,Г"

N\, N2, ..., N|W| — произвольные неотрицательные целые числа,

сумма которых равна iV; индексы у коэффициента / „ N дг|м,

т1 т2 ••• т\М\

подчиняются соотношению тп^’ = тп,-, если Nj ф 0, в противном

случае индекс опускается, сам же этот коэффициент является со

§3.5. Устойчивость, покрытия, паросочетания

_________

183

ответствующей частотой. Например, /т зт 7т о т о означает вза-

1 2 3*** |М|

имную частоту / mim2 букв mj, m2.

§ 3.5. Устойчивость, покрытия, пар о сочетания

В любом графе можно выделить совокупность некоторых мно

жеств, объединяемых по какому-то признаку, например, подмно

жеств вершин таких, что никакие две вершины одного и того же

подмножества не смежны. Аналогично, граф можно разбить на

подмножества ребер таким образом, чтобы ребра одного подмноже

ства были попарно не смежны. В общем случае число элементов в

различных подмножествах различно и существует подмножество,

где число элементов принимает максимальное значение. Поэтому

можно ввести два инварианта графа для попарно несмежных вер

шин и попарно несмежных ребер.

Множество вершин называется внутренне устойчивым, если

эти вершины попарно не смежны.

Внутренне устойчивое множество вершин называется пустым

подграфом, если при добавлении хотя бы одной вершины, не при

надлежащей этому множеству, образуется хотя бы одно ребро

(дуга).

Максимальная мощность пустого подграфа графа G называ

ется числом внутренней устойчивости или вершинным числом

независимости графа £q(G).

Максимальное число попарно несмежных ребер графа G назы

вается реберным числом независимости графа £i(G).

Если ребро инцидентно вершине, то говорят, что они покры

вают друг друга. Множество вершин, покрывающих все ребра

графа, называется вершинным покрытием графа G. Минималь

ная мощность вершинного покрытия называется числом вершин

ного покрытия графа Tr0(G). Аналогично, множество ребер,

покрывающих все вершины графа G, называется реберным по

крытием графа. Минимальная мощность реберного покрытия гра

фа G называется числом реберного покрытия ж\ (G).

' Условимся считать, что любая вершина графа покрывает сама

себя и две смежные вершины покрывают друг друга. Тогда ми

нимальная мощность множества вершин, покрывающих все вер

шины графа G, называется вершинным числом внешней устой

чивости графа Ро (G).

Аналогично, будем считать, что каждое ребро графа покрывает

себя и два смежных ребра покрывают друг друга; тогда минималь

ная мощность множества ребер, покрывающих все ребра графа G,

называется реберным числом внешней устойчивости /?i(G).

Вычисление рассмотренных инвариантов графа требуется при

решении многих практических задач. Пусть, например, вершины

графа представляют собой технологические модули гибкого авто

184

Гл.З. Теория графов и мографов

матизированного процесса, за которыми должно осуществляться

непрерывное наблюдение, а две вершины графа соединены реб

ром, если соответствующие им модули можно наблюдать, находясь

около одного из них. Требуется так расставить телекамеры, чтобы

оператор, находящийся у монитора на диспетчерском пульте, мог

наблюдать за всеми модулями, но при этом число телекамер было

бы минимальным. Для решения этой задачи надо определить вер

шинное число внешней устойчивости данного графа.

Пример 3.6. Введенные инварианты для графа Петерсена G (см. рис. 3.4)

имеют следующие значения:

£0(G) = 4, |{1, 3, 9, 10}| = 4, ei(G) = 5, |{a, d, п, х, у}| = 5,

1r0(G) = 6, |{1, 3, 5, 7, 8, 9}| = 6, jti(G) = 5, |{*, т, п, р, г}| = 5,

0О(G) = 3, |{1, 4, 10}| = 3, /?i(G) = 4, |{а, с, *, к}| = 4.

Теорема 3.14. Для любого нетривиального связного графа

G = (V ,U )

£q{G) + tto(G) = £i(G) + TTi (G) = |V|. (3.13)

Множество ребер графа, в котором никакая пара ребер не смеж

на, называется паросочетанием графа. Множество ребер паросо-

четания, в котором число ребер равно £i, называется наибольшим

паросочетанием графа.

Для двудольных графов справедлива следующая теорема о

паросочетании.

Теорема 3.15 (Кёниг). Для двудольного графа G число ре

бер в наибольшем паросочетании равно числу вершинного по

крытия, т. е. £i = по.

Совершенным паросочетанием из Vi, в Vi в двудольном графе

G(Vi, V2) называется взаимно однозначное соответствие между

вершинами из Vi и подмножеством вершин из Vi, при котором

каждая вершина из Vi соединена ребром с некоторой вершиной

из V2.

Понятие паросочетании в двудольном графе позволяет сформу

лировать следующую теорему.

Теорема 3.16 (Холл). Пусть G = G(Vi, Vi) — двудольный

граф и для любого подмножества А С Vi пусть также

<р(А) — множество тех вершин из Vi, которые смежны по

крайней мере с одной вершиной из А. Тогда совершенное паро-

сочетание из Vi в Vi существует тогда и только тогда, ко

гда число элементов |А| < |у>(А)| для каждого подмножества

А е VI-

Рассмотрим выделение пустых подграфов {JSJ в графе G.

Окрестностью G(vq) вершины v0 графа G = (V, Г) называ

ется подграф (VQ, Uq), носитель которого совпадает с окрестностью

единичного радиуса этой вершины, Vo = Ги0, а сигнатуру UQ обра

зуют все ребра графа G, соединяющие вершины Vq.

§3.5. Устойчивость, покрытия, паросочетания

_________

185

Неокрестностью G(vо) вершины v0 графа G = (V, Г) назы

вается подграф (Vo, Uо), носитель которого есть

Vq = {vi/ Vi £ Ги0},

а сигнатура Uq состоит из всех ребер графа G, соединяющих вер

шины Vq.

Теорема 3.17. Пустой подграф G = (V, Г), не содержащий

вершину Vo G V, содержит хотя бы одну вершину из ее окрест

ности.

Сведем выделение пустых подграфов в заданном графе G к по

строению дерева, в котором каждый путь между висячей вершиной

(вершиной v со степенью, равной 1) и концом дуги, исходящей из

корня, состоит из вершин, которые образуют пустой подграф, где

под корнем понимается вершина, не являющаяся концом ни одной

из дуг.

Согласно теореме 3.17 это дерево строим следующим образом:

1) сопоставим корню дерева заданный граф;

2) фиксируем произвольную вершину и0 заданного графа G —

= {V, Г) и вершины ее окрестности Vo; взаимно однозначно сопо

ставим концу каждой дуги, исходящей из корня дерева, вершину

из множества {«о, Vo};

3) каждый конец va построенных дуг взвесим неокрестностью

G(va) вершины va-,

4) считаем конец va построенного яруса корнем нового дерева.

Будем повторять пп. 2)-4) до тех пор, пока каждый конец

построенных дуг не будет взвешен символом 0 (этот символ озна

чает отсутствие соответствующей неокрестности). Согласно тео

реме 3.17 путь между концом дуги, исходящей из корня пост

роенного дерева, и висячей вершиной, взвешенной символом 0,

состоит из вершин пустого графа.

В случае произвольного фиксирования вершины при построе

нии яруса дерева нельзя установить взаимно однозначное соответ

ствие между висячими вершинами и пустыми подграфами, так как

последние могут повторяться, т. е. один и тот же пустой подграф

может взвешивать несколько висячих вершин. Чтобы избежать

повторения пустых подграфов, введем закон поглощения подде

ревьев.

Закон поглощения. Если в k-м ярусе дерева вершины

Vi и Vj не смежны и поддерево с корнем и,- построено и если в

поддереве с корнем Vj появляется дуга с вершиной и,-, то соот

ветствующая ветвь не строится.

Закон справедлив, так как поддерево с корнем Vj не содержит

вершины va из окрестности вершины Vi, va € G(vi), и (согласно

теореме 3.17) содержится в пустом подграфе уже построенного под

дерева с корнем Vi.

186

Гл. 3. Теория графов и мографов

Пример 3.7. Найти распределение пустых подграфов в графе G, изобра

женном в верхней части рис. 3.11.

Сопоставим корню строящегося дерева заданный граф G. Зафиксируем вер

шину t>2. Ее окрестность состоит из четырех вершин: t»i, из, v«, t'e; поэтому из

первого корня выводим пять дуг. Концам дуг приписываем одну из вершин и

1,3,5}

Рис. 3.11

взвешиваем дуги неокрестностью этих вершин (см. рис. 3.11). Неокрестность

G(v2) содержит только вершину t>$, поэтому в третьем ярусе получаем висячую

вершину ds. Вершина Di имеет неокрестность с носителем {из, к*, 115}. Зафик

сируем вершину 1*4. Ее неокрестность есть V4 = 0 , поэтому в третьем ярусе

получаем висячую вершину 14 • Образуем еще две дуги из второго кория Hi: с

вершиной из и неокрестностью, состоящей из vs, и с вершиной us и иеокрестно-

стью V3. Согласно закону поглощения одио из поддеревьев поглощается. Крест

иа рисунке означает, что ветвь дальше не строится и не учитывается при под

счете пустых подграфов. В четвертом ярусе получаем висячую вершину t>$. Для

вершины второго яруса имеем неокрестность из вершины 1>з, и процесс закан

чивается на третьем ярусе висячей вершиной «з.

Вершина tu второго яруса со своей неокрестностью усекается согласно за

кону поглощения. Для вершины t/з с неокрестностью V* = {vi, t>s, t>*} строим

третий ярус. Получаем три кория: we, Vi (115), ws (fi). Все они усекаются со

гласно закону поглощения и не учитываются при подсчете пустых подграфов.

Таким образом, имеем пустые подграфы

Et = {2, 5}, Ег = {1, 4}, • Е3 = {1, 3, 5}, Е* = {3, 6}.

Установим свойства графа, определяющие ветвистость синте

зируемого дерева. В рассмотренном примере при построении сле

дующего яруса в каждом корне фиксировалась вершина с макси

мальной степенью. Для устранения повторения пустых подграфов

в дереве пять раз был применен закон поглощения. Зафиксируем

на первом шаге построения дерева вершину не с максимальной

степенью, а с минимальной — вершину «i, s(v 1) < s(u2). По

строив дерево после фиксации вершины Vi (рис. 3.12, а), видим,

что оно проще предыдущего; при его построении закон поглоще

ния использовался только один раз. Если же при построении

§3.5. Устойчивость, покрытия, паросочетания

_________

187

следующего яруса в каждом корне фиксировать вершину с мини

мальной степенью (рис. 3.12,о), то даже без применения закона

Е4= {3, 6}

iJE1={1.4>JE1={2, 5} Е4= {3,6}

0 (

Я3={1,3,5}

Рис. 3.12

поглощения в рассматриваемом примере число висячих вершин

совпадет с числом пустых подграфов.

Приведем алгоритм порождения всех пустых подграфов, в

котором для уменьшения трудоемкости каждый раз будем фикси

ровать вершину с минимальной степенью.

1. Сопоставляем корню синтезируемого дерева заданный граф G.

2. Фиксируем в графе вершину щ с минимальной степенью,

сопоставив ее концу исходящей из корня дуги. Строим |Ги0| исхо

дящих из корня дуг, и конец каждой из них взаимно однозначно

сопоставляем вершине окрестности G(vо).

3. Каждый конец построенных дуг взвешиваем неокрест-

ностью G(va) вершины va графа, сопоставленного рассматрива

емому корню.

4. Считаем конец va построенного яруса корнем нового дерева.

5. Устанавливаем, взвешена ли вершина va символом 0. Бели

ВДт, то переходим к п. 2, если да, то — к п. 6.

6. Пути между концами дуг, исходящих из корня синтезиро

ванного дерева, и висячими вершинами однозначно определяют

пустые подграфы заданного графа.

На основании этого алгоритма можно определить число вну

тренней устойчивости £o(G0 графа G = (V, Г) как максимальную

мощность пустого подграфа £o(G) = max |£7^ | и число вершинного

Покрытия 7t0(G) как разность |F| -eo(G) (согласно теореме 3.14).

Для рассмотренного примера £o(G) = 3, Емлкс = {1, 3, 5};

М<?) = 3, |{2, 4, 6}| = 3.

188

Гл. 3. Теория графов и мографов

Часто в графе требуется определить не максимальное число

вершин, между которыми отсутствуют связи, а наоборот, макси

мальное число попарно смежных вершин.

Плотностью p(G) графа G = (V, Г) называется максималь

ная мощность носителя полного подграфа FMaKC С G

p(G) = таxp(Fi).

Приведенный выше алгоритм порождения пустых подграфов

и закон поглощения после соответствующих изменений можно с

успехом использовать и при определении плотности p(G) гра

фа G.

Приведем алгоритм порождения полных подграфов.

1. Сопоставляем корню синтезируемого дерева заданный

граф.

2. Фиксируем в графе вершину vq с максимальной степенью,

сопоставив ее концу исходящей из корня дуги. Строим |Ги0| исхо

дящих из корня дуг (| Гг?о | — мощность носителя неокрестности

вершины «о). Конец каждой из этих дуг взаимно однозначно со

поставляем вершине неокрестности G(v0).

3. Каждый конец va построенных дуг взвешиваем окрестно

стью G(va) вершины va графа, сопоставленного рассматривае

мому корню.

4. Считаем конец va построенного яруса корнем нового дерева.

5. Устанавливаем, взвешена ли вершина va символом 0. Если

нет, то переходим к п. 2, если да, то — к п. 6.

6. Пути между концами дуг, исходящих из корня синтезиро

ванного дерева, и висячими вершинами однозначно определяют

полные подграфы заданного графа.

Закон поглощения. Если в к-м ярусе дерева вершины Vi

и Vj смежны, поддерево с корнем у, построено и если в подде

реве с корнем Vj появляется дуга с вершиной Vi, то соответ

ствующая ветвь не строится.

Пример 3.8. Найдем распределение полных подграфов в графе G, изобра

женном в верхней половине рис. 3.13. При фиксировании в п. 2 вершины с мак

симальной степенью иа каждом синтезируемом ярусе (рис. 3.13, а) повторения

полных подграфов в дереве ие было. Фиксирование в п. 2 вершины не с макси

мальной степенью в данном случае приводит к повторению полных подграфов.

Фиксирование вершины с минимальной степенью «з, л(из) = 1, при построе

нии второго яруса приводит к повторению полного подграфа Рз = {1, 2, 6}

(рис. 3.13,6); при построении же каждого яруса количество повторений еше

больше возрастает: F\ = {2, 3, 4}, F4 = {4, 5, 6}, F4 = (4, 5, 6} (рис. 3.13,в).

Плотность рассматриваемого графа G равна 3.

Пример 3.9. Найти максимальный поток через сеть G (рис. 3.14,а), если

пропускная способность дуг соответственно равна а = (t<i, «г) — 5, Ь = (wi, d4) —

- 2, с = (vi, 1*з) - 4, d = (v3, t»4) - 3, e = (v3, v5) - 2, k = (Vs, vs) - 4,

m = (d4, не) — 3, n = (d2, не) - 7, p =* (d2, vs) — 2.

§3.5. Устойчивость, покрытия, паросочетания 189

4 б

“ (2. з, 4}в /-,= {4,5,6}

Рис. 3.13

190

Гд.З. Теория графов и мографов

Для определения максимального потока через заданную сеть строим граф

достижимости Gg = (Vg, Ug), каждая вершина которого взаимно однозначно со

ответствует дуге заданного графа G и две вершины соединены ребром тогда и

только тогда, когда соответствующие им дуги входят в путь в исходном графе

G (рис. 3.15, а). Тогда пустой подграф графа достижимости взаимно однозначно

определяет разрез исходной сети. Минимальная сумма пропускных способнос-

Рис. 3.14

тей дуг, вошедших в разрез, согласно теореме 3.10 равна искомому максималь

ному потоку. Используя алгоритм порождения всех пустых подграфов, выделим

их в графе достижимости (рис. 3.15, о) и вычислим пропускную способность раз

реза.

Имеем

Ei = {п, р, Ь, е, of} —7 +2+ 2+2+3 = 16, Е2 = {п, р, Ь, с }—7+2+2+4 = 15,

Ei = {п, р, т , е} — 7 + 2 + 3 + 2 = 14, Ei = {я, к, Ь, of} — 7 + 4 + 2 + 3 = 16,

Еъ — {п, к, т } — 7 + 4 + 3 = 14, Ее = {а, Ь, of, е} — 5+2+ 3+ 2 = 12,

Ei — {а, Ь, с} — 5 + 2 + 4 = 11, Et — {а, т , е} — 5 + 3 + 2 = 10.

Разрез {а, т , е} с минимальной пропускной способностью, равной 10, опре

деляет максимальный поток = 10 через сеть G.

Модифицированной матрицей смежности S называется

дизъюнкция матриц смежности S и единичной диагональной ма

трицы {1, 1, 1}.