Анализ информационных моделей или нахождение количества путей в графе является заданием 9 ОГЭ. Задание состоит в том, что необходимо определить длину кратчайшего пути, или кратчайшую длину пути, проходящего через определенный населенный пункт.
Также может быть условие найти количество путей, проходящих из одного город в другой. По условию, по каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
С одной стороны, задание не очень сложное. Но большинство школьников начинают решать эту задачу путем подсчета дорог, проводя карандашиком по графу. В таком случае решение задачи займет много времени и есть хороший шанс допустить ошибку.
Это задание необходимо решать при помощи динамического программирования.
Динамическое программирование – это такой способ решения, когда мы разбиваем одну задачу на более простые задачи того же типа.
Этот способ применяется для решения этого типа задач путем постепенного нахождения количества путей для каждого города, пока в итоге не дойдем до необходимой вершины графа – города в который необходимо попасть.
Решим первую задачу.
Задача 1. Анализ информационных моделей
Мы сейчас находимся в городе А и с него начинаем свой путь. Сколько здесь дорог -1. Записываем на ребре графа единицу. В город Б идет тоже одна дорога из А – переписываем количество дорог рядом с городом Б – 1 дорога. В Г идет также одна дорога из А. Тоже написали единицу рядом с городом Г.
В город В идут две дороги( из Г и из Б). Суммируем количество дорог для каждой вершины графа, т.е. Б+Г=1+1 = 2. Рядом с вершиной В ставим 2.
В пункт Е – одна дорога из Г, в пункт Д идет одна дорога из Б – переписываем количество дорог рядом с вершинами графа Е и Д.
Теперь остается подсчитать количество дорог в пункте К. Для этого складываем дороги последовательно, которые ведут в город К:
Д+Б+В+Г+Е = 1+1+2+1+1 = 6 дорог.
Ответ: 6 дорог
Таким способом решить довольно быстро и небольшой шанс ошибиться.
Задача 2. Анализ информационных моделей
Ищем количество дорог из пункта А в пункт Л.
Собираем дороги. В рункте А – 1 дорога, в пункте Б – 1 дорога, в пункте Г – две дороги: из пункта А и из Г.
В пункт Б – 1 дорога из пункта А.
В пункт Е ведут две дороги – из пункта Б и из А (1+1=2).
В пункт Е ведет две дороги: из пункта Б и пункта В (2+1 = 3)
В пункте Ж –две дороги: из пункта Д и из пункта Г (2+1=3)
В пункт З у нас ведут дороги из пунктов: Е, В,Г,Д (3+2+2+3 =10)
В пункт И ведет дорога из Е, но в Е у нас входило 3 дороги. Переписываем эту тройку в пункт З.
В пункт К идет одна дорога из Ж.
Считаем количество дорог в город Л: (3+3+10+3+3 = 22)
Ответ: 22
Задача 3. Анализ информационных моделей
Эта задача отличается от предыдущих, так как надо найти количество путей, ограниченных дорогой через город Е.
Сначала мы на графе должны вычеркнуть те пути, которые не проходят через город Е.
Получается, что через город Е проходят дороги из пункта Б и пункта В.
Таким образом решаем задачу.
Из А у нас одна дорога. Из А в Д – 1 дорога, В Г ведет 2 дороги: из А и из Д.
В пункт Б у нас единственная дорога из А. В пункт В ведет 3 дороги: из А, Б и Г (1+1+2=4).
В пункт Е ведет дорога из В и Б (4+1 =5)
В пункт И из Е ведет 5 дорог, в пункт З из Е – 5 дорог.
Таким образом, в Л ведут дороги из пункта И (5 дорог), из Е (5 дорог), из З (5 дорог). Итого 5+5+5=15 дорог.
Ответ: 15 дорог.
Задача 4. Анализ информационных моделей
Эта задача посложнее.
Сначала убираем дороги, по которым мы не попадаем в город В: АД, ДЕ,ГЕ,ГЖ,ЕЖ
Все остальные дороги оставляем.
Теперь ищем:
А – 1 дорога;
Б – 1 дорога;
Г (1+1) – 2 дороги;
В (2+1) – 3 дороги;
Ж – 3 дороги;
Н – 3 дороги;
К – 3 дороги;
М (3+3) – 6 дорог;
Л (3+3+6) — 12 дорог;
П (3+12+6) = 21 дорога.
Ответ: 21.
Задача 5. Анализ информационных моделей
Убираем дороги, которые не проходят через пункт Ж. Это дороги: ЕИ и ЗИ.
Дорога А – 1 дорога;
Дорога Д – 1 дорога;
Дорога Г (1+1) – 2 дороги;
Дорога Б – 1 дорога из А;
Дорога В (1+1+2) – 4 дороги;
Дорога З (4+2+1) – 7 дорог;
Дорога Е (4+1) – 5 дорог;
Дорога Ж (5+4+9) – 16 дорог;
В пункт И всего одна дорога из Ж, поэтому переносим – 16 дорог;
В пункт Л – одна дорога из И – переносим 16 дорог;
В пункт М – одна дорога из Л – 16 дорог.
Ответ: 16.
Вопросы анализа информационных моделей 11 класса можно смотреть по ссылке.
😉 Посмотрела, вроде все понятно. А это главное.