Методические указания к выполнению расчетных работ по теории графов и сетей, страница 6

Увеличиваем i на 1 и переходим к шагу 2.Минимальное остовное дерево нагруженного орграфа. Пусть теперь каждомуребру x  X связного графа G  (V , X ) с непустым множеством ребер X поставлено в соответствие действительное число l (x ) – длина ребра x, т.е. граф G является нагруженным. Приведем алгоритм, позволяющий найти остовное дерево графа G с минимальнойсуммой длин содержащихся в нем ребер (по сравнению со всеми другими остовными деревьями графа G ), которое будем называть минимальным остовным деревом (МОД) графа G.Алгоритм 4.2 (выделения МОД нагруженного связного графа G )Шаг 1.

Выбираем в G ребро минимальной длины (если их несколько, то любое). Вместес инцидентными ему вершинами оно образует подграф G2 графа G , являющийся деревом. Полагаем i  2.Шаг 2. Если i  n  n(G), то задача решена и Gi – искомое МОД графа G. В противномслучае переходим к шагу 3.Шаг 3. Строим граф Gi 1 , добавляя к графу Gi новое ребро минимальной длины, выбираемое среди всех ребер графа G , каждое из которых инцидентно какой-нибудь вершинеграфа Gi и одновременно инцидентно какой-нибудь вершине графа G , не принадлежащей Gi .

Вместе с этим ребром включаем в Gi 1 и инцидентную ему вершину, не принадлежащую Gi . Увеличиваем i на 1 и переходим к шагу 2.Замечание 4.1. Пусть граф G (см. рис. 4.2)Рис. 4.2соответствует множеству важных пунктов некоторого города (вокзалы, торговые центры,деловые центры, большие предприятия и т.д.). Нужно соединить эти пункты сетью дорог(например, сетью метрополитена) такой, чтобы было возможно сообщение между любыми двумя пунктами, т.е.

выделить связный подграф графа G , содержащий все его вершины. Пусть, далее величины, указанные на ребрах, соответствуют стоимостям строитель26ных работ (т.е. граф G является нагруженным). Тогда, если выделить МОД графа G , томы получим проект с минимальной общей стоимостью строительных работ.Разбор типового варианта.

Выделить МОД графа G , изображенного на рис. 4.2.Решение. Согласно алгоритму 4.2 выбираем ребро {v1 , v5 } минимальной длины 1. Выделяем его жирной линией (см. рис. 4.2). Далее выбираем ребро минимальной длины, соединяющее либо v1 , либо v5 с какой-нибудь новой (т.е. отличной от v1 ,v5 ) вершиной графаG (т.е.

выбираем среди ребер {v1 , v2 }, {v5 , v6 }, {v5 , v9 } ). Минимальную длину имеет ребро{v1 , v2 }. Выделяем его жирной линией (см. рис. 4.2). Далее выбираем ребро минимальнойдлины, соединяющее либо v1 , либо v2 , либо v5 с какой-нибудь новой вершиной графа G(т.е. выбираем среди ребер {v2 , v3 }, {v2 , v6 }, {v5 , v6 }, {v5 , v9 } ). Минимальную длину имеетребро {v2 , v3 } . Выделяем его жирной линией (см. рис.

4.2). Следующим ребром минимальной длины среди всех возможных является {v2 , v6 }, затем {v6 , v7 } и т.д. Действуя такимобразом, выделяем МОД графа G (см. на рис. 4.2 подграф графа G , ребра которого выделены жирными линиями).Тема 5. Внутренняя и внешняя устойчивость в графах. Ядра графаВнутренняя устойчивость в орграфах. Пусть задан орграф D  (V , X ).

Множество вершин U  V называется внутренне устойчивым, если v U U  D(v)  , т.е. ворграфе D не существует дуги, инцидентной каким-либо двум различным вершинам изU . Внутренне устойчивое множество вершин U  V называется максимальным, если, добавляя к U любую вершину v V \ U , получаем множество, не являющееся внутреннеустойчивым. Часто при решении практических задач требуется найти внутренне устойчивые множества с максимальным числом вершин. Их следует искать среди максимальныхвнутренне устойчивых множеств вершин.Обозначим через  (D) совокупность всех максимальных внутренне устойчивыхмножеств вершин орграфа D.

Тогда число  ( D)  max | U | называется числом внутренU  ( D )ней устойчивости орграфа D.Пример 5.1. Для орграфа D, изображенного на рис. 5.1,Рис. 5.1максимальными внутренне устойчивыми множествами вершин являются: {v1 , v3 }, {v2 , v4 };множество {v1 , v2 } не является внутренне устойчивым; множество {v1} является внутренне устойчивым, но не максимальным.27Метод Магу отыскания семейства максимальных внутренне устойчивыхмножеств вершин орграфа D.

Пусть D  (V , X ) – орграф, где X  , V  {v1 ,..., vn },A  A( D)  [aij ]nn – матрица смежности орграфа D. Составим формулу логики высказыва-ний F (Y1 ,...,Yn )  & (Yi  Y j ), где Y1,..., Yn – высказывательные переменные и под записьюaij 1" aij  1" понимается множество всех пар  i, j  таких, что i, j {1,2,..., n}, aij  1.Применяя дистрибутивность & относительно , приводим F к дизъюнктивнойнормальной форме (кратко, ДНФ; см. [1, стр. 37]), а затем сокращаем ее до тех пор, покаэто возможно, используя равносильности:A  A  (A&B), A  A  A, A  A&A,(5.1)где A, B – произвольные формулы логики высказываний. В результате получим формулуF1 (равносильную F ), находящуюся в ДНФ, каждому дизъюнктивному члену Yi1 &...&Yikкоторой соответствует максимальное внутренне устойчивое множество вершинV \ {vi1 ,..., vik }.Замечание 5.1. Перед приведением формулы F к ДНФ часто оказывается целесообразным упростить формулу F , воспользовавшись равносильностями:A  A&A, ( A  B)&( A  C)&...&( A  D)  A  ( B&C&...&D),(5.2)где A, B, C, D – произвольные формулы логики высказываний.Внутренняя устойчивость в неориентированных графах.

Внутренне устойчивыемножества вершин аналогично можно определить и для неориентированного графаG  (V , X ), а именно: множество вершин U  V называется внутренне устойчивым, еслиv U U  G(v)  , где G(v)  {w V | {v, w}  X }, т.е. никакие две вершины из U не являются смежными. Нетрудно видеть, что если графу G  (V , X ) поставить в соответствиеорграф D с множеством вершин V , заменяя каждое ребро {v, w} графа G на любуюдугу из (v, w), (w, v) (или на обе эти дуги), то в получаемом таким образом орграфе совокупность внутренне устойчивых множеств вершин совпадает с совокупностью внутреннеустойчивых множеств вершин графа G.

Но тогда и совокупность максимальных внутренне устойчивых множеств вершин графа G совпадает с совокупностью максимальныхвнутренне устойчивых множеств вершин орграфа D, а следовательно, для их отысканияможно воспользоваться методом Магу, применяя его к орграфу D.Разбор типового варианта.

Используя метод Магу, определить: (а) совокупностьмаксимальных внутренне устойчивых множеств вершин орграфа D, изображенного нарис. 5.2, а также число  (D).Решение. Составим матрицу смежности A  A( D)  [aij ]55 (см. табл. 5.1).01A(D )  100Рис. 5.2010001001100100Табл. 5.12801000Согласно методу Магу имеем:& (Yi  Y j )  (Y1  Y3 )&(Y2  Y1 )&(Y2  Y4 )&(Y2  Y5 )&(Y3  Y1 )&(Y3  Y4 )&(Y4  Y2 )&(Y5  Y2 ) aij 1(упрощаем полученную формулу, используя (5.2), и опускаем символ & ) (Y1  Y3 )(Y1  Y2 )(Y2  Y4 )(Y2  Y5 )(Y3  Y4 )  (Y1  Y2Y3 )(Y2  Y4Y5 )(Y3  Y4 ) (приводим полученную формулу к ДНФ, используя дистрибутивность & относительно, и упрощаем ее, используя равносильности (5.1)) (Y1Y2  Y2Y3  Y1Y4Y5  Y2Y3Y4Y5 )(Y3  Y4 )  Y1Y2Y3  Y1Y2Y4  Y2Y3  Y2Y3Y4  Y1Y3Y4Y5  Y1Y4Y5  Y2Y3Y4Y5  Y2Y3Y4Y5  Y1Y2Y4  Y2Y3  Y1Y4Y5 .Таким образом, мы получили формулу, находящуюся в ДНФ.

Дальнейшее ее сокращение с использованием равносильностей (5.1) невозможно, а следовательно, искомыми максимальными внутренне устойчивыми множествами вершин орграфа D являются:{v3 , v5}, {v1 , v4 , v5}, {v2 , v3}, и при этом  ( D)  3.Внешняя устойчивость в орграфах. Пусть задан орграф D  (V , X ). Множествовершин U  V называется внешне устойчивым, если v V \ U U  D(v)  , т.е. длялюбой вершины v V , не принадлежащей U , найдется дуга в орграфе D, исходящая изv и заходящая в одну из вершин множества U . Внешне устойчивое множество вершинU  V называется минимальным, если после удаления из U произвольной вершины получаем множество, не являющееся внешне устойчивым.

Часто при решении практическихзадач требуется найти внешне устойчивые множества с минимальным числом вершин. Ихследует искать среди минимальных внешне устойчивых множеств вершин.Пример 5.2. Для орграфа D из примера 5.1 множества вершин {v1 , v3 }, {v2 , v4 } являются внешне устойчивыми, а множество {v1 , v2 } таковым не является, посколькуv3 {v1 , v2 }, но при этом (v3 , v1 )  X , (v3 , v2 )  X . Докажите, что {v1 , v3 }, {v2 , v4 } – мини-мальные внешне устойчивые множества вершин.Обозначим через  (D) совокупность всех минимальных внешне устойчивых множеств вершин орграфа D. Тогда число  ( D)  min | U | называется числом внешней усU  ( D )тойчивости орграфа D.Метод Магу отыскания семейства минимальных внешне устойчивых множеств вершин орграфа D.

Пусть D  (V , X ) – орграф, где V  {v1 ,..., vn }. Составим форnмулу логики высказываний F (Y1 ,..., Yn )  &(Yi i 1Y)aij 1j(здесь при каждом фиксированномi под записью " aij  1" понимается множество всех j {1,2,..., n} таких, что aij  1 ). Применяя дистрибутивность & относительно , приводим F к ДНФ, а затем сокращаем еедо тех пор, пока это возможно, используя равносильности (5.1). В результате получаемформулу F1 , равносильную F , находящуюся в ДНФ, каждому дизъюнктивному членуYi1 &Yi2 &...&Yik которой соответствует минимальное внешне устойчивое множество вершин{vi1 , vi2 ,..., vik }.Замечание 5.2. Перед приведением формулы F к ДНФ часто оказывается целесообразным упростить формулу F , применяя равносильности (5.2), а также29A&( A  B)  A.(5.3)Внешняя устойчивость в неориентированных графах.

Внешне устойчивыемножества вершин можно аналогичным образом определить и для неориентированногографа G  (V , X ), а именно: множество U  V называется внешне устойчивым, еслиv V \ U U  G(v)  , т.е. любая вершина v V , не принадлежащая U , являетсясмежной с какой-нибудь вершиной из U . Нетрудно видеть, что если графу G  (V , X )поставить в соответствие орграф с множеством вершин V , заменяя каждое ребро {v, w}графа G на две дуги (v, w), (w, v), то в получаемом таким образом орграфе D совокупность внешне устойчивых множеств вершин совпадает с совокупностью внешне устойчивых множеств вершин графа G (поскольку в этом случае v V G(v)  D(v) ).

Но тогда исовокупность минимальных внешне устойчивых множеств вершин графа G совпадает ссовокупностью минимальных внешне устойчивых множеств вершин орграфа D, а следовательно, для их отыскания можно воспользоваться методом Магу (применяя его к орграфу D ). При этом, очевидно, используемая в алгоритме матрица A(D) полностью совпадает с A(G). Таким образом, метод Магу без изменений переносится и на неориентированные графы.Разбор типового варианта (продолжение).