§ 44. Графы

§ 44. Графы

Что такое граф?

Как вы знаете из курса 10 класса, граф — это набор узлов (вершин) и связей между ними (рёбер). Информацию об узлах и связях графа обычно хранят в виде таблицы специального вида — матрицы смежности (рис. 6.20).

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