Математический аппарат инженера - [17]

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

- 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 вместе с определенным на нем отношением смежности полностью определяет граф.