Читать «Математический аппарат инженера» онлайн - страница 30

Граф без петель и кратных ребер называют простым или обыкновенным. Граф без петель, но с кратными ребрами называют мультиграфом. Наиболее общий случай графа, когда допускаются петли и кратные ребра, называют псевдографом. Так, граф на рис. 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 вместе с определенным на нем отношением смежности полностью определяет граф.

- 49 -

Граф можно представить также матрицей смежности. Строки и столбцы этой матрицы соответствуют вершинам графа, а ее (ij) - элемент равен числу кратных ребер, связывающих вершины v_i и v_j, (или направленных от вершины v_i к вершине v_j, для орграфа). Например, для графов, приведенных на рис. 8, а и 9, а, имеем соответственно следующие матрицы смежности:

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