Дошкольникам
1 класс
2 класс
3 класс
4 класс
5 класс
6 класс
7 класс
8 класс
9 класс
10 класс
11 класс
ОГЭ
ЕГЭ
ВУЗ
Для всех
Назад
Новый рекорд!

Очки опыта

0

Обракоины

0
Как вам тренажер?

Следующая тема
Очки
0
Решено
0
Время
00:00:00

Бесплатные занятия

Оформите подписку, чтобы заниматься без ограничений.

Вы не вошли в аккаунт

Создайте бесплатный аккаунт, чтобы сохранить прогресс и получить персональную подборку полезных материалов.

Настройки

Остановка

Длительность тренировки

Времени на один вопрос

Другие тренажеры по теме
Cледующая тема
Cледующая тема
Все тренажеры Все тренажеры

Ошибки

Здесь появятся ошибки, допущенные во время тренировки.

Прогресс

Завершите тренировку, чтобы освоить навык.

О тренажере

Количество путей в графе

Схема дорог, по которым можно двигаться только в одну сторону, — это ориентированный граф: города — его вершины, дороги со стрелками — ребра с направлением. Путь из А в другой город — цепочка дорог, где каждая следующая начинается там, где закончилась предыдущая. Тренажер учит находить число таких путей не перебором, а счетом по вершинам: у каждого города записывается, сколько путей ведет в него из А.

Для кого этот тренажер

Тренажер подходит ученикам 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;
  • вместо путей считают ребра, которые ведут в конечную вершину.
Вернуться к тренажерам Вернуться к тренажерам

Предложить улучшение