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

При большом числе элементов рисунок графа теряет наглядность. В таком случае его целесообразно задать матричным способом. Граф можно задать различными матрицами, выбор которых обусловлен особенностями конкретной задачи.

Определение 17. Вершины и графа называют смежными, если они соединены дугой (ребром).

Определение 18. Матрицей смежности вершин орграфа называют квадратную матрицу -го порядка, в которой – число вершин графа; строки и столбцы матрицы соответствуют вершинам графа; элементы матрицы равны числу дуг, направленных из вершины в вершину .

Замечание. Если орграф состоит из однократных дуг, то элементы его матрицы смежности вершин равны либо 0, либо 1. В случае неориентированного графа ему вместе с ребром принадлежит и ребро , поэтому матрица неориентированного графа будет симметрической (то есть ее элементы, симметричные относительно главной диагонали, равны). Справедливо и обратное утверждение: любой симметрической матрице с целыми неотрицательными элементами можно поставить в соответствие неориентированный граф.

Определение 19. Дуги и называют смежными, если дуга входит в вершину , а дуга выходит из нее.

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

Определение 21. Ребра и называют смежными, если они имеют общую вершину.

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

Замечание. Матрица смежности ребер графа является симметрической.

Определение 23. Дугу и вершину называют инцидентными, если вершина является началом или концом дуги .

Определение 24. Ребро и вершину называют инцидентными, если инцидентны вершина и дуга (другими словами, вершина является началом или концом ребра ).

Определение 25. Матрицей инцидентности орграфа называют прямоугольную матрицу размерности , строки которой соответствуют вершинам, а столбцы – дугам орграфа, причем

Замечание. В случае неориентированного графа элементами матрицы инцидентности будут только числа 0 и 1.

Таким образом, всякий граф можно задать одной из матриц смежности или матрицей инцидентности.

Пример 36.3. Для графа, изображенного на рис 36.5, найти матрицу смежности вершин, матрицу смежности дуг и матрицу инцидентности.

Решение. Найдем матрицу смежности вершин.Граф, изображенный на рис 36.5, содержит четыре вершины, поэтому матрица смежности его вершин будет четвертого порядка (). На основании определений 17 и 18 найдем значения элементов матрицы . Граф является орграфом и состоит из однократных дуг. Смежными являются вершины и , и , и , и , и , и (так как у вершины есть петля). Поэтому элементы матрицы смежности вершин , , , , и равны единице, а остальные – нулю.

Вычисления удобно проводить с помощью таблицы, у которой строки и столбцы выделенной части заполняют следующим образом: если вершины и являются смежными (соединены хотя бы одной дугой), то на пересечении строки и столбца пишут количество дуг, соединяющих вершины и (элемент ); если же вершины и не являются смежными (не соединены ни одной дугой), то .

Выделенная часть таблицы представляет собой матрицу смежности вершин орграфа. Таким образом, матрица смежности вершин графа имеет вид

.

Найдем матрицу смежности вершин.Всего в данном графе шесть дуг, поэтому матрица смежности дуг орграфа будет порядка . Согласно определениям 19 и 20 перечислим смежные дуги и определим элементы . Смежными дугами при вершине являются дуги и ( входит в вершину , а выходит из нее), поэтому ; а также – дуги и , поэтому . Смежными дугами при вершине являются дуги и , поэтому ; а также – дуги и , поэтому . Смежными дугами при вершине являются дуги и , поэтому ; а также – дуги и , поэтому . Смежными дугами при вершине являются дуги и , поэтому ; а дуга является смежной сама себе, поэтому . Остальные элементы равны нулю.

Вычисления элементов матрицы удобно выполнять в виде таблицы. Таблицу заполняют следующим образом: если две дуги и являются смежными при некоторой вершине , то на пересечении строки и (элемент ) пишут единицу; в противном случае – 0.

							Выделенная часть таблицы представляет собой матрицу смежности дуг графа. Тогда .

Найдем матрицу инцидентности графа. Граф состоит из четырех вершин и шести дуг, поэтому его матрица инцидентности будет иметь размерность . Для вычисления ее элементов заполним вспомогательную таблицу согласно определениям 23 и 25: если дуга заходит в вершину , то на пересечении строки и столбца ставим (–1), элемент ; если дуга исходит из вершины , то на пересечении строки и столбца ставим 1, элемент ; если дуга и вершина никак не связаны, то .

Например, дуга входит в вершину , поэтому .

					–1
	–1
		–1	–1
						–1; 1

Выделенная часть таблицы представляет собой матрицу инцидентности графа. Тогда матрица инцидентности имеет вид .

Ответ. Матрица смежности вершин , матрица смежности дуг , матрица инцидентности .

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

Решение. Матрица смежности вершин графа не является симметрической и не содержит симметрических подматриц, следовательно, данный граф является орграфом (полностью ориентированным). Составим вспомогательную таблицу:

Так как матрица является матрицей смежности вершин и имеет размерность , то граф имеет три вершины. Найдем направления дуг. Так как , то вершина не является смежной сама себе, то есть граф не имеет петли в этой вершине. Так как , то вершину с вершиной соединяют две дуги. Так как , то вершину с вершиной соединяет одна дуга. Так как , то вершину с вершиной соединяет одна дуга. Так как , то вершина является смежной сама себе. Следовательно, граф имеет петлю у вершины . Так как , то вершину с вершиной соединяет одна дуга. Остальные элементы третьей строки равны нулю, то есть других соединений нет. Расположим на плоскости вершины графа и соединим их стрелками, имеющими соответствующие направления. Получим искомый орграф (рис. 36.6).