Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 35
Текст из файла (страница 35)
Для вершины ез с иеоврестнастью ьгз = (ем ез, аэ) страэм третий ярус. Получаем три кориа: аз, ез (ез), ез (аз). Все они усекаются са. гласно аакоиу поглощения и не учитываются при подсчете пустых аодграфов. Таким абрааам, имеем пустые иадграфы Е1 = (2, 5), Ез = (1, 4), ' Ез = (1, 3, $), Ез = (3, 6). Установим свойства графа, определяющие ветвистость синтезируемого дерева. В рассмотренном примере при построении следующего яруса в каждом корне фиксировалась вершина с максимальной степенью.
Для устранения повторения пустых подграфов в дереве пять раз был применен закон поглощения. Зафиксируем на первом шаге построения дерева вершину не с максимальной степенью, а с минимальной — вершину и1, г(и1) ( г(ит). Построив дерево после фиксации вершины о1 (рис. 3.12, я), видим, что оно проще предыдущего; при его построении закон поглощения использовался только один раз.
Если же при построении 3 3.5. Усщобчио ость, покрытию, яаросочсшаиия 187 следующего яруса в каждом корне фиксировать вершину с минимальной степенью (рис. 3.12, б), то даже без применения закона зу лз (1351 а 6 Рис. 3.12 поглощения в рассматриваемом примере число висячих вершин 'совпадет с числом пустых подграфов. Приведем алгоритм порождения всех пустых подграфог, в котором для уменьшения трудоемкости каждый раз будем фиксировать вершину с минимальной степенью. 1. Сопоставляем корню синтезируемого дерева заданный граф С.
2. Фиксируем в графе вершину ио с минимальной степенью, сопоставив ее концу исходящей из корня дуги. Строим )Гио) исходящих из корня дуг, и конец каждой из них взаимно однозначно сопоставляем вершине окрестности С(ио). 3. Каждый конец построенных дуг взвешиваем неокрестностью О(и ) вершины о„графа, сопоставленного рассматриваемому корню. 4. Считаем конец о построенного яруса корнем нового дерева. 5. Устанавливаем, взвешена ли вершина о символом Э. Если плт, то переходим к п. 2, если да, то — к п. 6. 6. Пути между концами дуг, исходящих из корня синтезированного дерева, и висячими вершинами однозначно определяют пустые подграфы заданного графа.
На основании этого алгоритма можно определить число внутренней устойчивости го(О) графа с4 = (У, Г) как максимальную мощность пУстого подгРафа го(С) = шах Щ и число веРшинного покРытиЯ хо(сг) как Разность )Ц вЂ” го(О) (согласно теоРеме 3.14). Для рассмотренного примера го(О) = 3, Е,, = (1, 3, 5); яо(б) = 3, Я2, 4, 6) ! = 3 Гл.3. Теория графов и мографое 188 1 з 3 4 5 Рнс. 3.13 Часто в графе требуется определить не максимальное число вершин, между которыми отсутствуют связи, а наоборот, максимальное число попарно смежных вершин. Плотностью р((') графа С) = (г', Г) называется максимальная мошность носителя полного подграфа гм с С (4 р(0) = шахр(г)).
Приведенный выше алгоритм порождения пустых подграфов и закон поглошения после соответствующих изменений можно с успехом использовать и при определении плотности р((') графа ('. Приведем алгоритм порождения палныг падграфао. 1. Сопоставляем корню синтезируемого дерева заданны й граф. 2. Фиксируем в графе вершину оо с максимальной степенью, сопоставив ее концу исходящей из корня дуги. Строим (Гио~ исходящих из корня дуг ((Гео) — мошность носителя неокрестности вершины ио).
Конец каждой из этих дуг взаимно однозначно сопоставляем вершине неокрестности С)(ио). 3. Каждый конец и построенных дуг взвешиваем окрестностью ('(о ) вершины о графа, сопоставленного рассматриваемаму корню. 4. Считаем конец и построенного яруса корнем нового дерева. б. Устанавливаем, взвешена ли вершина и символом Ы. Если нет, то переходим к п.
2, если да, то — к п. 6. 6. Пути между концами дуг, исходящих из корня синтезированного дерева, и висячими вершинами однозначно определяют полные подграфы заданного графа. 3 а к о н п о г л о ш е н и я. Если о )с-м ярусе дерева вершины сч и и смежны, поддерево е корнем о; построено и гели о поддереве е корнем и. паяоляггпея дуга е вершиной и;, та еаатоететвуюшая вггпоь не строится.
Приме р 3.3. Найдем распределение полных водграфов в графе с», яаебрзненном в верхней половине рнс. 3.13. Прн фнкснрованнн в и. 2 вершнны с мавснмалыюй степенью на каялом сннтеанруемем ярусе (рнс. 3.13,а) повторення полных водграфев в дереве не было. Фнкснрованне в в. 2 вершнныне с максимальной степенью в данном случае врнводнг к повшрению полных подграфов.
Фнкснрованяе вершнны с мвннмальной степенью ев, з(ев) = 1, прн пестрое. ннн второго яруса врнведнт к вевтореншо полного водграфа гв = (1, 2, 6) (рнс. 3.13,6); прн восгроеннн не канзздого яруса количестве певтореннй еше больше возрастает: г» = (2, 3, 4), г» = (4, $, 6), гз = (4, б, 6) (рнс.
Зяз,е). Платность рассматрнваемеге графа гз равна 3. П ример 3.9. Найти максимальный потек череа сеть С (рнс. 3.14, а), если пропускная способность дуг соответственно равна а = (ез, ез) — 3, б = (е», е»)— — 2, с = (еп ез) — 4, »( = (ез, е») — 3, е = (ев, ез) — 2, л = (ев, ез) — 4 ги = (е», ев) — 3, и = (ез, ез) — 7, р = (ез, ез) — 2. $3.8.
Устойчивость, покрытия, иаросочезиания 189 И И (2,3,4) рв (1,2,6) р (4,5,6) П,-(2.4, б) о 4 б 3 4 5 Рг (2 3 4) Рг "(2 4 б) Р» (4 5 б) Р-П,2.6) 2 б Г) (1, 2, б) Г (2, 4, б) Р»-(2,3,4]е Р»и(4,5. 6) Гл. 3. Теория графоа и мографоа 190 Ь ° 4 . У 1 0 1 0 0 1 0 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 0 1 0 0 1 0 1 1 1 1 0 1 1 1 2 б Рис. 3.14 )сО Рис. 3.15 Длн определении максимального потопа через аадвнную сеть строим граф достинимостн Сз — (Рз, 17з), валдая вершина которого ааанмно однозначно соответствует дуге азданйога графа С и лве вершины соединены ребром тогда и только тогда, вогда соответствующие нм дуги вхолят э путь в исходном графе С (рис.
3.15, а). Тогда пустой подграф графа достннимости вааимно оююаначно окределнег разрез исходной сети. Минимальная суьозв пропускных способнос- тей дуг, вошедших э разреа, согласно теореме 3.10 равна искомому максимальнаму потоку. Исвольаун алгоритм ворондения всех пустых водграфов, выделим их в графе достииимости (рис. 3.15, б) и вычислим пропускную способность рззреаа.
Имеем Е1 = (н, р, Ь, е, а)-7+2+2+2+3 = 16, Ез = (н, р, Ь, с)-7+2+2+4 = 15, Ез = (и, р, аг, е) — 7+ 2+3+2 = 14, Ез = (н, Й, Ь, а) — 7+ 4+ 2+ 3 = 16, Ез —— (н, Ь, ш) — 7+ 4+ 3 = 14, Ез = (а, Ь, а, е) — 5 + 2+ 3+ 2 = 12, Ет = (а, Ь, с) — 5 + 2+ 4 = 11, Ез = (а, ш, е) — 5+ 3+ 2 = 10. Равреа (а, аз, е) с минимальной провусвной способностью, равной 10, определнег максимальный катав Ф е = 10 череа сеть С. Модифицированной могнрицей смелсности У называется дизъюнкция матриц смежности Я и единичной диагональной матрицы (1, 1, ..
ч 1). 5 3.5. Устойчивость, накрытия, наросочешания 191 Определение числа внешней устойчивости сводится к построению модифицированной матрицы смежности и выделению покрытия с минимальным числом элементов. Пример 3.10. Определим вершинное числа внешней устойчивости дз(С) графа С (рис. 3.16), мвтрика Я(С) которого имеет следующий вид( Покрываем строки столблами или столбпы стра. Рис. 3.16 вами матрипы сменности, что равиоаначио э силу ее симметричности относительно главной внагоналн. Используя алгоритм Петрика, получаем (а+ с+ у)(Ь+ с+ б+ у)(а+ Ь+ с+ а+ е)(Ь+ с+ а + у)(с+ е+ у) х х (а+ Ь+ а+ е+ у) = (с+ у + ае)(а+Ь+ а+ а+су)(Ь+ с+ а+ у) = = (с+у+ее)(5+а+ос+су+ае+се+ау) = ьз Ьс+ ел+ ас + су" + се + Ьу + аУ + ау + еу+ аЬе + аде.
Кандый мультипликативный член полученного вырвненнн определяет внешне устойчивое мионество вершин; минимальная мощность такого мнонества равна вершинному числу внешней устойчивости рз(С) = 2. В случае ориентированного графа кроме вершинного числа внешней устойчивости,80(гх) графа с' различают положительное ьро+(с) и отуицательное,8 (с4) веРшинные числа внешней Устойчивости. Лолонсительным вершинным числом внешней устойчивости ,но+((я) графа С = = (г', Г) называется минимальная мощность множества вершин Ъ'+ = (о~) такого, что (о,+.) 0 (Го+) = Ь; (3.14) И при удалении хотя бы одной вершины из )г+ соотношение (3.14) Ме выполняется. Это число определяет минимальное количество вершин, из которых наблюдаются (достижимы за один шаг) все 1(аршины графа. Отрицательным вершинным числом внешней усглойчиаости ф (С) графа (4 = (Ъ; Г) называется минимальная мошность мно1дества вершин Ъ' = (о, ) такого, что (ит) О(Г ьог) = Ьг, (3.15) 2Г при удалении хотя бы одной вершины из ьг соотношение (3.15) Фе выполняется.
Это число равно минимальному количеству верМнн, которые наблюдаются всеми вершинами графа. Гл. 3. Теория графов и мографоа 192 1 0 1 0 0 0 0 1 1 0 0 1 0 0 1 1 1 0 О 1 0 1 0 1 0 0 0 0 1 1 1 0 0 0 0 1 Рнс. 3.13 У„(С) = Я,(С) Ч (1, 1, ..., Ц, т з. л. г рбвтаа Очевидно, что число )Уо+(С) вычнслЯетсл как минимальнаЯ мощность покрытия столбцов строками, число,О (С) — как мн нимальная мощность покрытия строк столбцамй в модифицированной матрице смежности У(С) графа С. ПРимеР 3.11, Вычислим числа !Уе (С) и !Уе (С) гРафа С (Рис.
3.17), мо- дифицнрованйвя матрица смежности которого имеет Ь вид а 6 с я е е Согласна апределеншо внешне устойчивого мно. Рис. 3.17 жества, в котором вершины, принадлежащие этому множеству, "изблюдаеьюг самимн собой", диагональные злемеиты Яч матрицы смежности Я(С) имеют аиачение 1, хотя в графе С и отсутствуют петли. Покрывал столбцы строками в модифицированной матрипе смежности с помощью алгоритма Петрика (а+ у)(Ь+ а)(а+ Ь+ с)(с+ а)(с+ е)(Ь+ с!+ е+ У) = = (а + у)(с+ ег1)(Ь+ аа+ ас) = = (а+у)(сЬ+ с(с+ еьа+аеЫ) = = аьс + аос + аде + ЬсУ + сФ + Ъеге', получаем Де (С) = 3. Каждый мулынпликативный член в зтих выражениях определяет саетвегствуюшее внешне устойчивое множество.
Реберное !нсло неэависимости г!(С), число реберного покрытия и!(С) и ребеРмое число внешней устойчивости )У!(С) графа С = (К Г) определяются аналогично, только вместо модифицированной матрицы смежности вершин исходной информацией является модифицированная матрица смежности ребер Ур(С) графа С: где Яр(С) — матрица смежности ребер, 11, 1, ..., 11 — диагональная единичная матрица. Пример 3 12. Найдем е!(С), тг(С) и Д!(С) графа С = (К Г), изображенного в верхней половине рис.
3.13. Для онределения реберного числа неаависнмости ег(С) графа С воспольауемсн алгоритмам нарождения пустых жздграфав. Сопоставнм парню дерева ааданный граф и окределям ребра, смежное с мнннмальным количеством ребер. Эта ребра Ь, аио смежно с тремя ребразас у, р и ш. Сопоставим ребрам Ь, у, р и ш концы исхадяшнх нз корня дерева пуг и вавесим важдую вершину построешюго яруса частичным водграфом, каждое ребра которога ие смежно с ребром, соваставленным зтай вершине (рис. 3.18). Другими словами, азфиксиравав ребро ааданиога графа, сопоставим ему и его окрестности вершины пруса дерева, каждую нз которых завешиваем не окрестностью саответствуюшего $3.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
