Анализирование информации представленной в виде схем.Графы

Анализирование информации представленной в виде схем Графы

Если в город  R  из города  A  можно добраться только из городов  X ,  Y  и  Z , то  количество различных путей из города A в город R равно сумме числа различных путей проезда из A в X, из A в Y и из A в Z , то есть:

где N R  — это количество путей из вершины A в вершину R

Число путей не бесконечно, исключением является только схема, в которой есть циклы – замкнутые пути.

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

Д  и  А-Г . Учтем это при дальнейших расчетах. Решим задание с конца. Т.е. так как траектория поиска путей — от  А  до  K , то мы будем рассматривать сначала город  K . В город  K  можно попасть из трех городов —  Д, E  и  Ж ; запишем это так: K = Д + Е + Ж Теперь аналогично рассмотрим города  Д, Е  и  Ж : Д = В (Б - Д не учитываем) Е = Д + В Ж = В + Г" width="640"

Как видим, таких дорог получилось две —  Б-Д  и  А-Г . Учтем это при дальнейших расчетах.

Решим задание с конца. Т.е. так как траектория поиска путей — от  А  до  K , то мы будем рассматривать сначала город  K .

В город  K  можно попасть из трех городов —  Д, E  и  Ж ; запишем это так:

K = Д + Е + Ж

Теперь аналогично рассмотрим города  Д, Е  и  Ж :

Д = В (Б - Д не учитываем) Е = Д + В Ж = В + Г

Далее, рассмотрим каждый город, дойдя до первого — города  А . Для него существует  только одни путь . Также, для городов,  выходящих только из города А, тоже существует только 1 путь . Таким образом имеем:

К = Д + Е + Ж

Д = В

Е = Д + В

Ж = В + Г

К = Д + Е + Ж

Д = В

Е = Д + В

Ж = В + Г

Д = В = 2

Ж = B + Г = 2 + 2 = 4

Е = Д + В = 2 + 2 = 4

Поскольку нас интересуют пути, проходящие через город  В , то вычеркнет те дороги, которые минуют город В:

К = Д + Е + Ж = 2 + 4 + 4 = 10

Самостоятельная работа

Задание 1

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

Задание 2

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

Ответы

Задание 1

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

К = И + Ж И = Ж Ж = Д + В + Е Ж = Д + В + Е = 4 + 3 + 4 = 11 И = Ж = 11 К = И + Ж = 22 Ответ:  22

Задание 2

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

H = C + D + G C = D + A D = A + E G = D + E + F G = D + E + F = 3 + 2 + 1 = 6 D = A + E = 1 + 2 = 3 C = D + A = 3 + 1 = 4 H = C + D + G = 4 + 3 + 6 = 13 Ответ:  13

Однозначное соотнесение таблицы и графа

Задание 1.

На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта В в пункт Е . В ответе запишите целое число  — так, как оно указано в таблице.

Решение.

Пункт В   — единственный пункт с пятью дорогами, значит, ему соответствует П6 , а пункт Е − единственный с четырьмя дорогами, значит, ему соответствует П4 .

Длина дороги из П6 в П4 равна 20.

Ответ: 20.

Задание 2.

На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта Г в пункт Е . В ответе запишите целое число  — так, как оно указано в таблице.

Пункт Г   — единственный пункт с тремя дорогами, значит, ему соответствует П2 , а пункт Е   — единственный с четырьмя дорогами, значит, ему соответствует П4 .

Длина дороги из П2 в П4 равна 40.

Ответ: 40.

Самостоятельная работа

Задание 1

На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта В в пункт Г . В ответе запишите целое число  — так, как оно указано в таблице.

Задание 2

На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта Б в пункт Д В ответе запишите целое число  — так, как оно указано в таблице.

Ответы

• Задание 1 . Пункт В   — единственный пункт с пятью дорогами, значит, ему соответствует П6 , а пункт Г   — единственный с тремя дорогами, значит, ему соответствует П2 . Длина дороги из П6 в П2 равна 55. 
• Ответ: 55.
• Задание 2. Есть только один пункт, из которого ведёт 5 дорог,  — это В , а в таблице  — П6 . Из А ведёт две дороги, и одна из них  — в В . В таблице такому соответствует П5 . Из Б ведёт три дороги, причём есть дороги в А и в В , в таблице под такое подходит только П3 . Из Д три дороги, две из которых  — в Б и в В , в таблице только один пункт такому соответствует  — П7 . Таким образом, Б   — это П3 , а Д   — П7 . Длина дороги между П3 и П7   — 8. Ответ: 8.