Графы. Задания 3 и 15

Теория: Если в город R из города A можно добраться только из городов X, Y и Z, то количество различных путей из города A в город R равно сумме числа различных путей проезда из A в X, из A в Y и из A в Z, то есть:

N_R = N_X + N_Y + N_Z

где N_Q — это количество путей из вершины A в вершину Q.

• Если в город R из города A можно добраться только из городов X, Y и Z, то количество различных путей из города A в город R равно сумме числа различных путей проезда из A в X, из A в Y и из A в Z, то есть:
• Число путей не бесконечно, исключением является только граф, в котором есть циклы – замкнутые пути
• Часто задачи с графами целесообразней решать с конца

15. На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город М?

Решение:

Около каждого города будем записывать количество маршрутов из города А.

В город Б ведет 1 маршрут

В город Д ведет 1 маршрут

В город Г ведут 2 маршрута из А и Д

В город В ведут 4 маршрута: 1 из А, 1 из Б и 2 из Г

В город Е ведут 5 маршрутов: 1 из Б и 4 из В

В город З ведут 7 маршрутов: 4 из В, 2 из Г и 1 из Д

В город Ж ведут 16 маршрутов: 5 из Е, 4 из В и 7 из З

В горд И ведут 28 маршрутов: 5 из Е, 16 из Ж и 7 из З

В город К ведут 28 маршрутов из И

В город Л ведут 28 маршрутов из И

В город М ведут 56 маршрутов: 28 из К и 28 из Л

Ответ: 56

15. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей, ведущих из города А в город М и проходящих через город Г?

Решение:

• Удалим ребра, которые проходят «мимо» вершины Г или до которых можно дойти, минуя вершину Г:
• Теперь посчитаем результаты по оставшимся вершинам:

М = И + Е + К = 6 + 6 + 9 = 21 (получили из последующих шагов)
-----
 И = Е = 6 (получили из последующих шагов)
 Е = Г + Ж = 3 + 3 = 6 (получили из последующих шагов)
 Г = Б + А + Д = 1 + 1 + 1 = 3 (получили из последующих шагов)
 Ж = Г = 3
 К = Е + Ж = 6 + 3 = 9  

Результат: 21

ЕГЭ по информатике 2017 задание 15 ФИПИ вариант 14 (Крылов С.С., Чуркина Т.Е.):
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей, ведущих из города А в город М и не проходящих через город Г?

Решение:

• Удалим ребра, которые проходят через вершину Г:
• Теперь посчитаем результаты по оставшимся вершинам:

М = И + Е + К = 7 (получили из последующих шагов)
-----
И = В + Е = 3 (получили из последующих шагов)
 В = 1
Е = В + Ж = 2 (получили из последующих шагов)
 Ж = 1
К = Е = 2 

Результат: 7

15 задание. Демоверсия ЕГЭ 2018 информатика:

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город М, проходящих через город Ж?

• Удалим ребра, которые не проходят через вершину Ж: Е-И, З-И. Таким образом в вершину И есть только один путь Ж-И 
• Теперь посчитаем результаты по оставшимся вершинам:

М = К+Л = 20
К=Л=И=10
И = Ж =10
Ж = Е+Б+В+Г+Д+З = 1+1+4+2+1+1 = 10
Е = Б=А=1
В = Б+А+Г=1+1+2=4
Г = Д+А =1+1 =2
Д=А =1
З=Д=1
 Результат: 20

ЕГЭ по информатике 2017, задание из сборника Ушакова Д.М, 1 вариант:
3. На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населенных пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта Д в пункт К. В ответе запишите целое число — так, как оно указано в таблице.

Решение:

А — > 2 ребра (Г, В)
В — > 4 ребра (А, Г, К, Д)
Г — > 4 ребра (А, В, К, Д)
Б — > 2 ребра (Г, К)
К — > 5 ребер (Б, Г, В, Д, Е)
Е — > 2 ребра (К, Д)
Д — > 3 ребра (В, К, Е)

• Рассмотрим граф и посчитаем количество ребер из каждой вершины:
• Мы выделили вершины, с уникальным числом ребер: 3 ребра соответствует только Д, а 5 ребер соответствует только К.
• Рассмотрим таблицу и найдем те строки или столбцы, в которых 5 значений и 3 значения: Это П2 и П4.
• Получаем П2 соответствует Д, а П4 соответствует К. На пересечении находится цифра 20.

Результат: 20

Ответ: 20

3 задание. Демоверсия ЕГЭ 2018 информатика (ФИПИ):

На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).

Так как таб­ли­цу и схему ри­со­ва­ли не­за­ви­си­мо друг от друга, то ну­ме­ра­ция населённых пунк­тов в таб­ли­це никак не свя­за­на с бук­вен­ны­ми обо­зна­че­ни­я­ми на графе. Определите, ка­ко­ва длина до­ро­ги из пунк­та А в пункт Г. В от­ве­те за­пи­ши­те целое число — так, как оно ука­за­но в таблице.

Решение:

A -> 3 (В Г Д)
Б -> 1 (В)
В -> 4 (А Б Г Е)
Г -> 4 (А В Д К)
Д -> 2 (А Г)
Е -> 1 (В)
К -> 1 (Г)

• Посчитаем сколько ребер у каждой вершины:
• Три ребра имеет только одна вершина — А, поэтому только А может соответствовать П3.
• Уникальное значение количества ребер имеет также вершина Д, — два ребра. В таблице вершине Д будет соответствовать П4.
• Вершины Г и В имеют по 4 ребра. Рассмотрим матрицу, в ней 4 числа соответствуют пунктам П2 и П5.
• С пунктом Д пересекается только вершина Г (Г -> 4 (А В Д К)). В весовой матрице с вершиной Д пресекается П5. Значит вершина Г соответствует П5.
• В П5 на пересечении с П3 находится число 6.

Результат: 6

ДЗ: решаем задания 3 и 15 из КИМ