Задание 13. Графы. Количество путей. ЕГЭ 2024 по информатике
Средний процент выполнения: 60.5%
Ответом к заданию 13 по информатике может быть цифра (число) или слово.
Задачи для практики
Задача 1
![](https://shatki-oosh.ru/wp-content/uploads/2024/04/149-1.png)
На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
Решение
Построим таблицу. В первую строку таблицы запишем наименование всех вершин в следующем порядке. Сначала запишем вершину К. Затем те вершины, из которых в К ведёт прямой путь и из которых в вершину К можно попасть только через уже просмотренные вершины. Далее вершины, из которых в уже просмотренные вершины ведёт прямой путь и из которых можно попасть только через уже просмотренные вершины. Получим:
К | З | И | Ж | Е | В | Б | Д | Г | А |
Вторую строку таблицы заполним числами, соответствующими количеству исходящих путей Px(K) из просматриваемой вершины x в K. Если из вершины x выходит несколько путей, например, в вершины x1, x2, и x3, то количество путей, ведущих из этой вершины в К, будет равно сумме путей, ведущих из x1, x2, и x3 в К.
То есть Px(K) = Px1 (K) + Px2 (K) + Px3 (K).
Для вершины К в таблицу заносим значение PК(K) = 1.
Следующей идёт вершина З. Из этой вершины выходит путь только в одну вершину К. PЗ(K) = PК(K) = 1.
Из вершины И выходят два пути в вершины З и К.
PИ(K) = PЗ(K) + PК(K) = 1 + 1 = 2.
Из вершины Ж выходит путь только в одну вершину К.
PЖ(K) = PК(K) = 1.
Из вершины Е выходят два пути в вершины Ж и К.
PЕ(K) = PЖ(K) + PК(K) = 1 + 1 = 2.
Из вершины В выходит путь только в одну вершину З.
PВ(K) = PЗ(K) = 1.
Из вершины Б выходят пути в вершины Е, Ж и В. Следовательно, PБ(K) = PЕ(K) + PЖ(K) + PВ(K) = 2 + 1 + 1 = 4.
Из вершины Д выходит путь только в одну вершину И.
PД(K) = PИ(K) = 2.
Из вершины Г выходят два пути в вершины И и Д.
PГ(K) = PД(K) + PИ(K) = 2 + 2 = 4.
Из вершины А выходят пути в вершины Б, В, Г и Д. Следовательно, PА(K) = PБ(K) + PВ(K) + PГ(K) + PД(K) = 4 + 1 + 4 + 2 = 11.
Получим:
К | З | И | Ж | Е | В | Б | Д | Г | А |
1 | 1 | 2 | 1 | 2 | 1 | 4 | 2 | 4 | 11 |
Задача 2
![](https://shatki-oosh.ru/wp-content/uploads/2024/04/112-2.png)
На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л, не проходящих через пункт Ж?
Решение
Построим таблицу. В первую строку таблицы запишем наименование всех вершин в следующем порядке. Сначала запишем вершину Л. Затем те вершины, из которых в Л ведёт прямой путь и из которых в вершину Л можно попасть только через уже просмотренные вершины. Далее вершины, из которых в уже просмотренные вершины ведёт прямой путь и из которых можно попасть только через уже просмотренные вершины. Получим:
Л | К | Ж | Е | И | Д | Г | В | Б | А |
Вторую строку таблицы заполним числами, соответствующими количеству исходящих путей Px(Л) из просматриваемой вершины x в Л, не проходящих через пункт Ж. Если из вершины x выходит несколько путей, например, в вершины x1, x2, и x3, то количество путей, ведущих из этой вершины в Л, не проходящих через пункт Ж, будет равно сумме путей, ведущих из x1, x2, и x3 в Л.
То есть Px(Л) = Px1(Л) + Px2 (Л) + Px3(Л).
Для вершины Л в таблицу заносим значение PЛ(Л) = 1.
Следующей идёт вершина К. Из этой вершины выходит путь только в одну вершину Л. PК(Л) = PЛ(Л) = 1.
Следующей в таблице идёт вершина Ж. Так как мы ищем пути, не проходящие через эту вершину, то PЖ(Л) = 0.
Из вершины Е выходят два пути в вершины Ж и К.
PЕ(Л) = PК(Л) + PЖ(Л) = 1 + 0 = 1.
Из вершины И выходят два пути в вершины Л и Ж.
PИ(Л) = PЖ(Л) + PЛ(Л) = 0 + 1 = 1.
Из вершины Д выходит путь только в одну вершину И.
PД(Л) = PИ(Л) = 1.
Из вершины Г выходит путь только в вершину Е. PГ(Л) = PЕ(Л) = 1.
Из вершины В выходят пути в вершины Д, Ж, Е и Г. Следовательно, PВ(Л) = PД(Л) + PЖ(Л) + PЕ(Л) + PГ(Л) = 1 + 0 + 1 + 1 = 3.
Из вершины Б выходят два пути в вершины Д и В.
PБ(Л) = PД(Л) + PВ(Л) = 1 + 3 = 4.
Из вершины А выходят два пути в вершины Б и Г.
PА(Л) = PБ(Л) + PГ(Л) = 4 + 1 = 5.
Получим:
Л | К | Ж | Е | И | Д | Г | В | Б | А |
1 | 1 | 0 | 1 | 1 | 1 | 1 | 3 | 4 | 5 |
Задача 3
![](https://shatki-oosh.ru/wp-content/uploads/2024/04/79-3.png)
На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л, проходящих через пункт В?
Решение
Построим граф, соответствующий данной схеме дорог. На графе будем для каждого города отмечать все возможные перемещения в города, связанные с ним исходящими дорогами.
Согласно условию задачи, требуется определить количество путей, проходящих через город В.
По графу определяем, что существует всего 10 различных путей, проходящих через город В.
Задача 4
![](https://shatki-oosh.ru/wp-content/uploads/2024/04/41-1.png)
На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
Решение
Построим таблицу. В первую строку таблицы запишем наименование всех вершин в следующем порядке. Сначала запишем вершину К. Затем те вершины, из которых в К ведёт прямой путь и из которых в вершину К можно попасть только через уже просмотренные вершины. Далее вершины, из которых в уже просмотренные вершины ведёт прямой путь и из которых можно попасть только через уже просмотренные вершины. Получим:
К | И | Е | З | Ж | Б | В | Г | Д | А |
Вторую строку таблицы заполним числами, соответствующими количеству исходящих путей Px(K) из просматриваемой вершины x в K. Если из вершины x выходит несколько путей, например, в вершины x1, x2, и x3, то количество путей, ведущих из этой вершины в К, будет равно сумме путей, ведущих из x1, x2, и x3 в К.
То есть Px(K) = Px1(K) + Px2(K) + Px3(K).
Например, из вершины Ж выходят пути в вершины Е, З и К. Следовательно, PЖ(K) = PЕ(K) + PЗ(K) + PК(K) = 1 + 2 + 1 = 4. Получим:
К | И | Е | З | Ж | Б | В | Г | Д | А |
1 | 1 | 1 | 2 | 4 | 1 | 6 | 6 | 7 | ‘20 |
Задача 5
![](https://shatki-oosh.ru/wp-content/uploads/2024/04/40.png)
На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М, Н, О. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город О, проходящих через город В?
Решение
Заметим, что количество путей из города А в город О, проходящих через город В равно произведению количества путей из города А в город В на количество путей из города В в город О. Разобъём заданный граф на два: один из которых будет содержать только города и соответствующие дороги, ведущие из А в В, а другой — только города и соответствующие дороги из В в О.
Построим таблицу, соответствующую каждой из полученных схем. В первую строку таблицы запишем наименование всех вершин в следующем порядке.
Для первой схемы сначала запишем вершину В. Затем те вершины, из которых в В ведёт прямой путь и из которых в вершину В можно попасть только через уже просмотренные вершины. Получим:
В | Б | Г | А |
Вторую строку таблицы заполним числами, соответствующими количеству исходящих путей Px (B) из просматриваемой вершины x в B. Если из вершины x выходит несколько путей, например, в вершины x1, x2, и x3, то количество путей, ведущих из этой вершины в К, будет равно сумме путей, ведущих из x1, x2, и x3 в К.
То есть Px (B) = Px1 (B) + Px2 (B) + Px3 (B). Получим:
В | Б | Г | А |
1 | 1 | 1 | 3 |
Количество путей из А в В равно 3.
Для определения количества путей из города В в О аналогично построим таблицу, соответствующую второй схеме.
О | Н | М | З | И | Л | К | Д | Ж | Е | В |
1 | 1 | 1 | 3 | 3 | 3 | 6 | 9 | 9 | 18 | 36 |
Количество путей из В в О равно 36.
Следовательно, количество путей из города А в город О, проходящих через город В, равно 3 · 36 = 108.
Задача 6
![](https://shatki-oosh.ru/wp-content/uploads/2024/04/4.png)
На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М, Н, О. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город О?
Решение
Построим таблицу, соответствующую заданной схеме. В первую строку таблицы запишем наименование всех вершин в следующем порядке. Сначала запишем вершину О. Затем те вершины, из которых в О ведёт прямой путь и из которых в вершину О можно попасть только через уже просмотренные вершины. Далее вершины, из которых в уже просмотренные вершины ведёт прямой путь и из которых можно попасть только через уже просмотренные вершины. Получим:
О | Н | М | З | И | Л | К | Д | Ж | Е | В | Б | Г | А |
Вторую строку таблицы заполним числами, соответствующими количеству исходящих путей Px (O) из просматриваемой вершины x в O. Если из вершины x выходит несколько путей, например, в вершины x1, x2, и x3, то количество путей, ведущих из этой вершины в К, будет равно сумме путей, ведущих из x1, x2, и x3 в К.
То есть Px (O) = Px1 (O) + Px2 (O) + Px3 (O). Получим:
О | Н | М | З | И | Л | К | Д | Ж | Е | В | Б | Г | А |
1 | 1 | 1 | 3 | 3 | 3 | 6 | 9 | 9 | 18 | 36 | 45 | 54 | 135 |
Задача 7
![](https://shatki-oosh.ru/wp-content/uploads/2024/04/166-1.png)
На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М?
Решение
Задача 8
![](https://shatki-oosh.ru/wp-content/uploads/2024/04/139-1.png)
На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е,Ж, З, И, К, Л, М, Н, О, П, Р. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город Р, не проходящих через города Б и М?
Решение
Задача 9
![](https://shatki-oosh.ru/wp-content/uploads/2024/04/130-1.png)
На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М, Н, О, П, Р. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город Р, не проходящих через города Е и Н?
Решение
Задача 10
![](https://shatki-oosh.ru/wp-content/uploads/2024/04/112-3.png)
На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М, Н, О, П, Р. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Р, проходящих через города З иМ?
Решение
Задача 11
![](https://shatki-oosh.ru/wp-content/uploads/2024/04/85-2.png)
На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М, Н, О. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город О, проходящих через город Е и не проходящих через город И?
Решение
Задача 12
![](https://shatki-oosh.ru/wp-content/uploads/2024/04/76-1.png)
На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М, Н, О. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город О, проходящих через город Д и не проходящих через город Л?
Решение
Задача 13
![](https://shatki-oosh.ru/wp-content/uploads/2024/04/67.png)
На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М, не проходящих через город В?
Решение
Задача 14
![](https://shatki-oosh.ru/wp-content/uploads/2024/04/58-1.png)
На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М, не проходящих через город Д?
Решение
Задача 15
![](https://shatki-oosh.ru/wp-content/uploads/2024/04/49-1.png)
На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М, Н, О. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город О, не проходящих через город Д?
Решение
Задача 16
![](https://shatki-oosh.ru/wp-content/uploads/2024/04/31-1.png)
На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М, проходящих через город Е?
Решение
Задача 17
![](https://shatki-oosh.ru/wp-content/uploads/2024/04/13-1.png)
На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М, проходящих через город Б?
Решение
Задача 18
![](https://shatki-oosh.ru/wp-content/uploads/2024/04/4-1.png)
На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е,Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М, проходящих через город Д?
Решение
Задача 19
![](https://shatki-oosh.ru/wp-content/uploads/2024/04/181.png)
На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
Решение
Задача 20
![](https://shatki-oosh.ru/wp-content/uploads/2024/04/171-1.png)
На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?