Страница 13 из 32
ребрами - ориентированным графом или короче орграфом (рис. 8, а).
Если пара вершин соединяется двумя или большим числом дуг, то такие дуги называют параллельными. При этом две дуги, одинаково направленные по отношению к данной вершине, называют строго параллельными, а различно направленные — нестрого параллельными. Ясно, что нестрого параллельные дуги, отображающие ориентацию связи в обоих направлениях, по существу равноценны неориентированной связи и могут быть заменены ребром. Произведя такую замену в орграфе, придем к смешанному графу, который содержит ребра н дуги (рис. 8, б). Обратно, любой неориентированный или смешанный граф можно преобразовать в ориентированный заменой каждого ребра парой нестрого параллельных дуг.
Рис. 8. Ориентированный (а) и смешанный(б) графы.
Изменив направления всех дуг орграфа на противоположные, получаем орграф, обратный исходному. Если направления дуг орграфа не учитываются и каждая дуга рассматривается как неориентированное ребро, то он называется соотнесенным (неориентированным) графом.
3. Взвешенные графы. Дальнейшее обобщение отображения связей между объектами с помощью графов состоит в приписывании ребрам и дугам некоторых количественных значений, качественных признаков или характерных свойств, называемых весами.
В простейшем случае это может быть порядковая нумерация ребер и дуг, указывающая на очередность при их рассмотрении (приоритет или иерархия). Вес ребра или дуги может означать длину (пути сообщения), пропускную способность (линии связи), напряжение или ток (электрические цепи), количество набранных очков (турниры), валентность связей (химические формулы), количество рядов движения (автомобильные дороги), цвет проводника (монтажная схема электронного устройства), характер отношений между людьми (сын, брат, отец, подчиненный, учитель) и т. п.
Вес можно приписывать не только ребрам и дугам, но и вершинам. Например, вершины, соответствующие населенным пунктам на карте автомобильных дорог, могут характеризоваться количеством мест в кемпингах, пропускной способностью станций техобслуживания. Вообще, вес вершины означает любую характеристику соответствующего ей объекта (атомный вес элемента в структурной формуле, цвет изображаемого вершиной предмета, возраст человека и т. п.).
- 47 -
Особое значение для моделирования физических систем приобрели взвешенные ориентированные графы, названные графами потоков сигналов или сигнальными графами. Вершины сигнального графа отождествляются с некоторыми переменными, характеризующими состояние системы, а вес каждой вершины означает функцию времени или некоторые величины, характеризующие соответствующую переменную (сигнал вершины). Дуги отображают связи между переменными, и вес каждой дуги представляет собой численное или функциональное отношение, характеризующее передачу сигнала от одной вершины к другой (передача дуги). Сигнальные графы находят широкое применение в теории цепей и систем, а также во многих других областях науки и техники.
4. Типы конечных графов.Если множество вершин графа конечно, то он называется конечным графом. В математике рассматриваются и бесконечные графы, но мы заниматься ими не будем, так как в практических приложениях они встречаются редко. Конечный граф G = (V, E), содержащий р вершин и q ребер, называется (р, q)-графом.
Рис. 9. Типы графов:
а - псевдограф; б - полный граф (шестиугольник); в - двудольный граф (биграф).
Пусть V = { v1, v2, ..., vp } и E = { e1, e2, ..., eq } - соответственно множества вершин и ребер (р, q)-графа. Каждое ребро ek ∈ E соединяет пару вершин vi ∈ V являющихся его концами (граничными вершинами). Для ориентированного ребра (дуги) различают начальную вершину, из которой дуга исходит, и конечную вершину, в которую дуга заходит. Ребро, граничными вершинами которого является одна и та же вершина, называется петлей. Ребра с одинаковыми граничными вершинами являются параллельными и называются кратными. В общем случае граф может содержать и изолированные вершины, которые не являются концами ребер и не связаны ни между собой, ни с другими вершинами. Например, для (5, 6)-графа на рис. 9, а V={ v1, v2, v3, v4, v5 }; Е= {e1, e2, e3, e4, e5} ребра e2 и e3 параллельны, ребро e6 является петлей, а v4 - изолированная вершина.
- 48 -
Число ребер, связанных с вершиной vi (петля учитывается дважды), называют степенью вершины и обозначают через δ(vi) или deg (vi). Так, для графа на рис. 9, а δ(v1) =1, δ(v2) = 4 и т. д. Очевидно, степень изолированной вершины равна нулю δ(v4) = 0). Вершина степени единицы называется концевой или висячей вершиной ( δ(v1) =1). Легко показать, что в любом графе сумма степеней всех вершин равна удвоенному числу ребер, а число вершин нечетной степени всегда четно. В орграфе различают положительные δ+(vi) и отрицательные δ-(vi) степени вершин, которые равны соответственно числу исходящих из vi и заходящих в vi дуг. Например, для вершины d орграфа (см. рис. 9, а) имеем δ+(d) = 2 и δ-(d) = 3. Очевидно, суммы положительных и отрицательных степеней всех вершин орграфа равны между собой и равны также числу всех дуг.
Граф без петель и кратных ребер называют простым или обыкновенным. Граф без петель, но с кратными ребрами называют мультиграфом. Наиболее общий случай графа, когда допускаются петли и кратные ребра, называют псевдографом. Так, граф на рис. 7,б - это мультиграф, а на рис. 9, а - псевдограф. Если граф не имеет ребер (Е = ∅), то все его вершины изолированы (V ≠ ∅), и он называется пустым или нульграфом. Простой граф, в котором любые две вершины соединены ребром, называется полным (на рис. 9, б приведен пример полного графа с шестью вершинами). Если множество вершин V простого графа допускает такое разбиение на два непересекающихся подмножества V1 и V2 (V1 ∩ V2 = ∅ ), что не существует ребер, соединяющих вершины одного и того же подмножества, то он называется двудольным или биграфом (рис. 9, в). Ориентированный граф считается простым, если он не имеет строго параллельных дуг и петель.
Граф, степени всех вершин которого одинаковы и равны r, называется однородным (регулярным) r-й степени. Полный граф с n вершинами всегда однородный степени n-1, а пустой граф-однородный степени 0. Граф третьей степени называют кубическим. Он обладает рядом интересных свойств и, в частности, всегда имеет четное число вершин.
5. Смежность.Две вершины vi и vi ∈ V графа G = (V, Е) называются смежными, если они являются граничными вершинами ребра ek ∈ E. Отношение смежности на множестве вершин графа можно определить, представив каждое ребро как пару смежных вершин, т. е. ek = (vi, vj) k = 1, 2, …, q. Для неориентированных графов такие пары неупорядочены, так что ek = (vi, vj) = (vj, vi) а для орграфов — упорядочены, причем и, vi и vj означают соответственно начальную и конечную вершины дуги ek. Петля при вершине vi , в обоих случаях представляется неупорядоченной парой (vj, vi). Ясно, что множество вершин V вместе с определенным на нем отношением смежности полностью определяет граф.