ПОИСК Статьи Рисунки Таблицы Основные сведения по теории матриц и теории графов из "Оперативно-календарное планирование" Запись линейных соотношений между большим числом величин значительно упрощается при употреблении символов, принятых в теории матриц, а использование результатов этой теории, равно как и теории графов, позволяет компактно и в ряде случаев более наглядно получить существенные результаты по анализу и расчету ХТС, в частности по расчету производственной мощности. [c.38] Приведем некоторые, необходимые для понимания дальнейшего изложения, сведения из теории матриц и теории графов, имея в виду, разумеется, не столько подмену многочисленных руководств и пособий [5, 7, 12, 22, 28, 30, 42, 58], сколько уточнение используемых терминов и ввод обозначений, применяемых в этой книге. [c.38] Матрицу — прямоугольную таблицу из т X п элементов — будем обозначать прямой прописной буквой, нанример В = ДЦ. Матрица, состоящая из одного столбца или одной строки, может рассматриваться как вектор. В дальнейшем мы будем оперировать в основном с векторами-столбцами. [c.38] Транспонированием матрицы называется такое ее преобразование, при котором -тый столбец матрицы становится ее г-той строкой, а у-тая строка — /-тым столбцом. Трансионированную матрицу В будем обозначать через В. Вектор-столбец а в результате транспонирования преобразуется в вектор-строку а. [c.38] Об элементах матрицы, для которых I = /, говорят, что они лежат на главной диагонали матрицы. [c.39] В зависимости от тех или иных значений коэффициентов ац (элементов матрицы А) и составляющих вектора у система (1П.4) может совсем не иметь решения (быть несовместной), иметь единственное решение определенная система) или иметь бесчисленное множество решений неопределенная система). Ответ на этот вопрос может быть дан при помощи понятия ранга матрицы, который равен числу линейно независимых столбцов или строк матрицы. [c.39] Пусть т — число строк матрицы А, а — число ее столбцов. Система (III.4) имеет решение тогда и только тогда, когда совпадают ранги матриц А и В, где В — матрица с т строками и ге + 1 столбцом, из которых первые п столбцов — это столбцы матрицы А, а последний — вектор-столбец у. [c.39] Если система (1П.4) имеет решение и ранг А равен г, то любые f = п — г переменных, не принадлежащих к линейно независимым столбцам, могут получить произвольные значения. Эти нараметры-носят название свободных переменных, а их число называют степенью свободы системы. [c.39] Перейдем теперь к основным понятиям теории графов, используемым в этой книге. [c.39] Число ребер, инцидентных с вершиной, называется степенью вершины. [c.40] Граф называют обыкновенным, если каждая пара вершин в нем соединяется не более чем од [им ребром, в противном случае его называют мулътиграфом. [c.40] Цепь с совпадающими начальной и конечной вершинами называется циклом. Рассматриваемый граф содержит единственный цикл b2 4d3b. [c.40] Если любые две вершины графа соединены между собой по крайней мере одной цепью, то такой граф называется связным. Граф, приведенный на рис. iII-1, является связным. [c.40] Подграфом графа G называют граф, все вершины и ребра которого принадлежат G. Подграфами рассматриваемого графа являются, например, граф, содержащий ребра i и 2 и вершины а, Ъ, с, или граф, содержащий ребра 2, 3, 4, 5 ж вершины Ь, с, d, е. [c.40] Подграф Gi графа G может содержать внутренние вершины, смежные только с вершинами того же подграфа, и внешние, смежные также с вершинами, не принадлежащими G . Так, в подграфе abed имеются три внутренние вершины а, Ъ, с) и одна внешняя (d). Внешние вершины будем называть также вершинами сочленения или полюсами подграфа. [c.40] Граф может быть задан матрицей, элементы которой указывают на отношение между вершинами и ребрами. Одна из матриц, посредством которой может быть задан граф, — матрица инциденций ее строки соответствуют вершинам, а столбцы — ребрам. Элемент этой матрицы равен единице, если ребро т инцидентно с вершиной и, и нулю в противном случае. [c.41] В квадратной матрице смежности А обыкновенного графа и. строки, и столбцы соответствуют вершинам элемент ее равен единице, если вершины соединены ребром, и нулю в противном случае. Элемент матрицы смежности мультиграфа равен числу ребер, соединяющих соответствующие вершины. [c.41] Матрица смежности неориентированного графа симметрична относительно главной диагонали, но для ориентированного графа (см. несколько ниже) это утверждение не справедливо. [c.41] /с-тая степень матрицы смежности А, получаемая повторенным к — 1 раз умножением матриц согласно (111.2), характеризует маршруты длиной к в графе. Если элементы матрицы А образовывать по правилам булевой алгебры, так что каждый из них может быть равен только нулю или единице, то равенство ац единице будет указывать на существование в графе по меньшей мере одного маршрута длиной к между вершинами и и у, а равенство этого элемента нулю — на отсутствие такого маршрута. Если же получать А -тую степень матрицы А по правилам обычной алгебры, то значение элемента а указывает на число маршрутов длины к между вершинами МНУ. [c.41] Вернуться к основной статье