Теория графов ОГЭ по информатике задание № 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. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город З?