«Сетевые структуры данных. Понятие графа и его представления.»

Глава 2. Способы предоставления графов
Граф, как и большинство других математических объектов, может быть представлен с помощью перечисления множеств, с помощью графического изображения, так же может изображаться матричным способом.
Способ перечисления множеств – это способ перечисления множеств V и E составляющих множество G:

• 
  G= (V, E), здесь G – граф, V – его вершины, а E – ребра;
  
• 
  |V| – порядок (число вершин);
  
• 
  |E| – размер графа (число рёбер).
  

Графический способ – способ графического отображения взаимодействий между множествами V и E в графе G.
Матричный способ разберём конкретней, потому что с помощью матриц выполняются операции над графами, которых они описывают.
Матрица — математический объект, записываемый в виде прямоугольной таблицы элементов кольца или поля (например, целых, действительных или комплексных чисел), которая представляет собой совокупность строк и столбцов, на пересечении которых находятся её элементы. Количество строк и столбцов задает размер матрицы.
Матрица смежности графа — это квадратная матрица, в которой каждый элемент принимает одно из двух значений: 0 или 1. Прежде чем отобразить граф через матрицу смежности, рассмотрим простой пример такой матрицы (Рисунок 6).
Это двоичная квадратная матрица, т. к. число строк в ней равно числу столбцов, и любой из ее элементов имеет значение либо 1, либо 0. Первая строка и первый столбец (не входят в состав матрицы, а показаны здесь для легкости ее восприятия) содержат номера, на пересечении которых находится каждый из элементов, и они определяют индексное значение последних. Имея в наличии лишь матрицу такого типа, несложно построить соответствующий ей граф, обратим внимание на рисунок 7.



Рисунок 6 – Матрица смежности



Рисунок 7 – Матрица смежности и соответствующий граф

Слева на рисунке изображена все та же матрица смежности, имеющая размерность 4×4. Числа, выделенные синим, можно рассматривать как вершины смешанного графа, расположенного справа – того, представлением которого является матрица.

Для графа со взвешенными ребрами ячейки матрицы смежности принимают значения веса ребра.
Матрица инцидентности. Говорить о том, что ребро g и каждая из вершин u и y инцидентна g, стоит лишь в том случае, если g соединяет u и y. Уяснив это, перейдем к рассмотрению данного метода. Матрица инцидентности строиться по похожему, но не по тому же принципу, что и матрица смежности. Так если последняя имеет размер n×n, где n – число вершин, то матрица инцидентности – n×m, здесь n – число вершин графа, m – число ребер. То есть теперь чтобы задать значение какой-либо ячейки, нужно сопоставить не вершину с вершиной, а вершину с ребром.
В каждой ячейки матрицы инцидентности неориентированного графа стоит 0 или 1, а в случае ориентированного графа, вносятся 1, 0 или -1. То же самое, но наиболее структурировано:
1) Неориентированный граф
a. 1 – вершина инцидентна ребру
b. 0 – вершина не инцидентна ребру
2) Ориентированный граф
a. 1 – вершина инцидентна ребру, и является его началом
b. 0 – вершина не инцидентна ребру
c. -1 – вершина инцидентна ребру, и является его концом
Построим матрицу инцидентности сначала для неориентированного графа, а затем для орграфа. (смотреть Рисунок 8)



Рисунок 8 – Матрица инцидентности и соответствующий ей неориентированный граф
Ребра обозначены буквами от a до e, вершины – цифрами. Все ребра графа не направленны, поэтому матрица инцидентности заполнена положительными значениями. (Рисунок 9)

Рисунок 9 - Матрица инцидентности и соответствующий ей ориентированный граф

Для орграфа графа матрица имеет немного другой вид. В каждую из ее ячеек внесено одно из трех значений. Обратите внимание, что нули в матрицах, изображенных на рисунке 8 и рисунке 9, занимают одинаковые позиции, ведь в обоих случаях структура графа одна. Но некоторые положительные единицы сменились на отрицательные, например, в неориентированном графе ячейка (1, b) содержит 1, а в орграфе -1. Действительно, это уместно, т. к. в первом случае ребро b не направленное, а во втором – направленное, и, причем вершиной входа для него является вершина «1».

Каждый столбец отвечает за какое-либо одно ребро, поэтому граф, описанный при помощи матрицы инцидентности, всегда будет иметь следующий признак: любой из столбцов матрицы инцидентности содержит две единицы, либо 1 и -1 когда это ориентированное ребро, все остальное в нем – нули.
Для графа со взвешенными ребрами ячейки матрицы инцидентности принимают значения веса ребра, при то что в орграфе значение ячейки может быть отрицательным.