ОГЭ 2027 · Информатика

Задание 4 ОГЭ по информатике

Что проверяет линия, сколько она стоит, на чём теряют баллы и как решать — по нашим конспектам. В банке 50 заданий этой линии с разбором.

Аналитика ОГЭ: №4 (графы, кратчайший путь)

Баллы: 1 первичный балл
Частота: в каждом варианте

Частые ловушки

Берут прямую дорогу, не проверив более короткий обходной путь
Проходят через один пункт дважды (в ОГЭ каждый пункт — не более одного раза)
Ошибаются при сложении длин участков

Совет. Выпиши все пути между нужными пунктами, сложи длины участков и выбери минимальную сумму

Разборы

Разбор примера

Разбор перебором: все маршруты выписаны

Дороги: A–B 3 км, A–C 9 км, B–C 2 км, B–D 6 км, C–D 1 км, C–E 6 км, D–E 2 км. Определите длину кратчайшего пути между A и E.

Показать решение по шагам

1. Из A выходят два ребра: в B (3) и в C (9). Значит маршрутов будет две группы.
2. Группа «через B»: A–B–C–E = 3 + 2 + 6 = 11; A–B–C–D–E = 3 + 2 + 1 + 2 = 8; A–B–D–E = 3 + 6 + 2 = 11; A–B–D–C–E = 3 + 6 + 1 + 6 = 16.
3. Группа «через C»: A–C–E = 9 + 6 = 15; A–C–D–E = 9 + 1 + 2 = 12; A–C–B–D–E = 9 + 2 + 6 + 2 = 19.
4. Сравниваем все суммы: 8, 11, 11, 12, 15, 16, 19. Наименьшая — 8.
5. Кратчайший путь оказался самым длинным по числу рёбер: A–B–C–D–E, целых четыре участка. Прямая дорога A–C длиной 9 в кратчайший путь вообще не вошла.
6. В ответ записываем только число: 8.

Ответ: Ответ: 8

Разбор примера

Тот же граф методом пометок

Те же дороги: A–B 3, A–C 9, B–C 2, B–D 6, C–D 1, C–E 6, D–E 2. Найдите длину кратчайшего пути от A до E методом пометок.

Показать решение по шагам

1. Ставим пометки: A = 0, остальные пока не определены.
2. Обрабатываем A. Соседи: B получает 0 + 3 = 3, C получает 0 + 9 = 9.
3. Наименьшая непомеченная — B (3). Обрабатываем её: C можно улучшить до 3 + 2 = 5 (это меньше 9), D получает 3 + 6 = 9.
4. Наименьшая непомеченная — C (5). Обрабатываем: D улучшаем до 5 + 1 = 6 (меньше 9), E получает 5 + 6 = 11.
5. Наименьшая непомеченная — D (6). Обрабатываем: E улучшаем до 6 + 2 = 8 (меньше 11).
6. Осталась одна вершина E с пометкой 8 — она и становится окончательной. Ответ совпал с перебором: 8.
7. Обрати внимание, как пометка C менялась: сначала 9, потом 5. Именно это уточнение и даёт правильный ответ; тот, кто зафиксировал 9 сразу, получит 12 вместо 8.

Ответ: Ответ: 8

Разбор примера

Задание 4: кратчайший путь по таблице расстояний

Между населёнными пунктами построены дороги, протяжённость которых приведена в таблице. Пустая клетка означает, что прямой дороги нет. A—B 1, A—C 1, A—D 2, A—F 9, B—C 7, B—D 3, B—F 6, C—D 3, C—E 1, D—E 5, E—F 7. Определите длину кратчайшего пути между A и F.

Показать решение по шагам

1. Сначала выписываем все дороги, ведущие в F: A—F (9), B—F (6), E—F (7). Значит, попасть в F можно только через A напрямую, через B или через E.
2. Считаем лучшие расстояния до этих пунктов от A: до B — 1 (напрямую), до E — через C: A—C (1) + C—E (1) = 2 (напрямую из A дороги в E нет, через D вышло бы 2 + 5 = 7).
3. Складываем три варианта: напрямую A—F = 9; через B: 1 + 6 = 7; через E: 2 + 7 = 9.
4. Наименьшее: 7, путь A—B—F.
5. Почему это надёжнее полного перебора: маршрутов в такой таблице десятки, а дорог в конечный пункт всего три. Считать надо только лучшие пути до этих трёх пунктов — работа сокращается в разы.

Ответ: 7

Разбор примера

Задание 4: тот же приём при другой таблице

Дороги: A—B 2, A—C 4, B—C 1, B—D 7, C—D 3, C—E 8, D—E 2, D—F 6, E—F 1. Определите длину кратчайшего пути между A и F.

Показать решение по шагам

1. Дороги в F: D—F (6) и E—F (1). Значит, нужны лучшие расстояния от A до D и до E.
2. До B: 2. До C: напрямую 4 или через B 2 + 1 = 3 — берём 3.
3. До D: через B 2 + 7 = 9 или через C 3 + 3 = 6 — берём 6.
4. До E: через C 3 + 8 = 11 или через D 6 + 2 = 8 — берём 8.
5. Варианты финиша: через D 6 + 6 = 12; через E 8 + 1 = 9. Кратчайший путь 9: A—B—C—D—E—F.
6. Важная деталь: путь из пяти дорог оказался короче пути из двух. Число участков ничего не говорит о длине — сравнивать надо только суммы.

Ответ: 9

Разбор примера

Задание 4: когда прямая дорога не самая короткая

Дороги: A—B 1, B—C 1, A—C 5. Определите длину кратчайшего пути между A и C и объясните, почему ответ не 5.

Показать решение по шагам

1. Вариант первый — прямая дорога A—C: 5 км.
2. Вариант второй — через B: A—B (1) + B—C (1) = 2 км.
3. Кратчайший путь — 2, и он идёт в обход, хотя прямая дорога существует.
4. Вывод, который спасает на экзамене: наличие прямой дороги не значит, что она кратчайшая. Проверять обходные пути обязательно — именно на этом построена половина заданий линии 4.
5. Проверка на смысл: в таблице такие случаи видны сразу — в строке стоит одно большое число и несколько маленьких.

Ответ: 2

Уроки по этой линии

Задание 4: кратчайший путь в графе — открыт бесплатно
Таблицы как информационные модели: отбор данных по условию

Потренируй задание 4

Задания этой линии с проверкой и разбором решения — после бесплатной регистрации. Ошибки сами попадут в план повторения.

Начать бесплатно

Аналитика ОГЭ: №4 (графы, кратчайший путь)

Баллы

1 первичный балл

Частота

в каждом варианте

Частые ловушки

Берут прямую дорогу, не проверив более короткий обходной путь

Проходят через один пункт дважды (в ОГЭ каждый пункт — не более одного раза)

Ошибаются при сложении длин участков

Совет. Выпиши все пути между нужными пунктами, сложи длины участков и выбери минимальную сумму

Разборы

Разбор примера

Разбор перебором: все маршруты выписаны

Дороги: A–B 3 км, A–C 9 км, B–C 2 км, B–D 6 км, C–D 1 км, C–E 6 км, D–E 2 км. Определите длину кратчайшего пути между A и E.

Показать решение по шагам

1. Из A выходят два ребра: в B (3) и в C (9). Значит маршрутов будет две группы.
2. Группа «через B»: A–B–C–E = 3 + 2 + 6 = 11; A–B–C–D–E = 3 + 2 + 1 + 2 = 8; A–B–D–E = 3 + 6 + 2 = 11; A–B–D–C–E = 3 + 6 + 1 + 6 = 16.
3. Группа «через C»: A–C–E = 9 + 6 = 15; A–C–D–E = 9 + 1 + 2 = 12; A–C–B–D–E = 9 + 2 + 6 + 2 = 19.
4. Сравниваем все суммы: 8, 11, 11, 12, 15, 16, 19. Наименьшая — 8.
5. Кратчайший путь оказался самым длинным по числу рёбер: A–B–C–D–E, целых четыре участка. Прямая дорога A–C длиной 9 в кратчайший путь вообще не вошла.
6. В ответ записываем только число: 8.

Ответ: Ответ: 8

Разбор примера

Тот же граф методом пометок

Те же дороги: A–B 3, A–C 9, B–C 2, B–D 6, C–D 1, C–E 6, D–E 2. Найдите длину кратчайшего пути от A до E методом пометок.

Показать решение по шагам

1. Ставим пометки: A = 0, остальные пока не определены.
2. Обрабатываем A. Соседи: B получает 0 + 3 = 3, C получает 0 + 9 = 9.
3. Наименьшая непомеченная — B (3). Обрабатываем её: C можно улучшить до 3 + 2 = 5 (это меньше 9), D получает 3 + 6 = 9.
4. Наименьшая непомеченная — C (5). Обрабатываем: D улучшаем до 5 + 1 = 6 (меньше 9), E получает 5 + 6 = 11.
5. Наименьшая непомеченная — D (6). Обрабатываем: E улучшаем до 6 + 2 = 8 (меньше 11).
6. Осталась одна вершина E с пометкой 8 — она и становится окончательной. Ответ совпал с перебором: 8.
7. Обрати внимание, как пометка C менялась: сначала 9, потом 5. Именно это уточнение и даёт правильный ответ; тот, кто зафиксировал 9 сразу, получит 12 вместо 8.

Ответ: Ответ: 8

Разбор примера

Задание 4: кратчайший путь по таблице расстояний

Показать решение по шагам

1. Сначала выписываем все дороги, ведущие в F: A—F (9), B—F (6), E—F (7). Значит, попасть в F можно только через A напрямую, через B или через E.
2. Считаем лучшие расстояния до этих пунктов от A: до B — 1 (напрямую), до E — через C: A—C (1) + C—E (1) = 2 (напрямую из A дороги в E нет, через D вышло бы 2 + 5 = 7).
3. Складываем три варианта: напрямую A—F = 9; через B: 1 + 6 = 7; через E: 2 + 7 = 9.
4. Наименьшее: 7, путь A—B—F.
5. Почему это надёжнее полного перебора: маршрутов в такой таблице десятки, а дорог в конечный пункт всего три. Считать надо только лучшие пути до этих трёх пунктов — работа сокращается в разы.

Ответ: 7

Разбор примера

Задание 4: тот же приём при другой таблице

Дороги: A—B 2, A—C 4, B—C 1, B—D 7, C—D 3, C—E 8, D—E 2, D—F 6, E—F 1. Определите длину кратчайшего пути между A и F.

Показать решение по шагам

1. Дороги в F: D—F (6) и E—F (1). Значит, нужны лучшие расстояния от A до D и до E.
2. До B: 2. До C: напрямую 4 или через B 2 + 1 = 3 — берём 3.
3. До D: через B 2 + 7 = 9 или через C 3 + 3 = 6 — берём 6.
4. До E: через C 3 + 8 = 11 или через D 6 + 2 = 8 — берём 8.
5. Варианты финиша: через D 6 + 6 = 12; через E 8 + 1 = 9. Кратчайший путь 9: A—B—C—D—E—F.
6. Важная деталь: путь из пяти дорог оказался короче пути из двух. Число участков ничего не говорит о длине — сравнивать надо только суммы.

Ответ: 9

Разбор примера

Задание 4: когда прямая дорога не самая короткая

Дороги: A—B 1, B—C 1, A—C 5. Определите длину кратчайшего пути между A и C и объясните, почему ответ не 5.

Показать решение по шагам

1. Вариант первый — прямая дорога A—C: 5 км.
2. Вариант второй — через B: A—B (1) + B—C (1) = 2 км.
3. Кратчайший путь — 2, и он идёт в обход, хотя прямая дорога существует.
4. Вывод, который спасает на экзамене: наличие прямой дороги не значит, что она кратчайшая. Проверять обходные пути обязательно — именно на этом построена половина заданий линии 4.
5. Проверка на смысл: в таблице такие случаи видны сразу — в строке стоит одно большое число и несколько маленьких.

Ответ: 2