Логотип Репа AI Репа AIподготовка к ЕГЭ
Войти Попробовать бесплатноПопробовать
← Все задания: Информатика
Задание23

Алгоритмы на графах

ЕГЭ по информатике · задание 23 из 27

ЕГЭ-2027 · проект ФИПИ · сверено 19.09.2026

Ответ: Числовой результат

Что проверяет задание

Новый тип проекта 2027: оптимальные пути и число путей в ориентированном ациклическом графе.

Как решать

  1. Постройте список рёбер, сохранив направление и вес.
  2. Для ациклического графа найдите топологический порядок; номера вершин не обязаны идти по нему.
  3. Для кратчайшего пути берите минимум расстояний, для числа путей — сумму количеств.

Попробуйте на примере

Авторские учебные примеры. Упражнения показывают отдельный приём; на экзамене условия могут быть сложнее.

Упражнение 1 · Алгоритмы на графах

Рёбра направленного графа: A→B вес 2,5; A→C вес 7; B→C вес 1,2; B→D вес 6; C→D вес 2,1. Найдите целую часть длины кратчайшего пути A→D.
Показать решение и ответ
  1. A→B→D: 8,5; A→C→D: 9,1.
  2. A→B→C→D: 2,5 + 1,2 + 2,1 = 5,8.
  3. Целая часть минимальной длины равна 5.
Ответ5

Упражнение 2 · Количество направленных путей

В ориентированном ациклическом графе рёбра A→B, A→C, B→C, B→D, C→D. Сколько различных путей ведут из A в D?
Показать решение и ответ
  1. До A один пустой путь; до B — 1, до C — напрямую из A или через B: 2.
  2. До D приходят из B и C: 1 + 2 = 3 пути.
Ответ3

Упражнение 3 · Округление после поиска пути

Рёбра графа: A→B длиной 1,8; B→D — 1,8; A→C — 2,1; C→D — 1,1. Найдите целую часть длины кратчайшего пути из A в D.
Показать решение и ответ
  1. Пути через B и C имеют длины 3,6 и 3,2 соответственно.
  2. Минимум — 3,2; его целая часть 3. Округлять отдельные рёбра до сложения нельзя.
Ответ3

Где легко ошибиться

Округление каждого ребра

Если нужна целая часть результата, сначала найдите точную сумму весов пути.

Номер вершины как порядок обработки

Нумерация не обязана совпадать с направлением рёбер. Для динамики по ациклическому графу нужен топологический порядок.

Минимум вместо суммы путей

Для оптимальной длины сравнивают расстояния. Для количества маршрутов складывают числа путей от предшественников — это другая динамика.

Частые вопросы

Можно обрабатывать вершины по номеру?

Только если условие гарантирует соответствующий порядок рёбер. Иначе нужен топологический порядок или подходящий алгоритм поиска пути.

Закрепите знания на практике

В Репе — короткие уроки, проверка ответа и помощь Помогашки.

Попробовать бесплатно

Смежные задания

01Графы и таблицы дорог 13Подсчёт программ исполнителя 22Параллельные процессы
Об источниках и редакции

Нумерация, форматы ответов и баллы сверены с опубликованными проектами ФИПИ на 2027 год. Примеры авторские: часть показывает формат задания, часть тренирует отдельный приём. Указанное время — учебный ориентир, а не норматив ФИПИ. После утверждения документов нужна повторная сверка.

Источники: ФИПИ: демоверсии, спецификации, кодификаторы · ФИПИ: планируемые изменения ЕГЭ-2027 · Комплект проекта по предмету (архив)

Сверка содержания: . Статус документов — проект.

Обновлено