Математический аппарат инженера - страница 22
и 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 вместе с определенным на нем отношением смежности полностью определяет граф.
- 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 × q, строки которой соответствуют вершинам, а столбы - ребрам. Для неориентированного графа элементы этой матрицы определяются по следующему правилу: ij-элемент равен 1, если вершина v>i, инцидентна ребру e>i, и равен нулю, если v>i, и e>i, не инцидентны.
- 50 -
В случае орграфа ненулевой ij-элемент равен 1, если v>i начальная вершина дуги e>i, и равен - 1, если v>i - конечная вершина дуги e>i.
Например, матрица инцидентности графа, приведенного на Рис. 9, а, имеет вид:
Каждый столбец матрицы инцидентности содержит обязательно два единичных элемента (для орграфа эти элементы всегда имеют различные знаки и равны соответственно 1 и —1). Количество единиц в строке равно степени соответствующей вершины (для орграфа количество положительных единиц определяет положительную степень, а количество отрицательных единиц — отрицательную степень). Нулевая строка соответствует изолированной вершине, а нулевой столбец - петле.