Логотип
Войти
Информатика • 9 класс
115

Графы. Таблица смежности

  • Граф — математическая абстракция реальной системы любой природы, объекты которой обладают парными связями.

 

Пример. Пусть требуется найти расстояния от 1-й вершины до всех остальных.

Решение:

  1. минимальная метка 1 и её соседями являются вершины 2, 3, 6, где вершина 2 имеет минимальный вес 7, 3 ― 9, а 6 ― 14;
  2. минимальная метка 2 и её соседями являются вершины 3, 4, где вершина 3 имеет минимальный вес 17 (7 + 10), 4 ― 22 (7 + 15). Но вершина 3 имеет уже вес 9, который меньше 17, поэтому метка не меняется;
  3. минимальная метка 3 и её соседями являются вершины 6, 4, где вершина 6 имеет минимальный вес 11 (9 + 2), 4 ― 20 (9 + 11);
  4. минимальная метка 6 и её соседями являются вершина 5, где вершина 5 имеет минимальный вес 20 (9 + 2 + 9);
  5. минимальная метка 4 и её соседями являются вершина 5, где вершина 5 имеет минимальный вес 26 (9 + 11 + 6). Но вершина 5 имеет уже вес 20, который меньше 26, поэтому метка не меняется.
Было полезно?

Рекомендуем

Вы учитель или ученик?
Познакомьтесь с нашим образовательным онлайн-сервисом с тысячами интерактивных работ
Учителю
Удобно проводить уроки в классе, назначать работы на дом и анализировать результаты всего класса или конкретных учеников
Ученику
Самостоятельно изучать новые и повторять пройденные темы, готовиться по индивидуальной траектории и оценивать результаты на наглядных графиках
Зарегистрироваться в «Облаке знаний»