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