- 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 вместе с определенным на нем отношением смежности полностью определяет граф.
- 49 -
Граф можно представить также матрицей смежности. Строки и столбцы этой матрицы соответствуют вершинам графа, а ее (ij) - элемент равен числу кратных ребер, связывающих вершины vi и vj, (или направленных от вершины vi к вершине vj, для орграфа). Например, для графов, приведенных на рис. 8, а и 9, а, имеем соответственно следующие матрицы смежности:
Матрица смежности неориентированного графа всегда симметрична а орграфа - в общем случае несимметрична. Неориентированным ребрам соответствуют пары ненулевых элементов, симметричных относительно главной диагонали матрицы, дугам - ненулевые элементы матрицы, а петлям - ненулевые элементы главной диагонали. В столбцах и строках, соответствующих изолированным вершинам, все элементы равны нулю. Элементы матрицы простого графа равны 0 или 1, причем все элементы главной диагонали нулевые.
Для взвешенного графа, не содержащего кратных ребер, можно обобщить матрицу смежности так, что каждый ее ненулевой элемент равняется весу соответствующего ребра или дуги. Обратно, любая квадратная матрица n-го порядка может быть представлена орграфом с n вершинами, дуги которого соединяют смежные вершины и имеют веса, равные соответствующим элементам матрицы. Если матрица симметрична, то она представима неориентированным графом.