§ 44. Графы
Что такое граф?
Как вы знаете из курса 10 класса, граф — это набор узлов (вершин) и связей между ними (рёбер). Информацию об узлах и связях графа обычно хранят в виде таблицы специального вида — матрицы смежности (рис. 6.20).
Единица на пересечении строки А и столбца В означает, что между узлами А и В есть связь. Ноль указывает на то, что связи нет. Матрица смежности симметрична относительно главной диагонали (выделенные фоном ячейки в таблице). Единица на главной диагонали обозначает петлю — ребро, которое начинается и заканчивается в одной и той же вершине (в данном примере — в вершине С). Строго говоря, граф — это математический объект, а не рисунок. Конечно, его можно нарисовать на плоскости, но матрица смежности не даёт никакой информации о том, как именно следует располагать узлы друг относительно друга. Для таблицы, приведенной на рис. 6.20