Решение задач при помощи графов

Рассмотрим ещё раз важную тему: решение задач с помощью графов. 

В 6-м классе мы уже говорили о визуализации данных и создавали таблицы в Word. Теперь покажем решение задач с помощью дополнительной визуализации на примере.

Допустим, у нас есть таблица с дорогами между населенными пунктами (А, В, С, D, Е) (такую таблицу можно назвать весовой матрицей).

• Если дорога есть, в весовой матрице указывается расстояние.
• Если дороги нет, то клетка пустая.
• Между самим городом (например, А и А), нет смысла проводить дорогу, поэтому ставим «x».

По такой таблице довольно сложно понять, как нам проехать быстрее.

Для визуализации построим граф - т.е. модель с вершинами и ребрами.

Вершины - это города, ребра - это дороги.

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

Теперь нам достаточно легко посмотреть кратчайший путь между городами, Например, из А в В идем через С.