Текст книги "Математический аппарат инженера"

Автор книги: Виталий Сигорский

сообщить о нарушении

Текущая страница: 3 (всего у книги 8 страниц)

24. Запишите отношение между элементами множества цифр из задачи 13, выражающееся как «x имеет больше двух общих элементов с y».

25. Пусть x ∈ X, y ∈ Y и A – отношение между элементами множеств X и Y, выражаемое соотношением xAy. Укажите, в каких случаях А можно рассматривать как функцию:

а) X – множество студентов, Y – множество учебных дисциплин, xAy – «x изучает y»;

б) X – множество спортсменов, Y – рост в единицах длины, xAy – «x имеет рост y»;

в) X – множество компонентов электрической цепи, Y– множество узлов цепи, xAy – «x связан с y».

3. Матрицы

1. Матрица как таблица. Матрица – это совокупность чисел или объектов другой природы, расположенных в виде прямоугольной таблицы:

Такая таблица, состоящая из m строк и n столбцов, содержит mn клеток (позиций). При этом говорят, что матрица имеет размер m × n и ее называют ( m × n )-матрицей. Позиция на пересечении i -й строки и j -го столбца называется ij -клеткой.

Числа или любые другие объекты, расположенные в клетках таблицы, называют элементами матрицы. Положение элементов строго фиксировано: в каждой клетке должен располагаться только один элемент и ни одна клетка не должна оставаться свободной.

– 29 -

В общем обозначении элемента a_ij первый индекс i всегда указывает номер строки, а второй – номер столбца. Элемент, расположенный в ij -клетке, называют ij -элементом.

Матрица обозначается одной буквой (часто буквы, обозначающие матриц, набирают жирным шрифтом или снабжают какими-либо дополнительными символами). Однако независимо от принятого способа обозначения матрица всегда является совокупностью таблично упорядоченных элементов. Две матрицы равны, если и только если равны их соответствующие элементы, т.е. А = В при условии a_ij = b_ij (i = 1, 2, ... , n). Ясно, что сравнивать можно только матрицы одного и того же размера, между элементами которых определено отношение равенства.

Матрицы, элементами которых являются вещественные или комплексные числа, называют соответственно вещественными или комплексными. Пусть А – комплексная (m × n)-матрица с элементами a_ij = α_ij + iβ_ij. Матрица A̅ того же размера с элементами a^*_ij = α_ij + iβ_ij называется комплексно-сопряженной с А.

Часто для упрощения нулевые элементы в таблицу не записывают, но при этом имеют в виду, что пустые клетки тоже содержат числа (нули).

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

Матрицы впервые появились в середине прошлого столетия в работах английских математиков А. Кэли и У. Гамильтона. Представление совокупностей элементов в виде матриц и разработанные правила операций над ними оказались весьма плодотворными в математике и нашли широкое применение в физике, технике, экономике. Существенный вклад в разработку общей теории матриц и ее приложений внесли советские математики И. А. Лаппо-Данилевский, А. Н. Крылов, Ф. Р. Гантмахер, М. Г. Крейн.

2. Типы матриц. Матрица может иметь любое количество строк и столбцов (конечное или бесконечное). В дальнейшем при отсутствии оговорок будут рассматриваться конечные матрицы с числовыми элементами.

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

– 30 -

Столбцевую и строчную матрицы называют также векторами и сокращенно обозначают как x = (x₁, x₂, ..., x_n) y = (y₁, y₁, ..., y₁). Обычно из контекста ясно, идет ли речь о векторе-столбце или о векторе-строке. В противном случае используют приведенные выше обозначения.

Матрица, количество строк и столбцов которой одинаково и равно n, называется квадратной матрицей порядка n. Совокупность ii-клеток (i = 1, 2, ..., n) образуют главную диагональ квадратной матрицы. Матрица, все элемента которой вне главной диагонали равны нулю, т.е.

называется диагональной и более кратко записывается D = diag(d₁, d₂, ..., d_n). Если в диагональной матрице d₁ = d₂ = ...= d_n = 1, то имеем единичную матрицу n-го порядка

– 31 -

которая часто обозначается также через 1_n или просто цифрой 1 (не следует принимать это обозначение за число, равное единице).

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

Квадратная матрица зазывается верхней (нижней) треугольной, если равны нулю все элементы, расположенные под (над) главной диагональю:

Диагональная матрица является частным случаем как верхней (А), так и нижней (В) треугольных матриц.

3. Сложение матриц. Сумма двух матриц А и В одинаковых размеров определяется как матрица С тех же размеров, каждый элемент которой равен сумме соответствующих элементов матриц, т.е. C = A +B, если c_ij = a_ij + b_ij. Пример:

Из приведенного определения следует, что операция сложения матриц коммутативна, т.е. А+В = В+А, и ассоциативна, т.е. (А+В)+С = А+(В+С). Она естественным образом распространяется на любое число слагаемых. Очевидно также, что матрица А не изменяется при суммировании ее с нулевой матрицей тех же размеров, т.е. А + 0 = А.

4. Умножение матрицы на число. По определению произведением матрицы А на число α (в отличие от матриц и векторов, числа часто называют скалярами) является матрица С = αА, элементы которой получаются умножением соответствующих элементов матрицы А на это число α, т.е. c_ij = αa_ij. Пример:

– 32 -

Очевидно, справедливы следующие соотношения: α(A + B) = αA +αB; (α + β)A = αA + βA; (αβ)A = α(βA), где A и B – матрицы одинакового размера; α и β – числа (скаляры). Общий множитель элементов можно выносить за знак матрицы, считая его скалярным множителем.

Разность двух матриц одинаковых размеров сводится к уже рассмотренным операциям соотношением A – B = A + (-I)B, т.е. C = A – B, если c_ij = a_ij – b_ij.

5. Умножение матриц. По многим соображениям целесообразно определить эту операцию следующим образом: Произведением матрицы A размера (m × n) на матрицу B размера (n × r) является матрица C = AB размера (m × r), элемент c_ij которой, расположенный в ij-клетке, равен сумме произведений элементов i-й строки матрица A на соответствующие элементы j-го столбца матрицы B, т.е.

Умножение А на В допустимо (произведение АВ существует) если число столбцов А равно числу строк В ( в таких случаях говорят, что эти две матрицы согласуются по форме). Пример:

– 33 -

Для матриц A (m × n) и B(n × m) существует как произведение АВ размера m × m, так и произведение BA размера n × n. Ясно, что при m × n эти произведения не могут быть равными уже вследствие различных размеров результирующих матриц. Но даже при m = n, т.е. в случае квадратных матриц одинакового порядка, произведения АВ и ВА не обязательно равны между собой. Например, для матриц

имеем:

Отсюда следует, что вообще операция умножения матриц не подчиняется коммутативному закону (AB ≠ BA). Если же выполняется соотношение AB = BA, то матрицы А и В называю коммутирующими или перестановочными. Ассоциативный и дистрибутивный законы для матричного умножения выполняются во всех случаях, когда размеры матриц допускают соответствующие операции: (AB)C = A(BC) = ABC (ассоциативностью), A(B + C) = AB + AC и (A +B)C = AC +BC (дистрибутивность умножения слева и справа относительно сложения).

Умножение (m × n) – матрицы А на единичную матрицу m-го порядка слева и на единичную матрицу n-го порядка справа не изменяет этой матрицы, т.е. E_mA = AE_n = A. Если хотя бы одна из матриц произведения АВ является нулевой, то в результате получим нулевую матрицу.

Отметим, что из АВ = 0 не обязательно следует, что А = 0 или В = 0. В этом можно убедиться на следующем примере:

6. Транспонирование матрицы. Преобразование матрицы А, состоящее в замене строк столбцами ( или столбцов строками) при

– 34 -

сохранении их нумерации, называется транспонированием. Полученная в результате такого преобразования матрица называется транспонированной к матрице А и обозначается A^t или A':

Произвольная (m × n) – матрица при транспонировании становится ( n × m ) – матрицей, а элемент a_ij занимает ji – клетку, т.е. a_ij = a^t_ji.

Если матрица (квадратная) совпадает со своей транспонированной, т.е. A = A^t, то она называется симметричной и ее элементы связаны соотношением a_ij = a_ji (симметрия относительно главной диагонали). Матрица, для которой A = -A^t, называется кососимметричной, и ее элементы связаны соотношением a_ij = -a_ji . Она, как и симметричная матрица, всегда квадратная, но диагональные элементы равны нулю, т.е. a_ii = 0 (i = 1, 2, ..., n). Ниже приведены примеры симметричной и кососимметричной матриц:

Ясно, что не все элементы таких матриц могут быть выбраны произвольно. Можно убедиться, что из n² элементов для симметричной матрицы независимыми могут быть только 1/2 n (n + 1), а для кососимметричной -1/2 n (n + 1) элементов.

– 35 -

Комплексно-сопряженная и транспонированная матрица (A)^t называется сопряженной с А и обозначается A*. Матрица, равная своей сопряженной, т.е. A = (A̅)^t = A*, называется эрмитовой. Если A = -(A̅)^t, то А – косоэрмитова матрица.

Легко показать, что транспонирование произведения АВ равно произведению транспонированных матриц, взятых в обратном порядке: (AB)^t = B^tA^t. Дважды транспонированная матрица равна исходной, т.е. (A^t)^t = A.

7. Матричная запись системы линейных уравнений. Первоначально матрицы были введены для упрощения записи систем линейных уравнений, что и обусловило и определение основных матричных операций. Система линейных уравнений:

записывается одним матричным равенством

Действительно, перемножив в правой части равенства ( m × n ) – матрицу на столбцевую матрицу, получим

– 36 -

Из равенства матриц-столбцов следуют равенства для соответствующих элементов, которые совпадают с исходной системой уравнений. Если обозначить

то матричное равенство запишется еще короче

y = Ax.

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

8. Линейные преобразования. Систему уравнений, записанную в начале предыдущего пункта, можно рассматривать как линейное преобразование совокупности величин x₁, x₂, ..., x_n в совокупность y₁, y₂, ..., y_m. Это преобразование полностью определяется коэффициентами a_ij (i = 1, 2, ..., m; j = 1, 2, ..., n). На языке матриц линейное преобразование y = Ax означает преобразование столбца х в столбец у, которое определяется матрицей преобразования А.

Пусть величины x₁, x₂, ..., x_n получаются из некоторой совокупности величин z₁, z₂, ..., z_n посредством линейного преобразования x = Bz, где x и z – столбцы соответствующих величин; В – матрица их преобразования. Тогда формальной подстановкой х в первое матричное уравнение получаем

y = Ax = A(Bz) = (AB)z = Cz,

где C = AB – матрица преобразования величин z и y. К этому же результату можно прийти путем подстановки значений x₁, x₂, ..., x_n из второй системы уравнений в первую с учетом введенного ранее правила умножения прямоугольных матиц.

9. Обратная матрица. В обычной алгебре два числа, произведение которых равно единице, называют взаимно обратными. Число, обратное числу a обозначают через a^-1 и по определению aa^-1 = 1

– 37 -

Аналогично в матричной алгебре две квадратные матрицы, произведение которых равно единичной матрице, т.е. AA^-1 = A^-1A = 1, называют взаимно обратными ( A^-1 обратна A). Однако дальше этого аналогия не проходит.

Выражение a^-1b, где a и b – числа, можно представить как частное от деления b на a, но для матриц такое представление не имеет смысла и в общем случае A^-1B ≠ BA^-1. Поэтому вместо операции деления В на А различают левое частное A^-1B и правое частное BA^-1, которые сводятся к умножению слева или справа на обратную матрицу A^-1.

Способ обращения матрицы проще всего установить, рассматривая решение системы n линейных уравнений с n неизвестными:

В матричной форме эта система уравнений запишется как Ax = q, где А – квадратная матрица n-го порядка, называемая матрицей системы: x и q – столбцевые матрицы неизвестных переменных и свободных членов:

Матричное уравнение Ax = q решается умножением обеих его частей слева на обратную матрицу A^-1 т.е. A^-1Ax = A^-1q в результате получаем x = A^-1q.

В соответствии с правилом Крамера неизвестные x_k(k = 1, 2, ..., n) определяются соотношением:

где Δ – определитель системы уравнений Δ_sk – алгебраические дополнения.

– 38 -

Определитель Δ представляет собой числовую функцию, которая вычисляется по определенным правилам на основании квадратной таблицы, состоящей из коэффициентов системы уравнений

Табличное представление определителя Δ по форме совпадает с матрицей системы уравнений, т.е. состоит из тех же элементов и в том же порядке, что и матрица А. В таких случаях его называют определителем матрицы А и записывают Δ = detA.

Алгебраическое дополнение Δ_sk вычисляется как определитель матрицы, полученной удалением из матицы A s-й строки и k-го столбца, причем этот определитель умножается еще на (-1)^s+k. Величину Δ_sk называют также алгебраическим дополнением элемента a_sk матрицы A. Часто определитель матрицы А обозначается через |A|, а алгебраическое дополнение – через A_sk.

Записав для всех элементов столбцевой матрицы x выражения по правилам Крамера, получим решение системы уравнений в виде:

– 39 -

откуда, сравнивая с A^-1q, имеем

Из полученного выражения следует правило определения обратной матрицы: 1) элементы a_ij данной матрицы A n-го порядка заменяются их алгебраическими дополнениями Δ_ij: 2) матрица алгебраических дополнений транспонируется, в результате чего получаем присоединенную или взаимную матрицу к А ( она обозначается через AdjA); 3) вычисляется определитель Δ матрицы А и присоединенная матрица AdjA умножается на величину, обратную этому определителю.

Обратная матрица существует для матрицы А при условии, что detA ≠ 0. Такие матрицы называются неособенными, в отличие от особенных (вырожденных), определитель которых равен нулю. Ниже вычисление обратной матрицы иллюстрируется примером:

– 40 -

Матрица, обратная произведению двух матриц, равна переставленному произведению матриц, обратных исходным, т.е. (AB)^-1 = B^-1A^-1. Действительно, умножив обе части этого равенства на АВ, приходим тождеству E = B^-1A^-1(AB), так как B^-1(A^-1A)B = B^-1EB = B^-1B =E, где E – единичная матрица n-го порядка.

10. Блочные матрицы. Часто матрицу удобно разбить вертикальными и горизонтальными линиями на блоки которые являются матрицами меньших размеров и при выполнении операций рассматриваются как элементы исходных матриц. Операции над блочными матрицами выполняются по сформулированным выше правилам при условии, что эти операции допускаются размерами соответствующих матриц.

Пусть, например, матрицы А и В разбиты на блоки (жирными линиями) так, чтобы для соответствующих блоков имела смысл операция умножения, т.е.

По правилу умножения прямоугольных матриц можно записать:

Вычислим блоки C₁₁ и C₂₁ матрицы C:

– 41 -

В результате имеем

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

Задачи и упражнения.

1. Любая матрица является прямоугольной таблицей. Справедливо ли обратное утверждение, т.е. можно ли считать всякую прямоугольную таблицу матрицей? Если нет,то какие дополнительные требования выдвигаются с позиций матричной алгебры?

2. Какие из приведенных ниже совокупностей объектов представляют собой матрицы:

3. Укажите, какие из приведенных ниже матриц являются равными между собой (при x=2)%

4. При каком значении x матрицы А и В равны:

5. Найти сумму А + В и разность А – В матриц:

6. Найти произведения АВ и ВА и сравнить полученные результаты для матриц:

– 42 -

7. Проверить дистрибутивность умножения слева А(В + С) = АВ + АС и справа (А + В)С = АС + ВС относительно сложения для следующих матриц:

8. Найти все матрицы, перестановочные с матрицей

9. Каким условиям в общем случае должны удовлетворять элементы квадратных матиц А и В второго порядка, чтобы они были перестановочными (АВ = ВА)? Как выглядят эти условия для случая, когда А симметричная матрица?

10. При каких условиях справедливы матричные соотношения:

(A + B)² = A² + 2AB +B²; (A-B)(A+B) = A² – B²?

11. Каким условиям должны удовлетворять элементы ненулевых квадратных матриц А и В, чтобы АВ = 0?

12. К каким типам относятся матрицы:

13. Построить транспонированную A^t, комплексно-сопряженную A̅ и сопряженную А* для матрицы

14. Показать, что матрица

является эрмитовой. Что можно сказать о диагональных элементах любой эрмитовой матрицы?

15. Какого типа должна быть квадратная матрица А, чтобы она была перестановочной с диагональной матрицей D того же порядка, т.е. чтобы AD = DA?

16. К какому типу относятся треугольные матрицы, если они кроме того: а) симметричные, б) кососимметричные?

17. Показать, что (A̅B̅) = A̅ B̅ и (AB)* = B* A*.

18. Проверить соотношение (AB)* = B*A* для матриц задачи 6в.

19. Показать, что произведение AA^t существует для любой матрицы А и является симметричной матрицей.

– 43 -

20. Для заданных матриц найти обратные и проверить соотношение AA^-1 = 1:

21. Найти матрицы, обратные заданным, и проверить соотношение (AB)^-1 = B^-1A^-1:

22. Дана система уравнений:

Записать эту систему в матричной форме Ax = q, вычислить обратную матрицу А^-1 и записать решение системы.

23. Зависимости между токами и напряжениями четырехполюсника (рис. 6, а) можно представить одной из систем уравнений:

Рис. 6. Соединение четырехполюсника: а – четырехполюсник; б – последовательное соединение; в – параллельное соединение.

а) Записать эти уравнения в матричной форме и установить зависимости между элементами матриц:

б) Показать, что матрица А последовательного соединения четырехполюсников (рис 6. б) равна произведению их матриц A' и A'', т.е. A = A' A'' (в порядке следования).

в) Показать, что матрица Y параллельного соединения четырехполюсников (рис. 6, в) равна сумме их матриц Y' и Y'', т.е. Y = Y' + Y''.

– 44 -

24. Выполнить умножение матриц, воспользовавшись разбиением их на блоки:

Проверить результат непосредственным умножением матриц.

4. Графы

1. Происхождение графов. Многие задачи сводятся к рассмотрению совокупности объектов, существенные свойства которых описываются связями между ними. Например, глядя на карту автомобильных дорог, можно интересоваться только тем, имеется ли связь между некоторыми населенными пунктами, отвлекаясь от конфигурации и качества дорог, расстояний и других подробностей. При изучении электрических цепей на первый план может выступать характер соединений различных ее компонентов – резисторов, конденсаторов, источников и т. п. Органические молекулы образуют структуры, характерными свойствами которых являются связи между атомами. Интерес могут представлять различные связи и отношения между людьми, событиями, состояниями и вообще между любыми объектами.

В подобных случаях удобно рассматриваемые объекты изображать точками, называемыми вершинами, а связи между ними – линиями (произвольной конфигурации), называемыми ребрами. Множество вершин V, связи между которыми определены множеством ребер Е, называют графом и обозначают 0 = (V, Е).

Первая работа по графам была опубликована двадцатилетним Леонардом Эйлером в 1736 г., когда он работал в Российской Академии наук. Она содержала решение задачи о кенигсбергских мостах

Рис. 7. К задаче о кенигсбергских мостах:

а – план города; б – граф.

(рис. 7, а): можно ли совершить прогулку таким образом, чтобы выйдя из любого места города, вернуться в него, пройдя в точности один раз по каждому мосту? Ясно, что по условию задачи не имеет значения, как проходит путь по частям суши а, b, с, d, на которых расположен г. Кенигсберг (ныне Калининград), поэтому их можно представить вершинами. А так как связи между этими частями осуществляются только через семь мостов, то каждый из них изображается ребром, соединяющим соответствующие вершины. В результате

– 45 -

получаем граф, изображенный на рис. 7, б. Эйлер дал отрицательный ответ на поставленный вопрос. Более того, он доказал, что подобный маршрут имеется только для такого графа, каждая из вершин которого связана с четным числом ребер.

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

Однако теория графов как математическая дисциплина сформировалась только к середине тридцатых годов нашего столетия благодаря работам многих исследователей, наибольшая заслуга среди которых принадлежит Д. Кенигу. Значительный вклад в теорию графов внесли советские ученые Л. С. Понтрягин, А. А. Зыкоз, В. Г. Визинг и др.

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

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

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

– 46 -

ребрами – ориентированным графом или короче орграфом (рис. 8, а).

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

Рис. 8. Ориентированный (а) и смешанный(б) графы.

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

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

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

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

– 47 -

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

4. Типы конечных графов.Если множество вершин графа конечно, то он называется конечным графом. В математике рассматриваются и бесконечные графы, но мы заниматься ими не будем, так как в практических приложениях они встречаются редко. Конечный граф G = (V, E), содержащий р вершин и q ребер, называется (р, q)-графом.

Рис. 9. Типы графов:

а – псевдограф; б – полный граф (шестиугольник); в – двудольный граф (биграф).

Пусть V = { v₁, v₂, ..., v_p } и E = { e₁, e₂, ..., e_q } – соответственно множества вершин и ребер (р, q)-графа. Каждое ребро e_k ∈ E соединяет пару вершин v_i ∈ V являющихся его концами (граничными вершинами). Для ориентированного ребра (дуги) различают начальную вершину, из которой дуга исходит, и конечную вершину, в которую дуга заходит. Ребро, граничными вершинами которого является одна и та же вершина, называется петлей. Ребра с одинаковыми граничными вершинами являются параллельными и называются кратными. В общем случае граф может содержать и изолированные вершины, которые не являются концами ребер и не связаны ни между собой, ни с другими вершинами. Например, для (5, 6)-графа на рис. 9, а V={ v₁, v₂, v₃, v₄, v₅ }; Е= {e₁, e₂, e₃, e₄, e₅} ребра e₂ и e₃ параллельны, ребро e₆ является петлей, а v₄ – изолированная вершина.

– 48 -

Число ребер, связанных с вершиной v_i (петля учитывается дважды), называют степенью вершины и обозначают через δ(v_i) или deg (v_i). Так, для графа на рис. 9, а δ(v₁) =1, δ(v₂) = 4 и т. д. Очевидно, степень изолированной вершины равна нулю δ(v₄) = 0). Вершина степени единицы называется концевой или висячей вершиной ( δ(v₁) =1). Легко показать, что в любом графе сумма степеней всех вершин равна удвоенному числу ребер, а число вершин нечетной степени всегда четно. В орграфе различают положительные δ⁺(v_i) и отрицательные δ^-(v_i) степени вершин, которые равны соответственно числу исходящих из v_i и заходящих в v_i дуг. Например, для вершины d орграфа (см. рис. 9, а) имеем δ⁺(d) = 2 и δ^-(d) = 3. Очевидно, суммы положительных и отрицательных степеней всех вершин орграфа равны между собой и равны также числу всех дуг.

Граф без петель и кратных ребер называют простым или обыкновенным. Граф без петель, но с кратными ребрами называют мультиграфом. Наиболее общий случай графа, когда допускаются петли и кратные ребра, называют псевдографом. Так, граф на рис. 7,б – это мультиграф, а на рис. 9, а – псевдограф. Если граф не имеет ребер (Е = ∅), то все его вершины изолированы (V ≠ ∅), и он называется пустым или нульграфом. Простой граф, в котором любые две вершины соединены ребром, называется полным (на рис. 9, б приведен пример полного графа с шестью вершинами). Если множество вершин V простого графа допускает такое разбиение на два непересекающихся подмножества V₁ и V₂ (V₁ ∩ V₂ = ∅ ), что не существует ребер, соединяющих вершины одного и того же подмножества, то он называется двудольным или биграфом (рис. 9, в). Ориентированный граф считается простым, если он не имеет строго параллельных дуг и петель.

Граф, степени всех вершин которого одинаковы и равны r, называется однородным (регулярным) r-й степени. Полный граф с n вершинами всегда однородный степени n-1, а пустой граф-однородный степени 0. Граф третьей степени называют кубическим. Он обладает рядом интересных свойств и, в частности, всегда имеет четное число вершин.

5. Смежность.Две вершины v_i и v_i ∈ V графа G = (V, Е) называются смежными, если они являются граничными вершинами ребра e_k ∈ E. Отношение смежности на множестве вершин графа можно определить, представив каждое ребро как пару смежных вершин, т. е. e_k = (v_i, v_j) k = 1, 2, …, q. Для неориентированных графов такие пары неупорядочены, так что e_k = (v_i, v_j) = (v_j, v_i) а для орграфов – упорядочены, причем и, v_i и v_j означают соответственно начальную и конечную вершины дуги e_k. Петля при вершине v_i , в обоих случаях представляется неупорядоченной парой (v_j, v_i). Ясно, что множество вершин V вместе с определенным на нем отношением смежности полностью определяет граф.

– 49 -

Граф можно представить также матрицей смежности. Строки и столбцы этой матрицы соответствуют вершинам графа, а ее (ij) – элемент равен числу кратных ребер, связывающих вершины v_i и v_j, (или направленных от вершины v_i к вершине v_j, для орграфа). Например, для графов, приведенных на рис. 8, а и 9, а, имеем соответственно следующие матрицы смежности: