Задание 4 · Базовый уровень · Модели и графы
Графы и простейшие модели
Сопоставляем таблицу дорог, схему или граф с описанием объекта.
Теория
Вершины графа — объекты, рёбра — связи. При сопоставлении полезно сначала сравнить степени вершин: сколько связей выходит из каждой вершины.
Что держать в голове
Степень вершины = число рёбер, выходящих из неё
Вес ребра может означать расстояние или стоимость
Отсутствие ребра означает отсутствие прямой связи
Алгоритм решения
- Посчитайте число связей у каждой вершины.
- Сопоставьте уникальные степени.
- Проверьте соседей найденных вершин.
- В конце сверяйте веса рёбер, если они есть.
Мини-пример
Если в таблице у пункта A три дороги, а только одна вершина графа имеет степень 3, это сильная подсказка для сопоставления.
Проверь себя
У вершины P есть рёбра к A, B, C и D. Чему равна степень P?