Вершина
Объект графа: город, село, площадка или участник.
Информатика · 7–9 класс · локальная версия
Маршрут по графу
Исследуй граф дорог и событийную карту Тамбовской области. Нажимай на города и сёла, изучай фестивали и решай задачи.
68
01 · Исследование
Карта становится графом
Каждый город — вершина, дорога — ребро, а число на линии — условный учебный вес.
02 · Событийный граф
Фестивали и ярмарки
Краеведческие сведения превращены в данные графа: населённые пункты — вершины, дороги — рёбра, числа — веса.
Режим изучения графа
Практическая работа № 6
Фестивальная экспедиция по Тамбовской области
Тема: «Взвешенные графы. Маршрут с ограничением» · 8–9 класс
G=(V,E)
Твоя миссия
Собери фестивальный маршрут
Ты находишься в Тамбове. Посети как можно больше действующих фестивалей и вернись обратно. На всю поездку можно потратить не более 500 учебных километров.
1 Нажми «Начать» — Тамбов станет первой точкой.
2 На карте подсветятся места, куда можно ехать дальше.
3 Нажимай подсвеченные точки. Путь и километры считаются сами.
4 Вернись в Тамбов и нажми «Проверить».
доступный ход выбранная точка
Справка: как эта задача записывается на языке графов
Математическая модель. Дан неориентированный взвешенный граф G=(V,E). Вершина v — населённый пункт с фестивалями, значение p(v) — количество действующих событий, вес ребра w(u,v) — условная длина дороги.
Условие. Начать в вершине «Тамбов», двигаться только по рёбрам графа, посетить каждую выбранную вершину не более одного раза и вернуться в Тамбов. Сумма весов рёбер не должна превышать 500 км.
Целевая функция. Максимизировать Σp(v). Если несколько маршрутов охватывают одинаковое число событий, лучшим считается маршрут меньшего веса.
Как читать карту
- Оранжевая точка — вершина графа.
- Тонкая линия — допустимое ребро.
- Число на линии — вес ребра.
- Зелёная линия — построенный маршрут.
Алгоритм ученика
- Оцени «ценность» соседних вершин.
- Нажимай вершины по порядку обхода.
- Следи за весом и возможностью возврата.
- Замкни цикл в Тамбове.
- Проверь решение и обоснуй метод.
Таблица рёбер и весов
0 событий
0 км
Маршрут не начат
Здесь появится протокол: каждое выбранное ребро, его вес и накопленная сумма.
Нажми «Начать решение». После этого выбирай только соседние вершины непосредственно на карте.
3. Выбери метод, который гарантированно найдёт оптимум
Краеведческий смысл модели. События взяты из календаря региона, но веса дорог и единый маршрут являются учебным упрощением. Фестиваль «Атмановские кулачки — 2026» оставлен на карте для обсуждения достоверности данных, но его ценность p(v)=0 из-за отмены.
Эталон для учителя
Сравнить с оптимальным маршрутом
—
событий
событий
Сначала ученик решает самостоятельно
Эталон показывает максимум и один из оптимальных порядков вершин. Другой маршрут с той же ценностью тоже может быть правильным.
Педагогический результат: ученик читает взвешенный граф, строит допустимый цикл, контролирует ограничение, сравнивает эвристику с точным алгоритмом и объясняет роль качества исходных данных.
03 · Теория
Словарь исследователя
Ребро
Связь между двумя вершинами: дорога или взаимодействие.
Вес
Числовая характеристика ребра: расстояние, время или стоимость.
Путь
Последовательность соседних вершин без разрыва.
04 · Практика
Проверь себя
Пять заданий: от степени вершины до кратчайшего пути.
05 · Матрица
Матрица смежности
Единица означает наличие ребра, ноль — отсутствие связи.
| Тамбов | Рассказово | Кирсанов | |
|---|---|---|---|
| Тамбов | 0 | 1 | 1 |
| Рассказово | 1 | 0 | 1 |
| Кирсанов | 1 | 1 | 0 |