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

V	1	2	3	4
5
1	0	1	0	0	0
2	0	1	0	0	0
3	1	0	0	0	0
4	0	1	0	0	0
5	0	1	1	0	0

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

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

Если в графе есть вершины, соединённые между собой несколькими рёбрами, то элемент матрицы смежности sij равен числу рёбер, соединяющих вершины vi и vj. Из этого следует, что если вершины vi и vj не соединены рёбрами, то элемент матрицы смежности sij равен нулю.
Пример 4. Составить матрицу смежности для графа, представленного на рисунке ниже.

Ответ.

V	1	2	3	4	5
1	0	3	2	0	0
2	3	0	0	1	1
3	2	0	0	0	1
4	0	1	0	0	0
5	0	1	1	0	0

Нет времени вникать в решение? Можно заказать работу!

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

В случае взвешенного графа элемент матрицы смежности sij равен числу w, если существует ребро между вершинами vi и vj с весом w. Элемент sij равен нулю, если рёбер между вершинами vi и vj не существует.
Пример 5. Составить матрицу смежности для графа, представленного на рисунке ниже.

Ответ.

V	1	2	3	4	5
1	0	11	9	0	0
2	11	0	0	5	8
3	9	0	0	0	2
4	0	5	0	0	0
5	0	8	2	0	0

Матрицы инцидентности

Матрица инцидентности H - это матрица размера n x m, где n - число вершин графа, m - число рёбер графа. Обычно в матрице инцидентности строки соответствуют вершинам графа, а столбцы - рёбрам графа.

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

Элемент матрицы инцидентности для неориентированного графа hij определяется следующим образом:
- равен единице, если вершина vi инцидентна ребру ej;
- равен нулю, если вершина vi не инцидентна ребру ej.
Пример 6. Составить матрицу инцидентности для графа, представленного на рисунке ниже.

Ответ.

V	1-2	1-3	2-4	2-5	3-5
1	1	1	0	0	0
2	1	0	1	1	0
3	0	1	0	0	1
4	0	0	1	0	0
5	0	0	0	1	1

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

Элемент матрицы инцидентности для ориентированного графа hij определяется следующим образом:
- равен минус единице, если вершина vi является началом ребра ej;
- равен единице, если вершина vi является концом ребра ej;
- равен нулю, если вершина vi не инцидентна ребру ej.
Пример 7. Составить матрицу инцидентности для графа, представленного на рисунке ниже.

Ответ.

V	1-2	1-3	2-4	2-5	3-5
1	1	-1	0	0	0
2	-1	0	-1	-1	0
3	0	1	0	0	-1
4	0	0	1	0	0
5	0	0	0	1	1

На сайте есть пример реализации на языке программирования С++ алгоритма обхода в глубину графа, представленного матрицей инцидентности.

Списки инцидентности

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

Ответ.
1:2→3
2:1→4→5
3:1→5
4:2
5:2→3

Преимущества и недостатки каждого способа

Матрицы смежности и инцидентности целесообразнее использовать когда:

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

Из-за последнего обстоятельства матрицы чаще используются в теоретических исследованиях графов.
Списки инцидентности целесообразнее использовать когда:

• 
  число вершин графа велико;
  
• 
  число рёбер графа относительно невелико;
  
• 
  граф формируется по какой-либо модели;
  
• 
  во время действия алгоритма часто требуется модифицировать граф;
  
• 
  в алгоритме часто используются локальные свойства вершин, например, например, окрестности вершин.
  

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

На рис. 1,2 изображено множество точек  и множество линий , соединяющих эти точки, которые все вместе образуют граф .Если линии имеют стрелки, то граф называется ориентированным или орграфом (рис. 2).
 
Рис. 1. Граф . Рис. 2. Орграф  .
Графы и можно представить в аналитической форме либо матрицей смежности ,либо матрицей инцидентности .
Для нашего конкретного неориентированного графа  матрицы и выглядят следующим образом:

Матрица смежности для неориентированного графа всегда симметрична.
Фигурирующая в ней 2 может быть в некоторых случаях заменена на 1.
В матрице инцидентности сумма единиц по столбцам указывает на степень вершины v_i. Нередко расположение вершин и ребер в этой матрице меняют местами (транспонируют). Так, для нашего конкретного орграфа матрицы и выглядят существенно иначе:
 
В общем случае матрица смежности для ориентированного графа  уже не будет симметричной. В матрице инцидентности ставится 1, если дуга исходит из вершины, и —1, если дуга заходит в нее.
Матрица смежности и матрица инцидентности
Есть два стандартных способа представить граф G = (V,E) 

• 
  – как набор списков смежных вершин
  
• 
  как матрицу смежности.
  

Первый обычно предпочтительнее, ибо дает более компактное представление разреженных графов– тех, у которых |E| много меньше |V|².
Большинство стандартных алгоритмов используют именно это представление. Но в некоторых ситуациях удобнее пользоваться матрицей смежности – например, для плотных графов, у которых |EG| сравнимо с |VG|².
Матрица смежности позволяет быстро определить, соединены ли две данные вершины ребром. Алгоритмы отыскания кратчайших путей для всех пар вершин, используют представление графа с помощью матрицы смежности.

• 
  Определение Матрицей смежностиграфа G = (V, E) называется квадратная булева матрицаAпорядкаn,элементы которой определяются следующим образом:
  

Свойства

1. 
   А – симметрическая матрица
   
2. 
   На главной диагонали матрицы смежности всегда стоят 0.
   
3. 
   Число единиц в строке равно степени соответствующей вершины.
   

Матрицей инцидентностиграфаGназывается булева матрица размера |V|´|G| вида

Свойства:

1. 
   В каждом столбце матрицы ровно две единицы
   
2. 
   Равных столбцов нет.
   

Например, на следующем рисунке граф задан графически, списком смежных вершин, матрицей смежности и матрицей инцидентности.

графически	список смежных вершин номер вершины степень вершины 1 2 2 5 2 4 1 3 4 5 3 2 2 4 4 3 2 3 5 5 3 1 2 4
матрица смежности 1 2 3 4 5 1 0 1 0 0 1 2 1 0 1 1 1 3 0 1 0 1 0 4 0 1 1 0 1 5 1 1 0 1 0	матрица инцидентности e1 e2 e3 e4 e5 e6 e7 1 1 1 0 0 0 0 0 2 0 1 1 0 1 1 0 3 0 0 0 0 0 1 1 4 0 0 0 1 1 0 1 5 1 0 1 1 0 0 0

Рассматриваются также графы с нагруженными ребрами или взвешенные – графы, у которых каждому ребру поставлено в соответствие некоторое вещественное число – вес или нагрузка ребра.
Такой граф можно задать матрицей расстояний – квадратной матрицей размера |V|´|V|, где на пересечении i-ой строки и j-го столбца записан вес ребра (i, j), если ребро есть, ¥, если ребра нет и 0, если i = j.