Question

СРОЧНО ! ДАЮ МАКСИМУМ БАЛЛОВ !! ПОМОГИТЕ ПОЖАЛУЙСТА !! ПРОШУ ! выполнить два задания. (варианты ОГЭ)



4. (номер 1187) Между населенными пунктами A, B, C, D, E, F построены дороги, протяженность которых (в километрах) приведена в таблице. Определите длину кратчайшего пути между пунктами A и F, проходящий через пункт D. Передвигаться можно только по дорогам, протяженность которых указана в таблице. (желательно прикрепить чертёж)



9. (номер 1275) На рисунке - схема дорог, связывающих города A, B, C, D, E, F, G и H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город H, не проходящих через город D ?


сайт kpolyakov.spb.ru 15 вариант

Answer 1

Ответ:

во втором задании ответ =

Answer 2

Ответ:

4. 14

9. 5

Объяснение:

4. построим граф (картинка 1) или дерево (картинка 2, вычеркнуты пути, которые не приводят в D)

По ним видно, что добраться из A в F через D можно 2 путями, посчитаем их длину

ADF = 10 + 5 = 15

ABDF = 5 + 4 + 5 = 14

Длина кратчайшего пути между пунктами A и F, проходящий через пункт D, равна 14

9. картинка 3

Т.к. по условию нам нужны пути не проходящих через город D, то вычеркнем все пути ведущие в D (AD) и из него (DG и DE)

Начала пути (A) всегда 1 путь

A = 1

Дальнейшее количество путей - сумма от входящих путей (стрелочек).

Вычеркнутые пути НЕ считаем.

B = A = 1

E = A = 1 (DE вычеркнут)

и т.д.

Существует 5 различных путей из города A в город H, не проходящих через город D