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

    d(x₃) = min {∞, 6* + 7} = 13, d(x₅) = min{11, 6* + 6} = 11.

    Шаг 3. min{d(x₂), d(x₃), d(x₅), d(x₆)} = min{9, 13, 11, ∞} = 9* = d(x₂), x” = x₂.

    Шаг 4. x₂ ≠ x₆, возвращение  на второй шаг.

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

    Шаг 2. S” ={x₃}, d(x₃) = min{13, 9* + 8} = 13.

    Шаг 3. min{d(x₃), d(x₅), d(x₆)} = min{31, 11, ∞} = 11* = d(x₅), x” = x₅.

    Шаг 4. x₅ ≠ x₆, возвращение на второй шаг.

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

    Шаг 2. S”={x₆}, d(x₆) = min{∞, 11* + 4} = 15.

    Шаг 3. min {d(x₃), d(x₆)} = min{13, 15} = 13* = d(x₃), x” = x₃.

    Шаг 4. x₃ ≠ x₆, возвращение на второй шаг.

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

    Шаг 2. S” = {x₆}, d(x₆) = min{15, 13* + 9} = 15.

    Шаг 3. min{d(x₆₎} = min{15} = 15*, x” = x₆.

    Шаг 4. x₆ = t = x₆, конец первого этапа.

    Этап 2.

    Шаг 5. Составим множество вершин, непосредственно предшествующих x” = x₆ с постоянными метками S” = {x₃, x₅}. Проверим для этих двух вершин выполнение  равенства d_нов.(x_i) = min{d_стар.(x_i), d(x”) + ω(x”, x_i)}:

    d(x”) = 15 = 11* + 4 = d(x₅) + ω(x₅, x₆),

    d(x”) = 15 ≠ 13* + 9 = d(x₃) + ω(x₃, x₆).

    Включаем  дугу (x₅, x₆) в кратчайший путь. x” = x₅.

    Шаг 6. x” ≠ s = x₁, возвращение на пятый шаг.

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

    Шаг 5. S” = {x₁, x₄}.

    d(x”) = 11 = 0* + 11 = d(x₁) + ω(x₁, x₅),

    d(x”) = 11 ≠ 6* + 6 = d(x₄) + ω(x₄, x₅).

    Включаем  дугу (x₁, x₅) в кратчайший путь. x” = x₁.

    Шаг 6. x” = s = x₁, завершение второго этапа.

    Итак, кратчайший путь от вершины x₁ до вершины x₆ построен. Его длина (вес) равна 15, сам путь образует следующая последовательность дуг: μ = (x₁, x₅) - (x₅, x₆). 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

    1. 7 Алгоритм нахождения максимального пути 

    Для нахождения максимального пути граф G (сеть) должен быть ациклическим, ибо в противном случае может оказаться, что длины некоторых путей не ограничены сверху. Если G_n – ациклический граф, то для любых двух его вершин x_i ≠ x_j выполняется одно из двух условий:

1. x_i предшествует x_j, x_i S_предш (x_j);
2. x_i  следует за x_j, x_i S_след (x_j);
3. нет пути между x_i и x_j.,

    Первое  и второе условия одновременно не выполнимы из-за требуемой ацикличности графа.

    Перед вычислением максимального пути в орграфе необходимо упорядочить  вершины графа по алгоритму Фалкерсона.

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

    Пусть d_j – длина максимального пути от вершины x₁ до вершины x_j, тогда величина d_j удовлетворяет следующим рекуррентным соотношениям (1. 2. 5):

    

    Соотношения (1. 2. 5) позволяют легко вычислить длины максимальных путей от s = x₁ до вершин, достижимых из вершины s. Сами пути могут быть построены методом последовательного возвращения (второй этап в алгоритме Дейкстры).

    Пример 9: Граф (рис. 1.12) задан матрицей весов Ω. Найти максимального  пути из вершины x₁ в x₆ и сам этот путь.

    

    

                                                          Рис. 1. 12

    Этот  граф ациклический, поэтому возможно упорядочение его вершин по алгоритму  Фалкерсона. Сделаем это графическим  способом (рис. 1.13), переобозначив две вершины: x₄ назовём x , а x₃ – x , и применим рекуррентные формулы (1.2.5)

    

                                        Рис. 1. 13

    Этап 1.

    d₁ = 0,

    d₂ = max (d₁ + 4) = 4,

    d = max (d₁ + 6, d₂ + 8) = max (0 + 6, 4 + 8) = 12,

    d = max (d + 8, d₂ + 7) = max (12 + 8, 4 + 7) = 20,

    d₅ =  max (d + 7, d + 9, d2 + 6) = max (20 + 7, 12 + 9, 4 + 6) = 27,

    d₆ = max (d₅ + 3, d + 5) = max (27 + 3, 20 + 5) = 30.

    Итак, длина максимального пути их x₁ в x₆ равна 30.

    Этап 2.

    x₆ : d₆ = 30 = d₅ + 3 = 27 +3 – включаем дугу (x₅, x₆) в максимальный путь, d₆ = 30 ≠ d + 5 = 20 + 5.

    x₅ : d₅ = 27 ≠ d + 7 = 20 + 7 – включаем дугу (x , x₅) в максимальный путь,

    d₅ = 27 ≠ d + 9 = 12 + 9, d₅ = 27 ≠ d₂ + 6 = 4 +6.

    x : d = 20 = d + 8 = 12 + 8 – включаем дугу (x , x ) в максимальны путь,

    d = 20 ≠ d₂ + 7 = 4 +7.

      x : d = 12 = d₂ + 8 = 4 + 8 – включаем дугу (x₂, x ) в максимальный путь,

    d = 12  ≠ d₁ +6 = 0 + 6.

    x₂ : d₂ = 4 = d₁ +4 = 0 + 4 – включаем дугу (x₁, x₂) в максимальный путь.

    Итак, искомый путь таков: μ_max=(x₁, x₂)-(x2, x )-(x , x )-( x , x₅)-(x₅, x₆) или в первоначальных обозначениях μ_max=(x₁, x₂)-(x₂, x₄)-(x₄, x₃)-(x₃, x₅)-(x₅, x₆) 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 

ГЛАВА II. ПРАКТИЧЕСКАЯ ЧАСТЬ 

2. 1. Применение способов задания графов 

    Задача 1. Для графов, изображённых на рисунке 2.1, составить матрицы смежности вершин, смежности дуг и инциденций.

 
 
 
 
 
 
 
 

Рис. 2.1 
 

    Решение задачи 1.

    

а)  
 
 
 
 
 
 
 

      
 
 
 
 
 
 
 
 
 

    Задача 2: По матрице смежности построить наглядное изображение графа. 

    

 
 
 
 
 
 
 
 

    Решение задачи 2:

    

    Рис. 2. 2 
 
 

    Задача  3: Показать, что графы изоморфны (Рис. 2. 3).

 
 
 
 
 
 

    Рис. 2. 3 

    Решение задачи 3: Воспользуемся теоремой и рассмотрим матрицы смежности графов. Заметим, что они равны, следовательно графы являются изоморфными. 

 
 

= А (матрица  смежности первого и второго  графов) 
 
 
 

    Задача  4. Доказать, что графы на рисунке 2. 4 не изоморфны. 

 
 
 

Рис. 2. 4 

Решение задачи 4: Построим матрицы смежности вершин для данных графов. 

  
 

P₄=    P₅= 
 
 
 

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

    Задача 5: Найти матрицу достижимости С для данного графа

     Рис. 2. 5 

    Решение задачи 5:

    Находим матрицу смежности данного графа (рис. 2.5), Р. Затем находим Р², Р³ и Р⁴. Складываем данные матрицы и матрицу Е. Находим матрицу достижимости графа:

    

    Р= Р²= Р³= Р⁴= 

    

    

    В = Е + Р +Р² + Р³ + Р⁴ = С =  
 
 
 
 

    Задача  6. Найти матрицы сильных компонент связи для графа, изображённого на рисунке 2. 6.

     Рис. 2. 6

    Решение задачи 6: Находим матрицу смежности графа, возводим её в степени от 2 до 5. Находим матрицу В, и затем матрицу достижимости и контрдостижимости. Затем, путем перемножения последних двух  матриц, получаем матрицу, по которой определяем сильные компоненты связи.

      
 

    P = P² = P³ =  
 
 
 

      

    P⁴ = P⁵ =  
 
 

      
 

    B = E + P + P² + … + P⁵ = C= L= 
 
 

      
 

    F = C * L =  
 
 

    По  матрице F можно сказать, что граф содержит три сильные компоненты связности. Первая сильная компонента состоит из вершины x₁, вторая сильная компонента из вершины x₂ и третья – из вершин x₃, x₄, x₅.  

    Задача 7: Найти матрицы сильных компонент связи для графа, изображённого на рисунке 2. 7.

    

    Рис. 2. 7 

    Решение задачи 7: Решение аналогично предыдущему заданию. 

      

      Р = Р²= Р³= Р⁴= 
 
 
 

    

     

      В=Е+Р+Р²+Р³+Р⁴= С= L= 
 
 
 

      

    F=C*L= 
 
 
 

    Задача  8. Найти ранг графа, приведённого на рисунке 2. 8.

     Рис. 2. 8 

    Решение задачи 8: Ранг графа равен рангу его  матрицы смежности. Следовательно, построим матрицу смежности данного графа и найдём её ранг, приводя матрицу к ступенчатому виду. 

 

~ ~ ~ 
 
 
 

Ранг полученной матрицы смежности равен 5, тогда  и rangG = 5. 
 

Задача 9: Определить, имеют ли контуры орграфы с матрицами смежности

 

а) б)