Подготовка к ОГЭ по информатике. Теория графов. Задание № 11
©кабинет 21, 2006-2015
Теория графов. ОГЭ-11
1
. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
Пояснение.
Начнем считать количество путей с конца маршрута – с города К. NX — количество различных путей из города А в город X, N — общее число путей.
В "К" можно приехать из И, Ж, Е, или З, поэтому N = NК = NИ + NЖ + N Е + NЗ (1)
Аналогично:
NИ = NД;
NЖ = NД + NВ + NЕ;
NЕ = NВ + NГ;
NЗ = NЕ.
Добавим еще вершины:
NД = NБ + NВ;
NВ = NА + NБ + NГ = 1 + 1 + 1 = 3;
NГ = NА = 1;
NБ = NА = 1.
Преобразуем первые вершины с учетом значений вторых:
NИ = NД = NБ + NВ = 1 + 3 = 4;
NЖ = NД + NВ + NЕ = 4 + 3 + 4 = 11;
NЕ = NВ + NГ = 3 + 1 = 4;
NЗ = NЕ = 4.
Подставим в формулу (1):
N
= NЖ = 4 + 11 + 4 + 4 = 23
Ответ: 23
2. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
Пояснение.
Начнем считать количество путей с конца маршрута – с города К. NX — количество различных путей из города А в город X, N — общее число путей.
В "K" можно приехать из Е, Ж, З или И, поэтому N = NК = NЕ + NЖ + N З + NИ (1)
А
Быстрее и проще не писать многократно повторяющиеся части формул «N» и «+», тогда:
К = Е Ж З И = 5+2+3+2 = 12
Е=БЖ =5
Ж=В=2
З=ГЖ=3
И= Д=2
Б= АВ =3
В=АГ =2
Г=А =1
Д=АГ =2
налогично:NЕ = NБ + NЖ;
NЖ = NВ;
NЗ = NГ + NЖ;
NИ = NД.
Д
ля следующих вершин:
NБ = NА + NВ = 3;
NВ = NА + NГ = 2;
NГ = NА = 1;
NД = NА + NГ = 1 + 1 = 2.
Преобразуем первые вершины:
NЕ = NБ + NЖ = 3 + 2 = 5;
NЖ = NВ = 2;
NЗ = NГ + NЖ = 1 + 2 =3;
NИ = NД = 2.
Подставим в формулу (1):
N = NК = NЕ + NЖ + N З + NИ = 5 + 3 + 2 + 2 = 12. Ответ: 12
3. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
Другой вариант решения (сначала):
- если подписывать к каждой букве (кроме А, разумеется) количество путей которые к ней ведут.
Б
=1 (из А)
Г=1 (из А)
В=1(из А)+1(из Б)+1(из Г)=3
Д=1(из Б)+3(из В)=4
Е=1(из Г)
Ж=3(из В)+4(из Д)+1(из Е)=8
И=4(из Д)
Л=1(из Е)
К=4(из И)+8(из Ж)+1(из Е)+1(из Л)=14
Ответ: 14
Задания для самостоятельного выполнения
1. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город И?
2. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?
3
. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
4. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город З?
