Графы и их применение в задачах
💻 Информатика · 10 класс
Что такое граф
Граф — это математическая модель, состоящая из множества вершин и соединяющих их рёбер. Графами удобно описывать сети дорог, схемы метро, связи между людьми и многие другие задачи, где важны объекты и связи между ними.
Виды графов
- Неориентированный граф — рёбра не имеют направления, по ним можно двигаться в обе стороны.
- Ориентированный граф — рёбра имеют направление, такие рёбра называют дугами.
- Взвешенный граф — каждому ребру приписано число (вес): длина дороги, время, стоимость.
Матрица смежности
Граф удобно задавать матрицей смежности — квадратной таблицей, где строки и столбцы соответствуют вершинам. На пересечении ставят вес ребра, а если связи нет — ноль или прочерк. Рассмотрим граф с городами А, Б, В, Г.
| — | А | Б | В | Г |
|---|---|---|---|---|
| А | — | 5 | — | 3 |
| Б | 5 | — | 2 | — |
| В | — | 2 | — | 4 |
| Г | 3 | — | 4 | — |
Для неориентированного графа матрица симметрична относительно главной диагонали.
Поиск кратчайшего пути
Частая задача — найти путь наименьшей длины между двумя вершинами. Длина пути равна сумме весов его рёбер. Найдём кратчайший путь из А в В.
Путь 1: А → Б → В = 5 + 2 = 7Путь 2: А → Г → В = 3 + 4 = 7Оба пути дают одинаковую длину 7 — это и есть кратчайшее расстояние.
Степень вершины
Степень вершины — это число рёбер, выходящих из неё. В нашем примере вершина А связана с Б и Г, значит её степень равна двум. Сумма степеней всех вершин неориентированного графа равна удвоенному числу рёбер.
Деревья
Особый и очень важный вид графа — дерево. Это связный граф без замкнутых путей (циклов). В дереве между любыми двумя вершинами есть ровно один путь. Деревьями описывают, например, файловую систему компьютера, родословные и структуру организаций. Если в дереве n вершин, то рёбер у него ровно n - 1.
Где применяют графы
Графовые модели встречаются во многих практических задачах информатики и повседневной жизни.
| Задача | Что обозначают вершины и рёбра |
|---|---|
| карта дорог | города и соединяющие их дороги |
| схема метро | станции и перегоны между ними |
| социальная сеть | люди и их знакомства |
| компьютерная сеть | устройства и линии связи |
Во всех этих задачах граф позволяет наглядно представить связи и применять одинаковые приёмы решения: поиск пути, проверку связности, подсчёт расстояний.
Частые ошибки. В неориентированном графе матрица смежности симметрична — нельзя заполнить только половину. Длина пути — это сумма весов рёбер, а не число вершин. При поиске кратчайшего пути нужно перебрать все возможные маршруты, а не первый попавшийся.
Кратко о главном
- Граф состоит из вершин и соединяющих их рёбер.
- Графы бывают ориентированные, неориентированные и взвешенные.
- Матрица смежности задаёт связи и веса рёбер в виде таблицы.
- Кратчайший путь — маршрут с наименьшей суммой весов рёбер.