Решение задач при помощи графов
Рассмотрим ещё раз важную тему: решение задач с помощью графов.
В 6-м классе мы уже говорили о визуализации данных и создавали таблицы в Word. Теперь покажем решение задач с помощью дополнительной визуализации на примере.
Допустим, у нас есть таблица с дорогами между населенными пунктами (А, В, С, D, Е) (такую таблицу можно назвать весовой матрицей).
- Если дорога есть, в весовой матрице указывается расстояние.
- Если дороги нет, то клетка пустая.
- Между самим городом (например, А и А), нет смысла проводить дорогу, поэтому ставим «x».
| A | B | C | D | Е | |
| A | х | 17 | 8 | 3 | |
| B | х | 1 | 11 | ||
| C | 17 | 1 | х | 9 | |
| D | 8 | 11 | 9 | х | 6 |
| Е | 3 | 6 | х |
По такой таблице довольно сложно понять, как нам проехать быстрее.
Для визуализации построим граф - т.е. модель с вершинами и ребрами.
Вершины - это города, ребра - это дороги.
Такой граф будет взвешенным, так как его ребра имеют определенный вес, который мы возьмем из весовой матрицы. Граф не обязательно должен отображать реальное расстояние, но в идеале - это желательно сделать, например, с помощью линейки.
Теперь нам достаточно легко посмотреть кратчайший путь между городами, Например, из А в В идем через С.
