Настройки
Прогресс
Завершите тренировку, чтобы освоить навык.
Количество путей в графе
Схема дорог, по которым можно двигаться только в одну сторону, — это ориентированный граф: города — его вершины, дороги со стрелками — ребра с направлением. Путь из А в другой город — цепочка дорог, где каждая следующая начинается там, где закончилась предыдущая. Тренажер учит находить число таких путей не перебором, а счетом по вершинам: у каждого города записывается, сколько путей ведет в него из А.
Для кого этот тренажер
Тренажер подходит ученикам 9 класса, которые изучают графы на уроках информатики и готовятся к ОГЭ, где есть похожие задачи, и ученикам 11 класса для повторения темы. Нужно знать, что такое граф, вершина и ребро, и уметь складывать небольшие числа. Правило счета и пример разобраны в теории ниже.
Какие задания встречаются
Каждая схема составляется заново: от 7 до 10 городов, обозначенных буквами от А до К, стоят в несколько столбцов, дороги соединяют соседние столбцы, ведут через столбец и связывают города одного столбца. Дороги не пересекаются, циклов в графе нет: по стрелкам нельзя вернуться в город, где уже были. Ответ — число от 4 до 25. Все задания одной сложности: в каждом есть хотя бы три города, куда ведут две дороги и больше.
Что делает ученик
Ученик считает пути из А в последний город и записывает число. После ответа у каждого города появляется число путей в него, а пошаговое решение показывает, как они складываются: «Г = Б + В = 1 + 2 = 3». Если ответ неверный, подсказка называет частую ошибку: например, не учтены пути по одной из дорог или вместо путей посчитаны дороги, ведущие в последний город.
Чему научится ученик
Ученик научится читать схему ориентированного графа, видеть, из каких вершин можно попасть в данную, и считать пути правилом сложения в правильном порядке, когда все нужные числа уже известны. Этот прием помогает в задачах на графы, на подсчет вариантов и в заданиях экзамена, где полный перебор путей занял бы слишком много времени.
Теория
Количество путей в ориентированном графе
В ориентированном графе у каждого ребра есть направление: на схеме дорог это стрелка, и по дороге можно двигаться только по стрелке. Путь из одной вершины в другую — цепочка ребер, где каждое следующее начинается там, где закончилось предыдущее. Если в графе нет циклов, то есть по стрелкам нельзя вернуться в уже пройденную вершину, пути можно сосчитать, не выписывая их.
Правило сложения. Число путей из начальной вершины в данную равно сумме чисел путей в вершины, из которых в нее ведут стрелки: каждый путь в такую вершину продолжается последним ребром. Например, в город Т ведут стрелки из Р и С. Если в Р ведут 2 пути, а в С — 3, то в Т ведут 2 + 3 = 5 путей.
Одна входящая стрелка. Если в вершину ведет только одна стрелка, путей в нее столько же, сколько в вершину, откуда стрелка выходит. Например, в У ведет стрелка только из Т, в Т ведут 5 путей — значит, и в У ведут 5 путей.
Порядок счета. У начальной вершины записываем 1. Каждую следующую считаем, когда уже посчитаны все вершины, из которых в нее ведут стрелки. Например, из А стрелки ведут в Б и В, из Б — в В и Г, из В — в Г. Тогда Б = А = 1, В = А + Б = 1 + 1 = 2, Г = Б + В = 1 + 2 = 3. Проверим перебором: А–Б–Г, А–В–Г и А–Б–В–Г — три пути.
Частые ошибки:
- складывают числа вершин, в которые стрелки выходят из данной вершины, а не тех, из которых стрелки входят в нее;
- считают вершину раньше времени: в примере выше Г, посчитанная до В, дала бы 1 + 1 = 2 вместо 3;
- вместо путей считают ребра, которые ведут в конечную вершину.