Задание 1 · ЕГЭ, информатика 2027
Графы и таблицы
Схема и таблица описывают одну сеть дорог — совмещаем их и считаем кратчайший путь.
Простыми словами
У вас есть карта района без подписей расстояний и таблица расстояний, где улицы названы номерами П1, П2… Сначала нужно понять, какой номер — какая точка на карте, и только потом считать маршрут.
Один объект описан дважды: схемой (граф) и таблицей (весовая матрица). Нумерация в них никак не связана — первая работа задания 1 наложить одно на другое.
Степень вершины — число дорог, выходящих из пункта. На схеме это число линий у кружка, в таблице — число заполненных клеток в строке.
Пример: схема и таблица
| П1 | П2 | П3 | П4 | П5 | П6 | |
|---|---|---|---|---|---|---|
| П1 | 9 | 5 | 1 | |||
| П2 | 6 | |||||
| П3 | 9 | 3 | 4 | |||
| П4 | 3 | 8 | ||||
| П5 | 5 | 6 | 8 | |||
| П6 | 1 | 4 |
Вопрос: найдите длину кратчайшего пути из А в Е.
Сопоставление по степеням
- Степени в таблице: П1 — 3, П2 — 1, П3 — 3, П4 — 2, П5 — 3, П6 — 2. На схеме: А, В, Д — 3; Б, Г — 2; Е — 1.
- Начинаем с уникальной степени: единственная вершина степени 1 — Е = П2. Её сосед Д = П5.
- Соседи Д на схеме — В, Г, Е; у П5 — П1, П4, П2. Степень 2 среди них только у П4 → Г = П4, тогда В = П1.
- Оставшиеся: А (степень 3) = П3, Б (степень 2) = П6. Проверка: А–Б есть — клетка П3–П6 заполнена ✓
Каждый вывод проверяйте по соседям: если А = П3, то у П3 должны быть соседи Б, В, Г, то есть П6, П1, П4 — так и есть.
Кратчайший путь по таблице
Длины берём только из таблицы. Идём от А и для каждого пункта храним наименьшее известное расстояние, обновляя его, если нашёлся обход короче.
- А = 0: Б = 4, В = 9, Г = 3.
- Г (3): Д = . Б (4): В = — лучше 9.
- В (5): Д = — лучше 11.
- Д (10): Е = . Ответ: 16 (путь А–Б–В–Д–Е).
Где теряют балл: считают длину пути по схеме «на глаз», хотя числа есть только в таблице; забывают, что путь в обход может оказаться короче прямой дороги (А–В напрямую 9, а через Б — 5).
Различайте вершины по степеням их соседей: «вершина степени 3, у которой сосед степени 1» встречается один раз.
Где эта тема разобрана подробно
Готовые работы по теме
Собраны заранее — одним нажатием: распечатать с ключом, раздать ученикам ссылкой или QR-кодом, поменять настройки. Номер набора постоянный: по этой ссылке всегда та же работа.
теория этой темы, 8 заданий по подтемам и ключ — файлом DOCX, который можно править под себя.
Прохождение онлайн
Имя ученика никуда не отправляется: он вводит только номер по списку, а таблицу «номер → фамилия» видите только вы.
Классы, выданные работы и результаты учеников по кодам — в журнале учителя: без регистрации, хранится только на этом компьютере.