Граф. Весовая матрица графа. Длина пути между вершинами графа.

Изучая тему Моделирование как метод познания, вы могли узнали что существуют различные виды моделей: знаковые, табличные, графические.

К графическим моделям относят схемы, карты, чертёжи, графики, диаграммы и графы.

Граф - один из видов графических моделей, особый вид схем.

С помощью графов можно изображать связанные объекты и системы объектов.

Граф состоит из вершин, связанных линиями - рёбрами. Вершины графа изображаются кругами, овалами, точками, прямоугольниками и т. д.

Объекты представляются как вершины графа, а связи – как его рёбра (дуги) .

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

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

Таблица, построенная на основе взвешенного графа называется весовая матрица графа.

Если прямой связи между объектами нет, то на графе отсутствует соответствующее ребро или дуга, а в таблице ячейка, связывающая объекты остается пустой.

Крупные города Республики обозначены на графе буквами A, B, C, D, E. Некоторые горда соединены дорогами. Протяженность дорог (расстояния между городами) указаны на графе. Изучите рисунок и ответьте на вопросы.

1. Между какими городами построена прямая автомобильная дорога?
2. Укажите все возможные пути проезда из города А в город D
3. Определите длину каждого возможного пути из города А в город D.
4. Какой длины будет маршрут, проходящий через все города Республики