Матрицы в теории графов

       
 
 

А =     
 

– симметричная матрица порядка d + 1, все элементы которой, за исключением двух ближайших к главной диагонали полос, равны нулю. Минор порядка d матрицы А, остающийся после вычёркивания первого столбца и последней строки, равен единице. Следовательно, rank G = rank P(G) ≥ rank A ≥ d = d(G), т. е. rank = G d(G). 

      Вершина x называется центральной, если e(x) = r(G). Множество всех центральных вершин графа называется его центром. Центром может быть единственная вершина графа или несколько вершин (рис. 1.7). Здесь e(x₁)=e(x₂)=e(x₄)=e(x₆)=3, e(x₃) = e(x₇) = 4, e(x₅) = 2. Таким образом, d(G) = 4, R(G) = 2. Периферийные вершины: x₃ и x₇, диаметральные цепи: x₃ – x₂ – x₅ – x₆ – x₇ и x₃ – x₄ – x₅ –x₆ –x₇, центральная вершина x₅.

       
 
 
 
 
 

Рис. 1.7 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     1.4 Выявление маршрутов с заданным количеством рёбер 

     С помощью матрицы смежности вершин можно найти все маршруты, содержащие заданное количество рёбер (дуг). Справедлива  следующая теорема.

     Теорема: Для определения количества маршрутов, состоящих из k рёбер (дуг), необходимо возвести в k-ую степень матрицу смежности вершин. Тогда элемент p даст количество маршрутов длины k (состоящих из k рёбер) из вершины x_i в вершину x_j.

     Доказательство: Используем индукцию по k. Для k = 1 маршрут длины 1 как раз является ребром G,  следовательно,  результат теоремы при  k = 1 вытекает из определения матрицы смежности А. Пусть результат имеет место для k - 1.

                       (A^{(k - 1)})_ij = L_ij, (A)_ij = a_ij, тогда

                                              n

                       (A^k)_ij = (A^{(k - 1)}*A)_ij = SUM L_iq * a_qj.

                                             q=1

         где L_iq - число маршрутов длины (k-1) от v_i к v_q, a_qj - число маршрутов длины 1 от v_q к v_j.

         Следовательно, L_iq * a_qj - число маршрутов длины k из v_i в v_j, где vq - предпоследняя вершина маршрута. Отсюда следует, что n SUM L_iq * a_qj есть число маршрутов длины k от v_i к v_j. q = 1 

     Пример 5. Рассмотрим  неориентированный  граф, изображенный ниже (Рис. 1.8).

       

     Рис. 1.8 
 

     Составим матрицу смежности вершин и возведем ее  в  квадрат.

       Результат возведения:

     

           =    
 

    Рассмотрим первую строку. Элемент p = 3. Это значит,  что существуют три маршрута из А в А длиной два ребра. Действительно, это маршруты Au₁Bu₁A, Au₂Cu₂A, Au₃Du₃A. Из А  в B существуют два маршрута: Au₂Cu₅B, Au₃Du₄B. Если использовать числовую матрицу смежности вершин, то для нахождения самих маршрутов необходимо работать с графом. Если же воспользоваться модифицированной матрицей смежности, в ячейки которой записаны названия ребер, то можно получить не только количество маршрутов, но и сами маршруты.

    Действительно, для данного примера имеем: 

           

                            = 

      
 
 
 
 

    Аналогично  обстоит дело и с орграфом. У  него матрица смежности вершин несимметрическая.

    Пример 6: Рассмотрим следующий орграф (Рис. 1.9) и определим все маршруты с тремя ребрами.

      
 
 

    Рис. 1.9

    Матрица смежности и результаты ее возведения в квадрат и куб находятся ниже.

 

    P² =  =  

      

    P³ =  =  
 

    Рассмотрим  элемент p после возведения  матрицы смежности вершин в квадрат. p = 2, то есть из вершины В в вершину В есть два маршрута длиной две дуги.  Это  маршруты и Bu₃Cu₄B и Bu₂Au₁B. После возведения матрицы в куб сохраняется та же картина. Например, p = 2; это значит, что есть два маршрута длиной три дуги из вершины А в вершину В. Это маршруты Au₁Bu₂Au₁В и Au₁Bu₃Сu₄В. Для получения цепей (маршрутов, в которых каждое ребро встречается один раз) нужно в модифицированной матрице P³ вычеркнуть те слагаемые, в которых какой-либо сомножитель встречается более одного раза. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

1. 5  Определение экстремальных путей на графах. Метод

    Шимбелла

    Введем, следуя Шимбеллу, специальные операции над элементами матрицы смежности вершин, позволяющие находить кратчайшие или максимальные пути между вершинами, состоящие из заданного количества ребер. Эти операции таковы.

    1). Операция умножения двух величин  a и b при возведении матрицы в степень соответствует их алгебраической сумме, то есть

      

                  (1. 5. 1)

     2). Операция сложения двух величин  a и b заменяется выбором из этих величин минимального (максимального) элемента, то есть

                                  (1. 5. 2)

    нули  при этом игнорируются. Минимальный  или максимальный элемент выбирается из ненулевых элементов. Нуль в результате операции (1.5.1) может быть получен лишь тогда, когда все элементы из выбираемых – нулевые.

    С помощью этих операций длины кратчайших или максимальных путей между всеми вершинами определяются возведением в степень весовой матрицы Ω, содержащей веса рёбер. Например, элементы матрицы Ω² вычисляют следующим образом:

    ω = min (max){( ω + ω ), (ω + ω ), …, (ω + ω )}.

    Аналогично  находят элементы k-ой степени матрицы Ω.

    Пример 7: Составим для указанного графа (Рис 1. 10) матрицу весов. Она определяет все  маршруты, состоящие из одного ребра. Найдем кратчайшие  пути  из двух ребер, для этого возведем эту матрицу в квадрат с учетом операций Шимбелла (min – кратчайшие пути).

      
 
 

    Рис. 1. 10 

      
 

    Например: ω = min{( ω + ω ), (ω + ω ), (ω + ω ), (ω + ω )} = min{(0 + 0), (1 + 2), (3 + 0), (2 + 0)} = min {0, 3, 0, 0} = 3.

    Аналогично, кратчайшими путями из трёх рёбер  будут

      
 
 

    и так далее. Например, длина кратчайшего  пути из трёх рёбер из вершины D в вершину С равна 7. это путь DBAC. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

    1. 6. Нахождение кратчайших путей. Алгоритм Дейкстры. 

    Для начала рассмотрим алгоритм Фалкерсона (графический способ упорядочивания элементов):

1. Найти вершины графа, в которые не входит не одна дуга. Они образуют первую группу. Пронумеровать вершины группы в произвольном порядке.
2. Вычеркнуть все пронумерованные вершины и дуги, из них исходящие. В получившемся графе найдется, по крайней мере, одна вершина, в которую не входит ни одна дуга. Этой вершине, входящей во вторую группу, присвоить очередной номер, и т. д. Второй шаг повторять до тех пор, пока не будут упорядочены все вершины.

    Теперь  рассмотрим алгоритм нахождения кратчайшего пути между двумя заданными  вершинами в ориентированном графе. Пусть G = {S, U, Ω } – ориентированный граф со взвешенными дугами. Обозначим s-вершину – начало  пути и t-вершину -  конец пути.

    Алгоритм  Дейкстры содержит одно ограничение  - веса дуг должны быть положительными. Сам алгоритм состоит из двух этапов. На первом находится длина кратчайшего пути,  на втором строится сам путь от вершины s к вершине t.

    Этап 1. Нахождение кратчайшего пути.

    Шаг 1. Присвоение  вершинам начальных меток.

    Полагаем  d(s)=0* и считаем эту метку постоянной (постоянные метки помечаются сверху звёздочкой). Для остальных вершин x_i S, x_i ≠s полагаем d(x_i) = ∞ и считаем эти метки верными. Пусть x” = s, x” – обозначение текущей вершины.

    Шаг 2. Изменение меток.

    Для каждой вершины x_i с временной меткой, непосредственно следующей за вершиной x”, меняем ее метку в соответствии со  следующим правилом:

    d_нов.(x_i) = min{d_стар.(x_i), d(x”)+ω(x”, x_i)}.  (1. 6. 1)

    Шаг 3. Превращение метки из временной в постоянную.

    Из  всех вершин с временными  метками  выбираем вершину x_j* с наименьшим значением метки

    d(x_j*) = min {d(x_j) / x_j S, d(x_j) – временная}.    (1. 6. 2)

    Превращаем  эту метку в постоянную  и  полагаем x” = x_j*.

    Шаг 4. Проверка на завершение первого этапа.

    Если  x” = t, то d(x”) – длина кратчайшего пути от s до t. В противном случае происходит возвращение ко второму шагу.

    Этап 2. Построение кратчайшего пути.

    Шаг 5. Последовательный поиск дуг кратчайшего пути.

    Среди вершин, непосредственно предшествующих вершине x” c постоянными метками, находим вершину x_i, удовлетворяющую соотношению

    d(x”) = d(x_i) + ω(x_i, x”).   (1. 6. 3)

    Включаем  дугу (x_i, x”) в искомый путь и полагаем x” = x_i.

    Шаг 6. Проверка на завершение второго этапа.

    Если  x” = s, то кратчайший путь найден – его образует последовательность дуг, полученных на пятом шаге и выстроенных в обратном порядке. В противном случае возвращаемся к пятому шагу. 

    Пример 8: Задана весовая матрица Ω графа G. Найти минимальный путь из вершины x₁ в вершину x6 по алгоритму Дейкстры.

    

    

                      Рис. 1. 11

    На рисунке 1. 11 изображён сам граф по данной матрице весов. Поскольку на данном графе есть цикл между вершинами x₂, x₃ и x₅, то вершины графа нельзя упорядочить по алгоритму Фалкерсона. На рисунке графа временные и постоянные метки указаны над соответствующей вершиной. Итак, распишем подробно работу алгоритма Дейкстры по шагам.

    Этап 1.

    Шаг 1. Полагаем d(x₁) = 0*, x” = x₁,

    d(x₂) =  d(x₃) =  d(x₄) = d(x₅) = d(x₆) = ∞.

    1-ая  итерация.

    Шаг 2. Множество вершин, непосредственно следующих за x” = x1 со временными метками S” = {x₂, x₄, x₅}. Пересчитываем временные метки вершин: d(x₂) = min{∞, 0*, + 9} = 9,

    d(x₄) = min{∞, 0* + 6} = 6, d(x₅) = min{∞, 0* + 11} = 11.

    Шаг 3. Одна из  временных  меток превращается в постоянную min{9, ∞, 6, 11, ∞} = 6* = d(x₄), x” = x₄.

    Шаг 4. x” = x₄ ≠ t = x₆,  происходит возвращение на второй шаг.

    2-ая  итерация.

    Шаг 2. S” = {x₂, x₃, x₅}, d(x₂) = min{9, 6* + 5} = 9,