Математический аппарат инженера - [17]
Вес можно приписывать не только ребрам и дугам, но и вершинам. Например, вершины, соответствующие населенным пунктам на карте автомобильных дорог, могут характеризоваться количеством мест в кемпингах, пропускной способностью станций техобслуживания. Вообще, вес вершины означает любую характеристику соответствующего ей объекта (атомный вес элемента в структурной формуле, цвет изображаемого вершиной предмета, возраст человека и т. п.).
- 47 -
Особое значение для моделирования физических систем приобрели взвешенные ориентированные графы, названные графами потоков сигналов или сигнальными графами. Вершины сигнального графа отождествляются с некоторыми переменными, характеризующими состояние системы, а вес каждой вершины означает функцию времени или некоторые величины, характеризующие соответствующую переменную (сигнал вершины). Дуги отображают связи между переменными, и вес каждой дуги представляет собой численное или функциональное отношение, характеризующее передачу сигнала от одной вершины к другой (передача дуги). Сигнальные графы находят широкое применение в теории цепей и систем, а также во многих других областях науки и техники.
4. Типы конечных графов.Если множество вершин графа конечно, то он называется конечным графом. В математике рассматриваются и бесконечные графы, но мы заниматься ими не будем, так как в практических приложениях они встречаются редко. Конечный граф G = (V, E), содержащий р вершин и q ребер, называется (р, q)-графом.
Рис. 9. Типы графов:
а - псевдограф; б - полный граф (шестиугольник); в - двудольный граф (биграф).
Пусть V = { v>1, v>2, ..., v>p } и E = { e>1, e>2, ..., e>q } - соответственно множества вершин и ребер (р, q)-графа. Каждое ребро e>k ∈ E соединяет пару вершин v>i ∈ V являющихся его концами (граничными вершинами). Для ориентированного ребра (дуги) различают начальную вершину, из которой дуга исходит, и конечную вершину, в которую дуга заходит. Ребро, граничными вершинами которого является одна и та же вершина, называется петлей. Ребра с одинаковыми граничными вершинами являются параллельными и называются кратными. В общем случае граф может содержать и изолированные вершины, которые не являются концами ребер и не связаны ни между собой, ни с другими вершинами. Например, для (5, 6)-графа на рис. 9, а V={ v>1, v>2, v>3, v>4, v>5 }; Е= {e>1, e>2, e>3, e>4, e>5} ребра e>2 и e>3 параллельны, ребро e>6 является петлей, а v>4 - изолированная вершина.
- 48 -
Число ребер, связанных с вершиной v>i (петля учитывается дважды), называют степенью вершины и обозначают через δ(v>i) или deg (v>i). Так, для графа на рис. 9, а δ(v>1) =1, δ(v>2) = 4 и т. д. Очевидно, степень изолированной вершины равна нулю δ(v>4) = 0). Вершина степени единицы называется концевой или висячей вершиной ( δ(v>1) =1). Легко показать, что в любом графе сумма степеней всех вершин равна удвоенному числу ребер, а число вершин нечетной степени всегда четно. В орграфе различают положительные δ>+(v>i) и отрицательные δ>-(v>i) степени вершин, которые равны соответственно числу исходящих из v>i и заходящих в v>i дуг. Например, для вершины d орграфа (см. рис. 9, а) имеем δ>+(d) = 2 и δ>-(d) = 3. Очевидно, суммы положительных и отрицательных степеней всех вершин орграфа равны между собой и равны также числу всех дуг.
Граф без петель и кратных ребер называют простым или обыкновенным. Граф без петель, но с кратными ребрами называют мультиграфом. Наиболее общий случай графа, когда допускаются петли и кратные ребра, называют псевдографом. Так, граф на рис. 7,б - это мультиграф, а на рис. 9, а - псевдограф. Если граф не имеет ребер (Е = ∅), то все его вершины изолированы (V ≠ ∅), и он называется пустым или нульграфом. Простой граф, в котором любые две вершины соединены ребром, называется полным (на рис. 9, б приведен пример полного графа с шестью вершинами). Если множество вершин V простого графа допускает такое разбиение на два непересекающихся подмножества V>1 и V>2 (V>1 ∩ V>2 = ∅ ), что не существует ребер, соединяющих вершины одного и того же подмножества, то он называется двудольным или биграфом (рис. 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 вместе с определенным на нем отношением смежности полностью определяет граф.
