Информатика ОГЭ 2024 задание 9.

Вариант 1

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

Схема дорог

Решение:

Для каждой вершины направленного графа (города), определяем число путей.

А = 1; Б = 1; В = 1; Г = 1; Д = 1;

Е = 1; З = 1; И = 2; Е = 1; Ж = 6;

Из города А через город Ж проходит 6 путей в город К.

Ответ: 6.

Вариант 2

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

Схема дорог

Решение:

Для каждой вершины направленного графа (города), определяем число путей.

А = 1; В = 1; Б = 2; Г = 1; Д = 1;

Е = 2; З = 1; И = 2; Е = 2; Ж = 8;

Из города А через город Ж проходит 8 путей в город К.

Ответ: 8.

Вариант 6

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

Схема дорог

Решение:

Для каждой вершины направленного графа (города), определяем число путей.

А = 1; В = 1; через В в Б = 1; Е = 1;

через В в Ж = 3;

Из города А через город В проходит 4 (Е + Ж) путей в город К.

Ответ: 4.

Вариант 7

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

Схема дорог

Решение:

Для каждой вершины направленного графа (города), определяем число путей.

А = 1; Б = 1; через Б в В = 2; Г =1; Д = 1; И = 2;

Из города А через город З проходит 5 (В + Г + И) путей в город К.

Ответ: 5.

Вариант 12

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

Схема дорог

Решение:

Для каждой вершины направленного графа (города), определяем число путей.

А =1; Б = 1; Г =1;

В = 2;

Д = 3;

Е = 3;

Ж = 8 (Е +В + Д);

З = 9 (Ж + Г);

К = 20 (Е + Ж + З)

Ответ: 20

Вариант 13

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

Схема дорог

Решение:

Для каждой вершины направленного графа (города), определяем число путей.

А =1; В = 1; Б = 2; Г =1;

Д = 2;

Е = 3;

Ж = 2;

К = 3 (Е) + 2 (Ж через Д) = 5

Ответ: 5

Вариант 15

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

Схема дорог

Решение:

Для каждой вершины направленного графа (города), определяем число путей.

А = 1; В = 1; Д = 1;

Г = 2;

Ж = 1 (В) + 2 (Г) + 1 (Д) = 4 ;

Ответ: 4.