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

Сигорский Виталий Петрович

Рис. 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, а, имеем соответственно следующие матрицы смежности:

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

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

6. Инцидентность. Если вершина v_i, является концом ребра e_k то говорят, что они инцидентны: вершина v_i инцидентна ребру e_k и ребро e_k, инцидентно вершине v_i. В то время как смежность представляет собой отношение между однородными объектами (вершинами), инцидентность — это отношение между разнородными объектами (вершинами и ребрами). При рассмотрении орграфов различают положительную инцидентность (дуга исходит из вершины) и отрицательную инцидентность (дуга заходит в вершину).

Рассматривая инцидентность вершин и ребер (p и q) - графа, можно представить его матрицей инцидентности размера p x q, строки которой соответствуют вершинам, а столбы - ребрам. Для неориентированного графа элементы этой матрицы определяются по следующему правилу: ij-элемент равен 1, если вершина v_i, инцидентна ребру e_i, и равен нулю, если v_i, и e_i, не инцидентны.

– 50 -

В случае орграфа ненулевой ij-элемент равен 1, если v_i начальная вершина дуги e_i, и равен - 1, если v_i– конечная вершина дуги e_i.