Основные способы заданий графов. С помощью специальных структур
Геометрическое изображение. Как уже отмечалось, простейшим способом представления графов является их геометрическое изображение. При этом вершины графов обычно представляются точками пространства, которые помечены обозначениями вершин.
Рассмотрим пример геометрического задания графа, приведенный на рисунке 11.
Рисунок 11 - Пример геометрического задания графа
Кроме наглядного геометрического изображения и представления графов используются и другие способы задания. Они позволяют представлять графы в виде структур, которые можно хранить и обрабатывать с помощью специальных алгоритмов и программ.
Списки ребер.
Представление произвольного графа с помощью списка ребер состоит в заполнении массива, содержащего все пары вершин, представляющие ребра графа. Недостатком такого способа представления является возможность утраты информации об изолированных вершинах.
Матрица смежности.
Пусть G = (V, U) - это граф с вершинами V = {Vi, ... Vn}. Тогда матрицей смежности этого графа называется квадратная таблица размером n x n, строки и столбцы которой поставлены во взаимно однозначное соответствие вершинам множества V.
Значение элемента этой матрицы, расположенного на пересечении i -и строки и j-го столбца определяется по правилу:
(11)
Для графа, изображённого на рисунке 11, матрица смежности имеет следующий вид:
-
a
b
c
d
e
v
a
0
0
1
0
1
1
b
0
1
0
1
0
0
c
1
0
0
1
0
0
d
0
1
1
0
0
1
e
0
0
0
0
0
0
v
0
0
0
1
0
0
4. Матрицы инциденций.
В некоторых случаях табличное представление графа должно сохранять информацию о наименованиях ребер, соединяющих вершины графа. Такая информация отсутствует в представлении графов матрицами смежности. Для сохранения данных об обозначениях ребер можно использовать представление графов матрицами инциденций.
Пусть G = (V, U) - произвольный граф, для которого:
V= {V,, ... Vn}- список вершин, U = {U1, ... ,Uk}- список рёбер.
Тогда матрицей инциденций этого графа называется таблица, имеющая n строк, соответствующих вершинам из V, и k столбцов, соответствующих ребрам из U.
Значение элемента 
этой
матрицы, находящегося на пересечении
i-й
строки и j-го столбца,
определяется по правилу:
Если
ребро
Если
ребро
В
остальных случаях
выходит из вершины
ведёт в
и не является петлёй
Рассмотрим пример составления матрицы инцидентности для графа, изображённого на рисунке 12.
Рисунок 12 –Ориентированный граф.
Матрица инцидентности.
-
A
B
C
D
E
F
G
H
L
K
1
1
-1
0
0
0
0
0
0
0
0
2
0
1
-1
0
0
0
0
0
0
1
3
0
0
1
1
-1
0
0
0
0
0
4
0
0
0
0
1
-1
0
1
0
0
5
0
0
0
0
0
1
-1
0
0
0
6
0
0
0
0
0
0
1
-1
-1
-1
7
-1
0
0
0
0
0
0
0
1
0
К недостаткам представления графов матрицами относится большой размер представления по отношению к объему информации, содержащейся в таблицах. Во многих случаях значительная часть информации, содержащейся в матрицах, может оказаться избыточной и использоваться только для поддержания табличной структуры представления графов.