Матричные способы задания графов

Матрицей смежности вершин орграфа называется квадратная матрица п–го порядка (п – число вершин). Строки и столбцы соответствуют вершинам графа, элементы p_ij равны количеству дуг, идущих из i–й вершины в j–ую.

Если орграф состоит из однократных дуг, то матрица состоит из 1 и 0. В случае неориентированного графа ему вместе с ребром (x_i; x_j) принадлежит и ребро (x_j; x_i), поэтому матрица будет симметрической.

Матрица смежности дуг орграфа – это квадратная матрица m–го порядка (m – число дуг). Строки и столбцы соответствуют дугам графа. Элементы q_ij равны 1, если дуга u_i непосредственно предшествует дуге u_j и 0 – в остальных случаях.

Матрицей смежности ребер неориентированного графа является матрица m–го порядка, элементы которой q_ij равны 1, если ребро u_i и ребро u_j имеют общую вершину, и 0 – в остальных случаях.

Матрица инцидентности орграфа – прямоугольная матрица размера nxm, где n – число вершин, m – число дуг. Элементы матрицы

Если граф неориентированный, то его элементы 1 и 0.

Пример 1. Для данного графа составить матрицу смежности вершин и определить полустепени захода и исхода.

Пример 2. По данной матрице построить наглядное изображение графа.

.

Решение. Это симметрическая матрица 4-го порядка с неотрицательными элементами. Следовательно, ее можно изобразить как граф с 4 вершинами.

Т.к. р₁₁=2 => х₁ инцидентна 2 ребрам с началом и концом в х₁ (т.е. петлям).

р₁₂ = 1 => х₁ и х₂ соединены 1 ребром.

р₁₃ = 0 => ребра (х₁, х₃) не существует.

р₁₄ = 3 => 3 ребра (х₁, х₄). И т.д.