Матрица достижимостей

Пример 1

Сколько ребер в полном графе?

а) с пятью вершинами

б) с шестью вершинами

в) с n вершинами

 

Решение

Полный граф с    n вершинами имеет n(n-1)/2 ребер n(n-1)/2 ребер

 

 

Если в графе имеется ребро E=(v_i,v_j), то говорят, что эти вершины смежны в этом графе, ребро E инцидентно каждой из вершин v_i,v_j а каждая из них инцидентна этому ребру.

Способы представления графов. Матрицы

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

Наиболее часто используются такие структуры данных – матрица смежности, матрица инцидентности, списки инцидентности

Матрица смежности

Матрицей смежности R=[r_i,j]_nn графа G=(V,E) называется квадратная матрица порядка n (n – число вершин графа), элементы которой r_i,j (i=1, 2, …n; j=1,2, …n) определяются следующим образом:

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

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

Смежность вершин графа – это когда две вершины соединены ребром

Матрица смежности для неориентированного графа

Элемент матрицы смежности r_ij неориентированного графа определяется следующим образом:

- равен 1, если вершины v_i и v_j смежны;

- равен 0, если вершины v_i и v_j не смежны.

Если для элемента матрицы v_ij имеет место i=j, то есть элемент находится на диагонали, то этот элемент равен 1, если элемент имеет петлю, и 0, если элемент не имеет петли. 

Пример 2

Составить матрицу смежности для графа:

 

Решение:

 

 

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

Матрица смежности для ориентированного графа

Элемент матрицы смежности r_ij ориентированного графа определяется следующим образом:

- равен 1, если из вершины v_i в вершину v_j входит дуга;

- равен 0, если из вершины v_i в вершину v_j дуга не входит 

Если для элемента матрицы v_ij имеет место i=j, то есть элемент находится на диагонали, то этот элемент равен 1, если элемент имеет петлю, и 0, если элемент не имеет петли. 

Как и для неориентированного графа, если для элемента матрицы v_ij имеет место i=j, то есть элемент находится на диагонали, то этот элемент равен 1, если элемент имеет петлю, и 0, если элемент не имеет петли. 

Пример 3  

Составить матрицу смежности для графа:

 

Решение:

 

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

 

Матрица смежности для графа с кратными ребрами

Если в графе есть вершины, соединенные между собой несколькими ребрами, то этот элемент матрицы смежности r_ij равен числу ребер, соединяющих вершины v_i и v_j. Из этого следует, что если вершины v_i и v_j не соединены ребрами, то элемент матрицы смежности r_ij равен 0.

Пример 4

Составить матрицу смежности для графа:

Решение:

Взвешенный граф – это граф, дугам которого поставлены в соответствие веса, так что дуге E=(v_i,v_j) сопоставлено некоторое число w=w(v_i,v_j), называемое длиной (или весом, или стоимостью) дуги. Обычный (не взвешенный) граф можно интерпретировать как взвешенный, все ребра которого имеют одинаковый вес = 1.

 

Матрица смежности для взвешенного графа

В случае взвешенного графа элемент матрицы смежности r_ij равен числу w, если существует ребро между вершинами v_i и v_j   с весом w(v_i,v_j). Элемент r_ij равен нулю, если ребер между вершинами v_i и v_j   не существует.

Пример 5

Составить матрицу смежности для графа:

Решение

 

Матрица смежности полностью определяет структуру графа. Возведем матрицу смежности в квадрат. Элемент r²_i,j матрицы R² определяется по формуле:

Слагаемое     тогда и только тогда, когда     и     в противном случае слагаемое   . Так как из равенства       следует существование пути длины два (пути, проходящего через две дуги) из вершины v_i в вершину v_j, проходящего через вершину v_k, то r²_i,j равно числу путей длины два, идущих из v_i в v_j через v_k.

Если r^p_i,j является элементом матрицы R^p, то r^p_i,j ≠0 равно числу путей длины p, идущих из v_i в v_j.

След матрицы

След матрицы – это сумма элементов квадратной матрицы, расположенных на главной диагонали и обозначается trace(A)

Пример 6   

На рисунке задан граф G. построить матрицу смежности и выяснить, сколько путей длины три существует в графе G.

Рис. 2. Граф G

 

Решение.

                 

 

               

 

Элемент r³_1,4=1, следовательно, в данном графе существует единственный путь длиной три – это путь из вершины х₁ в вершину х₄: (х₁,x₂), (x₂,x₃), (x₃,x₄)

Все элементы матрицы R⁴ равны нулю. Следовательно, в графе отсутствуют пути длиной четыре.

 

Пример 7

По заданной матрице смежности построить исходный граф и определить число циклических маршрутов  длины 3 и длины 4 

 

 

 0 1 1 0 1

 1 0 0 0 0

 1 0 0 1 1

 0 0 1 0 1

 1 0 1 1 0,

 

Матрица смежности данного графа симметричная, поэтому ей соответствует неориентированный граф. Сумма элементов матрицы равна 12, следовательно, по лемме о рукопожатиях графе 6 ребер. Построим этот граф

(рис. 1.17). Очевидно, в нем два цикла (3–4–5 и 1–3–5) длиной 3 и один цикл (1–3–4–5) длиной 4. В данной задаче решение получено прямым подсчетом по изображению графа. Для более сложных случаев существует алгоритм решения задачи по матрице смежности.

Известно, что след (trace) матрицы смежности, возведенной в k – ю степень, равен числу циклических маршрутов длины k

Это число включает в себя и искомое число циклов. Цикл отличается от циклического маршрута тем, что в нем не повторяются ребра. Кроме того, предполагается, что искомые циклы не помечены, а в след матрицы входят именно помеченные маршруты. Непомеченных циклов длиной 3 в 6 раз меньше, чем помеченных, так как каждый помеченный цикл может отличаться началом, а их в данном случае три, и двумя направлениями обхода (по и против часовой стрелки). Возведем заданную матрицу смежности в третью степень:

A3 =

2 3 6 2 6

3 0 1 2 1

6 1 4 5 5

2 2 5 2 5

6 1 5 5 4

и получим

c3=1/6 traceA³= 2

 

Матрица инциденций

Матрицей инциденций S=[s_i,j]^m_n называется прямоугольная матрица размерности n´m (n – число вершин, m – число дуг), элементы которой     определяются следующим образом: 

 

Если граф G не содержит петель, то каждый столбец матрицы S содержит единственный элемент, равный 1 (дуга имеет начало) и единственный элемент, равный –1 (дуга имеет конец), а остальные элементы равны нулю.

Инцидентность – это когда вершина v является либо началом либо концом ребра e. Две вершины называются инцидентными, если у них есть общее ребро.

Матрица инцидентности для неориентированного графа

Элемент матрицы инцидентности для неориентированного графа s_i,j определяется следующим образом

- равен 1, если вершина v_i инцидентна ребру e_j;

- равен 0, если вершина v_i не инцидентна ребру e_j.

Пример 7

Составить матрицу инцидентности для графа:

Решение

Матрица инцидентности для ориентированного графа

Элемент матрицы инцидентности для ориентированного графа s_i,j определяется следующим образом

- равен 1, если вершина v_i является началом  ребра e_j

- равен -1, если вершина v_i является концом  ребра e_j;

- равен 0, если вершина v_i не инцидентна ребру e_j.

Пример 7

Составить матрицу инцидентности для графа:

Пример 8    

Построить матрицу смежности и матрицу инциденций для графа, приведенного на рисунке.

    

Рисунок – Исходный граф

Решение.

Матрица смежности R и инциденций S будут иметь вид:

 

;

                                   . 

Матрица достижимостей

Вершина графа v_i называется достижимой из вершины v_j того же графа, если существует по крайней мере один путь из v_i в v_j. R(v_i) – множество вершин, достижимых из некоторой вершины v_i  

Первым элементом множества R(v_i) является вершина v_i, которая достижима из себя самой с помощью пути длины нуль; Г(v_i) – множество вершин v_j, достижимых из v_i с использованием путей длины единица; Г²(v_i) – множество вершин, достижимых из v_i с использованием путей длины два; Г^p(v_i) – множество вершин, достижимых из v_i с использованием путей длины p. Таким образом, множество R(v_i) получается путем последовательного выполнения слева направо операции объединения вершин. Число объединений, которые необходимо выполнить, зависит от графа G. Но если граф конечен, то p<n, где n – число вершин графа.

Матрицей достижимостей D=[d_i,j]ⁿ_n называется квадратная матрица порядка n, элемент которой

 

 

Пример 9.    

Построить матрицу достижимостей графа G, представленного

на рис. 4

 

.

Рис. 4. Граф G

 

Решение.    

D(x₁)={x_1,x_2,x_3,x₄}

D(x₂)={x_2,x_3,x₄}

D(x₃)={x_3,x₄}

D(x₄)={x_4,x₃}

 

Следовательно, матрица достижимостей имеет вид:

.

Очевидно, что элементы d_i,i=1, i=1, 2, …, n, так как каждая вершина достижима из себя самой.

 

Пример 10

Для заданного графа построить матрицы смежности и инциденций

 

 

Инцидентность и смежность в графах, матрицы смежности, матрицы инцидентности, списки инцидентности.   https://function-x.ru/graphs5.html