Свойства матриц смежности и инцидентности

Задание графов матрицами

Пример.

Замечание.

1) Далее всюду при подсчете числа вхождений вершин в замкнутый маршрут (путь) начальную и конечную вершины будем считать за одно вхождение этой вершины в маршрут (путь).

2) При замкнутом маршруте (пути) e ₁ e ₂… e_k обычно считается, что последовательности e ₁ e ₂… e_k, e ₂… e_ke ₁, …, e_ke ₁ e ₂… e_{k –1} – различные записи одного и того же маршрута (пути).

Незамкнутый маршрут (путь), в котором все ребра (дуги) попарно различны, называется цепью. Цепь, в которой все вершины попарно различны, называется простой цепью. Замкнутый маршрут (путь), в котором все ребра (дуги) попарно различны, называется циклом (контуром). Цикл (контур), в котором все вершины попарно различны, называется простым.

Каковы минимальная длина простого цикла (контура) в (ориентированных) псевдографах, мультиграфах, графах?

Пусть p ₁= v ₁ e ₁ v ₂ e ₂ v ₃… e_{k –1} v_k, p ₂= v_ke_kv_{k +1}… e_{m –1} v_m – пути в орграфе G, где k ³2, m ³ k +1. назовем путь

p _1° p ₂= v ₁ e ₁ v ₂ e ₂ v ₃… e_{k –1} v_ke_kv_{k +1}… e_{m –1} v_m

композицией путей p ₁ и p ₂. Аналогично определяется композиция маршрутов.

Основными матрицами, описывающими граф, являются матрица смежности и матрица инцидентности.

Пусть дан граф G =(V, E), | V |= n, | E |= m.

Определение. Матрицей смежности графа G называется квадратная матрица A_G размера n × n, в которой

Как по матрице смежности отличить орграф от неорграфа?

Замечание. Если G – мультиграф, то значение a_ij можно положить равным k, где k – кратность дуги (v_i, v_j).

Определение. Матрицей инцидентности неорграфа G называется матрица B_G размера n × m, в которой

Определение. Матрицей инцидентности орграфа G называется матрица B_G размера n × m, в которой

Пример. Построить граф с матрицей:

а) ; б) ; в) ;

г) ; д); е) .

С помощью введенных матриц удобно задавать графы для обработки на ЭВМ. Однако при большом количестве вершин матрицы могут оказаться слишком громоздкими. Другим способом представить граф в памяти машины является структура смежности: для каждой вершины графа составляется перечень ее последователей.

1) Сумма элементов матрицы A_G, где G =(V, E) – мультиграф, V ={ v ₁, v ₂, …, v_n }, по i -ой строке (или по i -ому столбцу) равна deg v_i.

2) Суммы элементов матрицы A_G, где G =(V, E) – ориентированный псевдограф, V ={ v ₁, v ₂, …, v_n }, по i -ой строке и по i -ому столбцу соответственно равна deg⁺ v_i, deg^– v_i.

3) Пусть G =(V, E) – ориентированный мультиграф с непустым множеством дуг. Тогда

а) сумма строк матрицы B_G является нулевой строкой,

б) любая строка матрицы B_G является линейной комбинацией остальных строк;

в) ранг матрицы B_G не превосходит | V |–1;

г) для любого контура в G сумма столбцов матрицы B_G, соответствующих дугам, входящим в этот контур, равна нулевому столбцу.

4) Пусть G – мультиграф с непустым множеством ребер. Тогда при покоординатном сложении по модулю 2:

а) сумма строк матрицы B_G является нулевой строкой

б) любая строка матрицы B_G является суммой остальных строк;

в) для любого цикла в G сумма столбцов матрицы B_G, соответствующих ребрам, входящим в этот цикл, равна нулевому столбцу.

Самостоятельно обоснуйте!

Рассмотрим матрицу и обозначим ее элементы .

Теорема. Элемент матрицы графа (орграфа) G =(V, E) равен числу маршрутов (путей) в G длины k, соединяющих вершину v_i с вершиной v_j (из вершины v_i в вершину v_j).

Самостоятельно обоснуйте!

Следствие. а) В n -вершинном графе (орграфе) G =(V, E) существует маршрут (путь), соединяющий вершину v_i с вершиной v_j (из вершины v_i в вершину v_j) Û элемент c_ij матрицы C =отличен от нуля.

б) В n -вершинном графе (орграфе) G =(V, E) существует замкнутый маршрут (путь), проходящий через вершину v_i Û элемент c_ii матрицы C =отличен от нуля.

Замечание. Более экономичными в вычислительном отношении по сравнению с целочисленными матрицами являются булевы матрицы. Хранение их в памяти ЭВМ требует меньшего объема оперативной памяти, и логические операции над ними выполняются гораздо быстрее. Таким образом, устанавливать наличие (замкнутых) маршрутов (путей) в графе эффективнее обработкой булевых матриц.

Дата добавления: 2014-01-04