Математическая культура. Мациевский С.В. - 45 стр.

    Рассмотрим план города, на всех улицах которого одностороннее дви-
жение. Тогда связность соответствующего орграфа означает, что можно
проехать из любого пункта в любой другой, не обращая внимания на одно-
сторонность движения. А сильная связность означает, что это можно сде-
лать, выполняя правила одностороннего движения.
    Когда карту улиц можно превратить в систему с односторонним дви-
жением так, чтобы можно было проехать из любого пункта в любой дру-
гой? Если город состоит из двух частей, связанных одним мостом, или
имеется тупик, то так сделать нельзя. Но если нет тупиков и таких мостов,
то всегда найдется подходящая система односторонних дорог.
    Мы получили следующую теорему. Связный граф можно превратить в
сильно связный орграф тогда и только тогда, когда каждое ребро графа со-
держится по крайней мере в одном цикле.
    Упр. 5. Превратите граф на рисунке в сильно связный
орграф, нарисовав стрелки на его ребрах. Придумайте и
запишите алгоритм, превращающий любой граф, удовле-
творяющий условию теоремы, в сильно связный орграф.

               п. 2. Матричное исчисление                              ⎛ a11 a12 … a1n ⎞
    1. Матрица — прямоугольная таблица чисел. (m × n)- ⎜ a 21 a 22 … a 2 n ⎟
матрица состоит из m строк и n столбцов чисел aij, где ⎜                                   ⎟
i = 1, 2, , m, j = 1, 2, , n. Для квадратной матрицы m = n, ⎜          ⎜ …     …     … …   ⎟
                                                                         a     a     … a   ⎟
и размер матрицы n называется ее порядком.                             ⎝   m1    m 2    mn ⎠
    В дальнейшем матрицей будет квадратная матрица (n × n). Главная
диагональ матрицы — диагональ с числами aii. Матрица диагональная,
если все числа матрицы, кроме главной диагонали, равны 0. Матрица сим-
метричная, если она симметрична относительно своей главной диагонали.
    Сумма матриц A = (aij) и B = (bij) — матрица C = A + B = (aij + bij). Про-
                                                                      n
изведение A = (aij) и B = (bij) — матрица C = AB = (сij), где сij = ∑ k =1 aikbkj .

   Пример. Пусть A = ⎛⎜ 3 4 ⎞⎟ , B = ⎛⎜ 6
                                 1 2       8     7⎞
                                                  ⎟ . Тогда A + B = ⎛⎜1+ 8 2 + 7 ⎞⎟ = ⎛⎜ 9 9 ⎞⎟ ,
                               ⎝ ⎠       ⎝       5⎠                  ⎝ 3+ 6 4 + 5 ⎠ ⎝ 9 9 ⎠
        1⋅8 + 2⋅6 1⋅7 + 2⋅5 ⎞ ⎛ 20 17 ⎞
AB = ⎛⎜                     ⎟ =⎜      ⎟.
      ⎝ 3⋅8 + 4⋅6 3⋅7 + 4⋅5 ⎠ ⎝ 48 41⎠
                                        −5 2
   Упр. 6. Пусть A = ⎛⎜ 3 5 ⎞⎟ , B = ⎛⎜ 3 −1⎞⎟ , C = ⎛⎜1 1⎞⎟ , O = ⎛⎜ 0 0 ⎞⎟ , E = ⎛⎜ 0 1⎞⎟ . Най-
                       1 2                             11             0 0            1 0
                      ⎝ ⎠             ⎝      ⎠        ⎝ ⎠           ⎝      ⎠        ⎝ ⎠
дите матрицы A + B, B + A, A + O, O + A и AB, BA, AE, EA, AC, CA.
   2. Матрица смежности графа с множеством вершин {v1, v2, , vn} —
квадратная матрица A = (aij) порядка n, в которой элемент aij равен числу
ребер графа, соединяющих vi и vj. Смежная матрица графа симметрична.
   Матрица смежности орграфа с вершинами {v1, v2, , vn} — квадрат-
ная матрица A = (aij) (n × n), где элемент aij равен числу дуг (vi, vj) орграфа.
   Упр. 7. Вычислите три матрицы смежности для двух орграфов и их
графа-основания из примера выше.


                                               44