Граф – задается множеством вершин (точек) и множеством ребер (связей), соединяющих некоторые пары вершин. Пример графа – схема метрополитена.
Хранение информации о графе в памяти компьютера в виде растрового или векторного рисунка неэффективно, так как рисунок предназначен для восприятия человеком, а не компьютером. Компьютеру удобно хранить информацию в виде таблиц.
Если на пересечении строки А и столбца В записано 1, то это означает, что есть ребро, соединяющее вершины А и В, если 0, то такого ребра нет. Такую таблицу называют матрицей смежности. Единицы на главной диагонали показывают, что в графе есть петля – ребро, которое заканчивается в одной и той же точке, вершине. Матрица смежности симметрична относительно главной диагонали.
A B C D E
A 0 1 0 0 1
B 1 1 1 0 0
C 0 1 0 1 0
D 0 0 1 0 1
E 1 0 0 1 1
Весовая матрица:
A B C D E
A 15 5
B 15 13 12
C 12 8
D 8 10
E 5 10 7
Весовая матрица не определяет взаимное расположение вершин. Предполагая, что вес ребра обозначает расстояние между вершинами, то можно определить длину пути, то есть сумму длин ребер
