Регистрируйтесь в онлайн-школе и получайте деньги за интересные сообщения и другие действия!

ЗНАНИЯ

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

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

В 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

х

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

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

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

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

Графы, визуализация

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

Категории
ОПЫТ:

Задание 1

При правильном ответе Вы получите 1 балл

Как называется граф, у которого каждое ребро имеет какое-либо значение?

Выберите всего один правильный ответ.

Ответить
Категории

Комментарии:

Добавление комментариев доступно только зарегистрированным пользователям