Основное меню

Контакты

Главная / Подготовка к ЕГЭ / Графы

15 - Графы

Пример решения задачи:

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

Графический способ. Начнем с конца. В точку К можно попасть двумя способами: из точки Д и из точки Е.

В точку Д можно попасть из точек Б и В. А в точку Е из точек В и Г и т.д. Ход рассуждения отображен на схематичном рисунке.

Из рисунка видно, что у нас получилось различных 8 путей от начального пункта А до конечного пункта К.

Ответ: 8

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

Графический способ нагляден для небольшого количества путей. Иначе можно сбиться. Второй способ решения - с помощью функции.

Пусть R(X) - функция, равная количеству путей, ведущих от начальной точки к точке X.

Начальная функция R(А) = 1.

R(В) = R(А) = 1 (в точку Б можно попасть только из точки А)

R(Б) = R(А) + R(В) = 1 + 1 = 2 (в точку Б можно попасть из точек А и В)

R(Г) = R(А) + R(В) = 1 + 1 = 2

R(Д) = R(Б) + R(В) = 2 + 1 = 3

R(Ж) = R(В) + R(Г) = 1 + 2 = 3

R(Е) = R(В) + R(Д)+ R(Ж) = 1 + 3 + 3 = 7

R(И) = R(Д) + R(Е) = 3 + 7 = 10

R(К) = R(Ж) = 3

R(Л) = R(Е) + R(Ж)+ R(И)+ R(К) = 7 + 3 + 10 + 3 = 23

Ответ: 23

Тренировочные упражнения:

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

Введите ваш ответ и щелкните мышью на кнопке "Готово".

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

Введите ваш ответ и щелкните мышью на кнопке "Готово".

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

Введите ваш ответ и щелкните мышью на кнопке "Готово".

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

Введите ваш ответ и щелкните мышью на кнопке "Готово".