Теория
Граф
Граф — вершины (пункты) и рёбра (дороги). Ориентированный граф — рёбра со стрелкой (дорога только в одну сторону).
Список рёбер задаёт, откуда куда есть дорога. Таблица расстояний = матрица смежности: число — длина ребра, пусто — дороги нет.
Приём 1. Сколько путей из А в конечную вершину
- В старт А записываем 1 путь.
- Для каждой вершины: число путей = СУММА путей всех вершин, откуда в неё ведёт ребро.
- Считаем в топологическом порядке (сначала те, для которых все входящие уже посчитаны).
- Пример: А=1, Б=1, В=1, Г=1, Д=1, Е=1+1+1=3, Ж=3+1+1=5 → ответ 5.
Приём 2. Кратчайший путь по таблице
- Выписать все простые маршруты от пункта к пункту (узел не проходить дважды).
- Сложить длины рёбер каждого маршрута.
- Выбрать наименьшую сумму.
Совет: перебирай маршруты системно, чтобы не пропустить короткий неочевидный.
Термины темы
Понятия из теории выше — нажми, чтобы разобрать определение, признаки и пример:
- Граф — набор вершин и соединяющих их рёбер: пункты и дороги, станции и перегоны.
- Ориентированный граф — граф, рёбра которого — стрелки: по каждому можно пройти только в одну сторону.
- Матрица смежности — квадратная таблица, в клетках которой отмечено, есть ли ребро между двумя вершинами.
Попробуй решить
Реши задачу этого типа прямо здесь — проверю сразу и покажу разбор:
Дороги между городами А, Б, В, Г, Д, Е заданы списком (все дороги односторонние, проезд только в указанном направлении):
из А — в Б, Г
из Б — в В, Г, Д, Е
из В — в Г, Д
из Г — в Д
из Д — в ЕСколько существует различных путей из города А в город Е?
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
A B C D E A 7 2 6 B 7 3 C 3 4 6 D 2 4 E 6 6 Определите длину кратчайшего пути между пунктами B и C. Передвигаться можно только по указанным дорогам. Каждый пункт можно посетить только один раз.
Дороги между городами А, Б, В, Г, Д, Е, Ж заданы списком (все дороги односторонние, проезд только в указанном направлении):
из А — в Б, Д, Ж
из Б — в В, Д
из В — в Г, Д, Ж
из Г — в Д, Е, Ж
из Д — в Е
из Е — в ЖСколько существует различных путей из города А в город Ж?
Дороги между городами А, Б, В, Г, Д, Е, Ж, З заданы списком (все дороги односторонние, проезд только в указанном направлении):
из А — в Б, Е
из Б — в В, Е, Ж
из В — в Г
из Г — в Д, З
из Д — в Е, Ж
из Е — в Ж
из Ж — в ЗСколько существует различных путей из города А в город З?
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
A B C D E A 7 B 7 2 9 7 C 2 6 6 D 9 6 E 7 6 Определите длину кратчайшего пути между пунктами D и B. Передвигаться можно только по указанным дорогам. Каждый пункт можно посетить только один раз.
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
A B C D E A 8 3 8 B 8 2 7 C 3 9 D 2 9 1 E 8 7 1 Определите длину кратчайшего пути между пунктами B и D. Передвигаться можно только по указанным дорогам. Каждый пункт можно посетить только один раз.
Разбор заданий
Дороги между городами А, Б, В, Г, Д, Е заданы списком (все дороги односторонние, проезд только в указанном направлении):
из А — в Б, Е
из Б — в В, Е
из В — в Г, Е
из Г — в Д, Е
из Д — в Е
Сколько существует различных путей из города А в город Е?
Показать решение
Идём по городам по порядку: в А — 1 путь, а для каждого следующего города складываем числа путей во все города, из которых в него ведёт дорога.
Число путей: А = 1, Б = 1, В = 1, Г = 1, Д = 1, Е = 5.
В Е получается 5.
Ответ: 5.
Дороги между городами А, Б, В, Г, Д, Е, Ж заданы списком (все дороги односторонние, проезд только в указанном направлении):
из А — в Б, Г, Ж
из Б — в В
из В — в Г, Е
из Г — в Д, Е
из Д — в Е, Ж
из Е — в Ж
Сколько существует различных путей из города А в город Ж?
Показать решение
Идём по городам по порядку: в А — 1 путь, а для каждого следующего города складываем числа путей во все города, из которых в него ведёт дорога.
Число путей: А = 1, Б = 1, В = 1, Г = 2, Д = 2, Е = 5, Ж = 8.
В Ж получается 8.
Ответ: 8.
Частые вопросы
Что нужно знать по теме «Граф» для ОГЭ по информатике?
вершины (пункты) и рёбра (дороги). Ориентированный граф — рёбра со стрелкой (дорога только в одну сторону). Список рёбер задаёт, откуда куда есть дорога. Таблица расстояний = матрица смежности: число — длина ребра, пусто — дороги нет. Приём 1. Сколько путей из А в конечную вершину В старт А… Полный разбор с примерами — выше на этой странице.
В каких заданиях ОГЭ по информатике встречается тема «Граф»?
Тема «Граф» встречается в заданиях №4, №9 — по действующим спецификации и демоверсии ФИПИ.
Где потренироваться в заданиях по теме «Граф»?
В тренажёре Совелия — задачи этого типа с мгновенной проверкой, подсказками и разбором именно твоей ошибки. Бесплатно, без рекламы, прогресс сохраняется.