Электронный учебник

§ 44. Графы

§ 44. Графы

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

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

 

 

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

 

Block title

Вход на сайт

Поиск

Календарь

«  Декабрь 2024  »
ПнВтСрЧтПтСбВс
      1
2345678
9101112131415
16171819202122
23242526272829
3031

Архив записей

Статистика


Онлайн всего: 27
Гостей: 27
Пользователей: 0