Математика для гуманитарных, экологических и экономико-юридических специальностей. Часть 1

161

5.14. Понятие ориентированного графа. Матрица смежности

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

Заменим в орграфе все дуги ребрами — получим граф, который называется основанием данного орграфа. Например, для орграфа, приведенного на рис. 5.36, основанием является граф без стрелок на рис. 5.37.

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

Орграф может содержать и кратные дуги. Пример такого графа приведен на рис. 5.39. Его матрица смежности изображена на рис. 5.40.

Всякий неориентированный граф может быть представлен в виде орграфа. Для этого достаточно все его ребра заменить парами встреч- ных дуг.

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

162

Упражнения

1.(ХХН). Сколько ребер имеет основание орграфа на рис. 5.39?

2.На рис. 5.41 изображены восемь матриц смежности, каждая из которых задает некоторый орграф на четырех вершинах.

Укажите:

(УМБ) несвязные орграфы; (УТВ) орграфы, содержащие петли;

(ЛЯТ) орграфы, содержащие кратные дуги; (ЦАД) орграфы, основания которых — полные графы.

5.15. Степень вершины орграфа

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

Например, для графа на рис. 5.39 имеем:

K = 2 + 1 + 3 + 4 + 2 + 4 + 3 + 1 = 10.

2

164

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

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

Этап 1. Рассмотрим цепь 1-2-3-8. Ее пропускная способность равна двум. Уменьшим на 2 пропускные способности всех дуг цепи 1-2-3-8. Дуги (2-3) и (3-8) удаляем, так как их пропускная способность равна нулю. Таким образом, результатом первого этапа является число n1 = 2, представляющее собой ту часть пропускной способно-

сти сети, которую дает цепь 1-2-3-8.

Этап 2. Рассмотрим цепь 1-2-5-8 (рис. 5.43). Ее максимальная пропускная способность равна 4 (n2 = 4). Уменьшим на 4 пропускные

способности дуг (1-2), (2-5), (5-8). После удаления дуг с нулевой пропускной способностью получим орграф, изображенный на рис. 5.44.

2

Этап 3. Пропускная способность цепи 1-4-5-8 (рис. 5.44) равна двум, т.е. n3 = 2. Удалив дугу (4-5), получаем орграф, приведенный

íà ðèñ. 5.45.

Этап 4. Пропускная способность цепи 1-6-5-8 (рис. 5.45) равна единице, то есть n4 = 1. После удаления дуги (5-8) получим орграф,

представленный на рис. 5.46.

166

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

167

6. Элементы линейной алгебры

6.1.Матрицы и действия над ними

Âнекоторых случаях информацию удобно представлять в виде таблиц чисел. Предположим, например, что четыре завода 1, 2, 3, 4 производят пять наименований продукции, которые также можно пронумеровать числами 1, 2, 3, 4, 5. Символом

обозначим количество продукции с номером k, выпускаемой заводом с номером i. Например, число a34 означает количество продукции с

номером 3, произведенной заводом с номером 4. Тогда выпуск продукции всеми заводами можно представить таблицей вида

содержащей полную информацию о результатах работы всех четырех заводов. Сумма

a11 + a21 + a31 + a14 + a51

показывает количество всей продукции, произведенной первым заводом, сумма

a21 + a22 + a23 + a24

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

Матрицей размера m × n называется любая прямоугольная таблица чисел, содержащая m строк и n столбцов (колонок). Произвольную матрицу размера m × n будем записывать в виде

запись i = 1,m означает, что индекс i принимает значения 1, 2, ..., m (нумерация строк), а запись k = 1,n — индекс k принимает значения

168

1, 2, ..., n (нумерация столбцов). Числа aki называются элементами

матрицы. Ими могут быть любые числа: целые, дробные, положительные, отрицательные, комплексные, а также нуль.

Каждый элемент aki матрицы (6.1) снабжен двумя индексами. Верхний индекс (i) означает номер строки, а нижний (k) — номер столбца, где расположен этот элемент, например элемент a23 íàõî-

дится в третьей строке и втором столбце. Матрица, все элементы которой равны нулю, называется нулевой.

Две матрицы A = aki è B = bki одного размера называются рав-

ными, если равны их элементы, расположенные на одинаковых местах. В случае когда матрицы A è B равны (при этом пишут A = B), òî

a11 = b11, a12 = b12, ..., aki = bki .

Если хотя бы одно из этих равенств нарушается, то A ¹ B.

Матрица, у которой число строк совпадает с числом столбцов, называется квадратной, а число ее строк называется порядком матрицы. Запишем квадратную матрицу порядка n:

..., an1 — побочную. Если в квадратной матрице все элементы, распо-

ложенные выше главной диагонали, равны нулю, то такую матрицу называют треугольной. Квадратную матрицу называют треугольной и в том случае, если нулю равны все элементы, расположенные ниже главной диагонали.

Квадратная матрица вида

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

169

Матрицу размера m × n âèäà

где хотя бы одно из чисел a11, a22, ..., amm отлично от нуля и m < n,

называют ступенчатой или трапецеидальной. Очевидно, что если m = n, то ступенчатая матрица превращается в треугольную.

Рассмотрим следующие операции над матрицами: сложение матриц, умножение матрицы на число и умножение матриц.

Пусть даны две матрицы A = aki è B = bki одного размера. Суммой матриц A è B называется матрица

C = A + B = cki ,

ãäå cki = aki + cki , т.е. чтобы сложить две матрицы, нужно сложить их

элементы, стоящие на одинаковых местах. Например:

Запомним, что складывать можно только матрицы одинакового размера.

Произведением матрицы A = aki на число λ называется матри-

öà B = bki , åñëè bki = λaki . Чтобы умножить матрицу A на число λ,

нужно умножить все ее элементы на это число. В результате полу- чится новая матрица, которую обозначают B = λA = λaki .

170

Будем говорить, что размер матрицы A согласован с размером матрицы B, если число элементов в строке матрицы A равно числу элементов в столбце матрицы B. Иными словами: размер матрицы A согласован с размером матрицы B, если число столбцов матрицы A равно числу строк матрицы B. Если матрица A имеет размер m ´ n, то согласованная с ней по размеру матрица B должна иметь размер n ´ k. При этом числа m è k могут быть произвольными, в том числе

и равными. Заметим, что в общем случае из согласованности размера матрицы A с размером матрицы B не следует согласованность размера матрицы B с размером матрицы A. Лишь в случае когда матрица A имеет размер m ´ n, à B — n ´ m, то согласованным является размер не только матрицы A с размером матрицы B, но и матрицы B с размером матрицы A.

Пусть даны две матрицы A è B, где матрица A имеет размер m ´ n, а матрица B — n ´ l, т.е. число столбцов матрицы A равно

числу строк матрицы B. Произведением матриц A = aki è B = bjs

элемент cqp (стоящий в строке с номером q и столбце с номером p) которой равен сумме всех произведений элементов строки с номером q матрицы A на соответствующие элементы столбца с номером p матрицы B, ò.å.

Решение. Размеры матриц A è B согласованы, так как в матрице A четыре колонки, а в матрице B четыре строки. По формуле (6.2)

находим: