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

7.9.Рис. 7.8Рис. 7.9Заметим, что подграф графа G, порожденный множеством вершин {v1 , v2 , v5 }, является полным. В соответствии с замечанием 7.3 перенумеруем вершины в графе G так,чтобы вершина v5 в новой нумерации стала вершиной v3 . При этом граф G переходит,например, в граф G , изображенный на рис. 7.10.43Рис. 7.10Применяя к графу G  алгоритм 7.1, получаем раскрашивание вершин, указанноена рис.

7.10, с максимальным номером цвета r  4. Для уменьшения r применяем к графуG  метод ветвей и границ. Пусть GT – дерево возможных решений (раскрасок) для графаG  (аналогичное дереву GT , изображенному на рис. 7.6, являющемуся деревом возможных решений для графа G, изображенного на рис. 7.5). На рис. 7.11 приведен результатобхода части множества вершин дерева GT , т.е на этом рисунке приведено дерево GT1 ,являющееся подграфом дерева GT (ранее на рис.

7.7 аналогичным образом был выделенполужирными и жирными линиями подграф дерева возможных решений GT , соответствующего множеству раскрасок для графа G, изображенного на рис. 7.5). Этот обход произведен в соответствии с правилами (а) и (б), а также с выбранным способом продолженияветвления. На этом рисунке над каждой вершиной последнего 12-го уровня указано значение целевой функции для соответствующей этой вершине раскраски. Соответственно,над каждой вершиной меньшего уровня указана соответствующая этой вершине оценка.Кроме того, на этом рисунке под каждой вершиной дерева GT1 указан номер этой вершины в порядке обхода вершин этого дерева. В соответствии с правилом (б) не осуществляем дальнейшее продолжение цепей после вершин с оценками, большими или равнымидостигнутого текущего рекорда ~p (уточняемого в процессе обхода вершин дерева GT1 ).Такие вершины выделены полужирными кружками.

Оптимальное раскрашивание вершинграфа G , изображенного на рис. 7.10, соответствует цепи, соединяющей единственнуювершину первого уровня дерева GT1 с любой вершиной n -го уровня, с минимальным значением целевой функции для соответствующей этой цепи раскраски.

Она оказалась единственной, помеченной символом  (№38). Таким образом, хроматическим числом графаG  является p(G)  3. Оптимальное раскрашивание вершин графа G  приведено на рис.7.12, а соответствующее ему оптимальное раскрашивание вершин графа G приведено нарис. 7.13 (получается из рис. 7.12 после возвращения к исходной нумерации вершин графаG ).Таким образом, минимальное количество помещений, необходимое для храненияпродуктов 1,2,…,12 со схемой взаимодействия, соответствующей орграфу D, изображенному на рис. 7.8, равно 3.44Рис. 7.11Одно из оптимальных распределений продуктов по помещениям соответствует оптимальному раскрашиванию вершин, приведенному на рис. 7.13.

В первом помещениихранятся продукты 1, 6, 8, 12; во втором – 2, 3, 9, 11; в третьем – 4, 5, 7, 10.Рис 7.12Рис. 7.1345Тема 8. Цикломатическая матрица. Электрические цепи. Уравнения КирхгофаПусть G  (V , X ) – связный граф (в общем случае мультиграф), где V  {v1 ,..., vn },X  {x1 ,..., xm }, например, изображенный на рис. 8.1.Рис. 8.1Рис.

8.2Выделим произвольным образом остовное дерево графа G (например, используяалгоритм 4.1). Для графа G , изображенного на рис. 8.1, одним из возможных остовныхдеревьев является дерево, изображенное на рис. 8.2 (пунктирными линиями изображеныудаленные из G ребра).Тогда, добавляя любое из ребер, не вошедших в остовное дерево графа G (изображенных на рис. 8.2 пунктирными линиями), мы получим граф с некоторым единственнымпростым циклом (см. тему 4, свойство (5) деревьев), проходящим через добавляемое ребро. Всего в остовное дерево не вошли  (G)  m  n  1 ребер (для графа, изображенного нарис.

8.1,  (G)  m  n  1  2 ), а поэтому можем получить таким образом  (G) простыхциклов. Эти циклы различны в том смысле что каждый из них проходит через ребро (тосамое, которое мы добавляли для выделения данного цикла), через которое не проходитни один другой цикл. Они образуют цикловой базис графа G (см. [1, стр. 215]). Для графа, изображенного на рис. 8.1, в цикловой базис войдут циклы: 1  1 ( x3 )  x1 x2 x3 , 2  2 ( x4 )  x1 x2 x4 x5 . См.

изображение этих циклов на рис. 8.3 (при этом внутри циклов ука-зывается выбранное направление обхода ребер в этих циклах; в обоих случаях это направление выбрано по часовой стрелке; возможен выбор и противоположного направления длялюбого из этих циклов).21Рис 8.3Введем произвольным образом ориентацию на ребрах графа G (т.е.

каждое ребро{v, w} X превращаем либо в дугу (v, w), либо в дугу ( w, v) ). В результате каждое ребро~x j превратится в дугу ~x j и соответственно множество ребер X – в множество дуг X , а~сам граф G  (V , X ) – в орграф D  (V , X ). Для графа G , изображенного на рис. 8.1, в ре~зультате введения ориентации на его ребрах получим, например, орграф D  (V , X ), изображенный на рис.

8.4.46Рис. 8.4Цикломатической матрицей графа G с цикловым базисом {1 ,...,  (G ) } называетсяматрица C (G)  [cij ] (G )m (т.е. с  (G) строками и m столбцами) с элементами: cij  1, еслиребро x входит в цикл  и проходится в этом цикле в направлении ~x ; c  1, еслиjjiijребро x j входит в цикл  i и проходится в этом цикле в направлении, противоположном~x j ; cij  0, если ребро x j не входит в цикл  i .Для графа G , изображенного на рис.

8.1, для выделенного ранее циклового базисаэтого графа {1 ,  2 } (см. рис. 8.3) и выбранной ориентацией ребер, соответствующей орграфу D, изображенному на рис. 8.4, цикломатическая матрица имеет видC (G) 1x1x2x3x4x5-11100.011 2 -1 1При построении циклового базиса графа G мы поочередно добавляли к остовномудереву графа G ребра x3 , x4 . Выделим соответствующие этим ребрам столбцы в матрицеС (G) (они помечены символом  ).

Из выделенных столбцов составим матрицу. Ее опре-делитель равен 1, а следовательно, ранг матрицы С (G) равен числу строк, т.е.  (G). Этотфакт не случаен. Выделяя столбцы матрицы С (G), соответствующие добавляемым ребрам, мы всегда получим матрицу, определитель которой равен 1 по абсолютной величине,а следовательно, ранг матрицы С (G) всегда равен  (G), т.е. числу строк.Пусть теперь граф G , изображенный на рис. 8.1, соответствует электрической цепи, изображенной на рис. 8.5, где кружками изображены узлы этой цепи (см. замечание8.1).Рис. 8.5Замечание 8.1.

Будем говорить, что граф G , изображенный на рис. 8.1, являетсяграфом, ассоциированным с электрической цепью, изображенной на рис. 8.5. Аналогичным образом произвольной электрической цепи, состоящей из двухполюсных элементов(сопротивлений, емкостей, индуктивностей, источников тока, напряжений и т.д.) и соеди47ненных проводниками можно поставить в соответствие граф (в общем случае – мультиграф), в котором каждому элементу цепи будет соответствовать ребро графа. Вершиныэтого графа соответствуют узлам электрической цепи (условным точкам соединения проводниками некоторых концов элементов цепи).Выберем произвольным образом направления токов в элементах цепи (условныенаправления; после решения соответствующей системы уравнений знаки при величинахтоков покажут истинные направления токов).

Пусть эти направления соответствуют выбранной ранее ориентации ребер графа G (см. рис. 8.4). Пусть  – некоторый цикл в графе G. Сформулируем уравнение Кирхгофа для напряжений относительно этого цикла:алгебраическая сумма разницы напряжений для элементов электрической цепи, входящихв цикл  , равна нулю. Выпишем систему уравнений Кирхгофа для напряжений относительно выделенных ранее циклов 1 ,  2 :1 :  u1  u2  u3  0  0  0, 2 :  u1  u2  0  u4  u5  0,или, что то же самое,TС (G)U  0, где U  u1 , ... , u5  .(8.1)Таким образом, получили систему из  (G) линейно независимых уравнений Кирхгофа для напряжений.

Можно показать (см., например [1]), что любое уравнение Кирхгофа для напряжений, соответствующее некоторому произвольному циклу графа G , является линейной комбинацией уравнений системы (8.1). Поэтому имеет смысл ограничитьсярассмотрением системы (8.1).Матрица инцидентности. Пусть D  (V , X ) – орграф (в общем случае ориентированный мультиграф), где V  {v1 ,..., vn } , X  {x1 ,..., xm }. Матрицей инцидентности орграфаD называется матрица B( D)  [bij ]nm (т.е. с n строками и m столбцами) с элементами:bij  1, если вершина vi является концом дуги x j ; bij  1, если вершина vi является нача-лом дуги x j ; bij  0, если вершина vi не инцидентна дуге x j .Пример 8.1.

Для орграфа D, изображенного на рис. 8.6,Рис. 8.6матрица B(D) имеет вид:B(D) x1x2x3x4v1-1011v21-10-1v301-1048.Уравнения Кирхгофа для токов. Уравнение Кирхгофа для токов формулируетсяотносительно каждого узла электрической цепи: алгебраическая сумма величин токов,втекающих в данный узел электрической цепи, равна нулю.Для электрической цепи, изображенной на рис. 8.5, совокупность уравнений Кирхгофа для токов имеет вид:узел 1:  i1  i2  0  0  0  0,узел 2: 0  i2  i3  i4  0  0,узел 3: 0  0  0  i4  i5  0,узел 4: i1  0  i3  0  i5  0,или, что то же самоеB( D) I  0, где I  i1 , ...

, i5  ,TB(D) (8.2)x1x2x3x4x5v1-1-1000v201-1-10v30001-1v410101,~B(D) – матрица инцидентности орграфа D  (V , X ) (см. рис. 8.4), полученного ранее в ре-зультате введения ориентации на ребрах графа G (см. рис. 8.1). При этом условные направления токов в элементах электрической цепи, изображенной на рис. 8.5, соответствуют направлениям дуг в орграфе D.Рассмотрим вопрос о числе линейно независимых уравнений Кирхгофа для токов икак их выделить. Очевидно, что если сложить строки матрицы B(D), то получим нулевуюстроку, а следовательно, любое уравнение Кирхгофа для токов является суммой остальных уравнений, взятой со знаком «минус».