Моделирование. Графы.

Моделирование Графы

МАОУ СШ № 8 г. Бор Нижегородской обл.

Кустова Юлия Евгеньевна

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

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

Для решения этой задачи достаточно найти такое значение в таблице, где пересекаются пункт В и Е.

В

Е

Е

В

Алгоритм

• Обозначить пункты поиска;
• Посчитать сколько дорог ведут в эти пункты;

• Найти в таблице строки (столбцы), удовлетворяющие данному критерию;
• Смотрим значение в таблице пересечения этих путей.

Ответ: 20

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

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

Б

Е

Д

А

В

Б

Е

А

В

Д

Б –3 дороги (П2 либо П3 либо П7)

Д –3 дороги (П2 либо П3 либо П7)

Б и Д имеют развязку с городом В, который связан с другими городами 5 дорогами

В имеет развязку с городом А, который связан с другими городами 2 дорогами , в том числе с городом Б

Е имеет 4 дороги

Д имеет 3 дороги в города Б, В, Г

Расстояние из Б в Д 11 км

Ответ: 11

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

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

Е

Г

Г – 3 дороги (П2)

Г

Е – 4 дороги (П4)

Е

Расстояние из Г в Е 40 км

Ответ: 40

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

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

Е

П1

П1

П2

П2

П3

П3

57

57

П4

П4

П5

22

20

20

П5

22

П6

42

П6

42

П7

П7

25

8

8

25

23

23

21

21

8

7

7

8

33

33

9

9

В

Д

А

К

Г

Б

П1

П1

П2

П2

П3

57

П3

57

П4

П4

П5

20

22

22

П5

20

42

П6

П6

42

П7

25

25

8

8

П7

23

23

21

21

7

8

7

8

33

33

9

9

Г – 5 дорог (П2)

Б

А

Г

А –3 дороги (П1 либо П3 либо П6)

Г

Б имеет 2 дороги (П5)

А

Б граничит с А, Г, следовательно А (П3)

Б

Расстояние из А в Г 22 км

Е

В

Д

А

К

Г

Б

Ответ: 22

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

Е

К

Г

В

Д

К

Г

20

15

Е

20

35

10

В

25

20

Д

20+25=45

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

Ответ: 45

Пример 6. Демонстрационный вариант 2019

Определите, какие номера населенных пунктов в таблице могут соответствовать населенным пунктам В и С на схеме. В ответе запишите эти два номера в возрастающем порядке.

двухдорожные

трехдорожные

Найдем отличия трёхдорожных городов В, F, C?

В и C имеют развязки с двумя двухдорожными и одним трёхдорожным узлами. А F и G имеет развязку иную: с двумя трёхдорожными и одним двухдорожным узлом.

Проанализируем эту информацию по таблице

В и C (трёхдорожные) ?

Обратите внимание, мы не можем определить точно где В, а где С.

Нам это не важно. А важно найти номер В и С.

Номер одного из них это 2, а номер другого это 6. Нам необходимо записать их в порядке возрастания.

Ответ: 26

Задание для самостоятельного решения

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

В

Г

Д

Е

15

В

5

Г

Д

25

Е

10

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

Ответ: 20

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

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

Б –3 дороги (П2 либо П3 либо П7)

В

Д

Б

А

Е

Д –3 дороги (П2 либо П3 либо П7)

Б

Б и Д имеют развязку с городом В, который связан с другими городами 5 дорогами

Е

А

В

Е имеет 4 дороги

Д

В имеет развязку с городом А, который связан с другими городами 2 дорогами , в том числе с городом Б

Из Б можно съездить в А, В, Д

Расстояние из Б в Д 8 км

Ответ: 8

№

Проверяемые элементы содержания

3

Умение представлять и считывать данные в разных типах информационных

Коды проверяемых элементов содержания (по кодификатору)

моделей (схемы, карты, таблицы, графики и формулы)

Коды проверяемых требований к уровню подготовки (по кодификатору)

1.3.1

Уровень сложности задания

1.2.2

Макс. балл за выполнение задания

Б

Примерное время выполнения задания (мин.)

1

3