Графы и схемы

Графы и схемы как способ представления данных

Информацию можно показывать не только текстом, но и наглядными схемами. Один из самых мощных способов — граф. Граф — это набор точек, соединённых линиями. Точки называют вершинами, а линии между ними — рёбрами. Графами удобно изображать связи: дороги между городами, друзей в социальной сети, ходы в игре. Главное в графе — не где нарисованы точки, а какие из них соединены.

Виды графов

Если по ребру можно двигаться в обе стороны, граф называют неориентированным (например, дружба взаимна). Если связь односторонняя, ребро рисуют стрелкой — это ориентированный граф (например, «кто кому подписан»). Особый и очень важный вид графа — дерево.

Дерево

Дерево — это граф без замкнутых путей (циклов), у которого есть главная вершина — корень. От корня идут ветви к другим вершинам. Так устроены: генеалогическое древо семьи, структура папок на диске, оглавление книги. В дереве от корня к любой вершине ведёт ровно один путь.

Способ	Что показывает	Пример
Таблица	Свойства многих объектов	Расписание уроков
Граф	Связи между объектами	Карта дорог
Дерево	Подчинение, вложенность	Папки на диске

Таблицы

Таблица — ещё один способ представления данных. В строках записывают объекты, в столбцах — их свойства. Таблица удобна, когда у многих объектов одинаковый набор признаков, например расписание или список класса с оценками.

Пример: граф дорог

Запишем, какие города соединены дорогами:

Вершины: А, Б, В, Г Рёбра: А—Б, А—В, Б—Г, В—Г Путь из А в Г: А -> Б -> Г (или А -> В -> Г)

По такому графу легко найти, можно ли добраться из одного города в другой и какими маршрутами.

Где встречаются графы

Графы окружают нас, хотя мы не всегда называем их так. Карта метро — это граф: станции вершины, линии между ними рёбра. Список друзей в социальной сети — тоже граф: люди вершины, дружба рёбра. Даже схема «кто кого победил» в турнире — граф. Главное достоинство графа в том, что он показывает связи наглядно, и сразу видно, что с чем соединено и как добраться от одного к другому.

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

Частые ошибки. Не путай вершины и рёбра: вершина — это точка-объект, ребро — связь между двумя точками. В дереве не бывает циклов: если путь возвращается в ту же вершину, это уже не дерево. И помни — в графе важно только наличие связи, а длина и форма нарисованной линии значения не имеют.

Кратко о главном

• Граф — это вершины (точки) и рёбра (связи между ними).
• Графы бывают ориентированные (со стрелками) и неориентированные.
• Дерево — граф без циклов с корнем; так устроены папки и родословные.
• Таблица показывает свойства многих объектов по строкам и столбцам.
• Граф, дерево и таблица — разные удобные способы представления данных.