Задание 3

1. Общие сведения

2. Разбор демо 2017

3. Пример задания

4. Рекомендации для учителей: как разбирать задачу с учениками

5. Правильные ответы

6. История

Посмотрите материалы К.Ю.Полякова вот здесь

1. Общие сведения

Сложность: базовая.

Примерное время решения (для тех, кто будет выполнять часть 2):  2 минуты

Тема: Математические основы информатики

Подтема: Графы

Что проверяется: Задание графа с заданными весами ребер с помощью матрицы  смежности. Поиск кратчайшего пути между заданными вершинами.

Как может выглядеть задание:

Например, так.

Дана таблица, в которой указаны длины дорог между городами. Требуется найти длину кратчайшего пути между двумя указанными городами.

2.Разбор демо варианта 2017

Условие задачи
На рисунке схема дорог Н-ского района изображена в виде графа; в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).
Задание 3, демо 2017
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова протяжённость дороги из пункта Б в пункт В. В ответе запишите целое число – так, как оно указано в таблице.

Решение

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

Задание 3 демо 2017, решение
По изображению на графе находим, что вершина Б имеет степень 3, а вершина В – 4. Так как в графе есть только она вершина степени 4, то вершина В - это пункт 5 (П5). Определить однозначно вершину Б мы пока не можем: в таблице это может быть П1, П2 и П4. Разберемся, какой из пунктов П1, П2 и П4 соответствует какой из вершин Б, Г и Д.

Б - единственная из этих вершин, которая соседствует с вершиной степени 2 (это вершина А). В таблице пункт степени 2 - это П6. Пункт П6 связан дорогой с П1 и не связан дорогами с П2 и П4. Поэтому вершина Б - это П1.

Теперь мы определили нужные нам вершины Б (П1) и В (П5) и можем найти ответ в весовой таблице. Смотрим на пересечение строчки П1 и столбца П5 и получаем, что искомое расстояние равно 8.

Ответ: 8.

Бонус: определим остальные вершины.

Заметим, что вершины А и Е определяются однозначно. Из вершины Е выходит одно ребро и это соответствует П3 в таблице. Вершины А имеет степень 2, и ей соответствует П6 из таблицы.

Вершина Е соединена только с одной вершиной Д. В таблице вершина Е (П3) соединена только с вершиной П4. Таким образом П4 в весовой таблице и является вершиной Д на графе.

Оставшаяся вершина П2 в весовой таблице соответствует вершине Г в графе.

 

3. Пример задания

            2.1. Условие задачи.

Задача 2012-А2-1.   

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

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

 

A

B

C

D

E

F

A

 

2

4

 

 

 

B

 2

 

1

 

7

 

C

4

1

 

3

4

 

D

 

 

3

 

3

 

E

 

4

3

 

2

F

 

 

 

 

2

 

2.2. Набросок решения.  

2.2.1. Перебор путей с учетом особенностей задачи

Полезно для наглядности нарисовать схему дорог (говоря «математически», - граф), соответствующий таблице. На это уйдет меньше минуты, но дальнейшее решение упростится и уменьшится риск сделать ошибку:

Задача поиска кратчайшего пути в графе – одна из классических задач информатики. Общий подход к ее решению приведен ниже. А пока воспользуемся тем, что граф в условии задачи – небольшой, и просто переберем все возможные пути. При этом – будем наблюдательными и постараемся сократить работу.

  1. В пункт  F можно попасть только из пункта E.  Поэтому достаточно найти кратчайший путь из A в E.
  2. Из A можно попасть только в B и C. Из B можно попасть в C и E. Нашелся путь ABE. Его длина – 2+7 = 9.
  3. Все остальные пути из A в E ведут через C.
  4. Из А  в C есть 2 маршрута: “прямой» AC, его длина 4 и через пункт B, его длина 1+2=3. Т.е. кратчайший путь из A в C имеет длину 3.
  5. Из C в E есть 2 маршрута: “прямой» CE, его длина 4 и через пункт D, его длина 3+3=6. Т.е. кратчайший путь из C в E имеет длину 4.
  6. Таким образом, кратчайший путь из A в E, проходящий через C, - это путь ABCE, его длина 3+4=7. Это меньше, чем длина маршрута ABE. Значит, кратчайший путь из A в E имеет длину 7.
  7. А кратчайший маршрут из A в F – это маршрут ABCEF, его длина 7+2=9.

Ответ: 9.

2.2.2.  Систематический перебор вершин

Выпишем все пути из A в  F в алфавитном порядке и подсчитаем их длины. Можно рассматривать только пути без «хождения по кругу», то есть не рассматривать маршруты, которые через одну вершину проходят 2 раза. Итак.

Из A можно пойти только в B и C:

A→B→;

A→C→;

Разберемся с путями через B. Из B можно пойти в A (но это будет путь назад!), а также в C и E (это – разумные продолжения). Заменим в нашем списке путь A→B→ на два его возможных продолжения. Получим (новые верщины выделены жирным шрифтом):

A→B→ C→;

A→B→ E→;

A→C→;

Теперь в нашем списке – три неоконченных маршрута, они перечислены в алфавитном порядке. Снова попробуем продолжить первый из них.

Путь A→B→ C→ можно продолжить двумя способами (не считая путей назад): пойти в D или в E. Получим такой список неоконченных путей:

A→B→ C→ D→;

A→B→ C→ E→;

A→B→ E→;

A→C→;

Путь A→B→ C→ D→ можно продолжить до пути в F только одним способом – пойти в E. Получим:

A→B→ C→ D→ E→;

A→B→ C→ E→;

A→B→ E→;

A→C→;

Из E можно пойти только в F. Значит, из пути A→B→ C→ D→ E→ мы получили полный путь A→B→ C→ D→E→F. Его длина 2+1+3+3+2 = 11.

A→B→ C→ D→E→ F.  Длина 2+1+3+3+2 = 11.

A→B→ C→ E→;

A→B→ E→;

A→C→;

Пути A→B→ C→ E→ и A→B→ E→ тоже можно завершить только одним способом. Теперь наш список путей будет выглядеть так:

A→B→ C→ D→E→ F.  Длина 2+1+3+3+2 = 11.

A→B→ C→ E→F.  Длина 2+1+4+2 = 9.

A→B→ E→ F.  Длина 2+7+2 = 11.

A→C→;

Осталось разобраться с возможными продолжениями неоконченного пути A→C→. Это можно сделать точно так же, как мы поступали с продолжениями пути  A→B→.  У пути A→C→ есть три  продолжения: A→ C→ B→E→ F,  A→ C→ D→E→ F и  A→C→ E→ F.  Таким образом, полный список путей из A в F выглядит так:

1) A→B→ C→ D→E→ F.  Длина 2+1+3+3+2 = 11.

2) A→B→ C→ E→ F.  Длина 2+1+4+2 = 9.

3) A→B→ E→ F.  Длина 2+7+2 = 11.

4) A→C→ BEF.  Длина 4+1+7+2 = 14.

5) A→C→ D→ E→ F.  Длина 4+3+3+2 = 12.

6) A→C→ E→ F.  Длина 4+4+2 = 10.

Кратчайший путь: A→B→ C→ E→ F, его длина – 9.

Ответ. Длина кратчайшего пути: 9. Правильный вариант ответа: 1.

Замечание. На практике перебор можно уменьшить. Например, если неоконченный путь длиннее, чем уже найденный полный путь, то этот неоконченный можно не продолжать. Другой пример. Сравнивая пути A→B→ C→ D→E→ F и A→B→ C→ E→ F (пути 1) и 2) ), мы выяснили, что путь C→ E→ F короче, чем путь C→ D→E→ F. Поэтому при продолжении пути A→C→, вариант A→C→ D→ E→ F можно не рассматривать.

Подобные соображения можно систематизировать и получить более экономный алгоритм поиска кратчайшего пути – алгоритм Дейкстры (Эдгар Дейкстра, 1 мая 1930 г. — 6 августа 2002 – выдающийся голландский ученый, один из создателей современного программирования). Сильным ученикам его можно объяснить, однако для выполнения ЕГЭ в этом нет необходимости.

4. Еще примеры заданий.

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

 

A

B

C

D

E

F

A

8

3

 

 

 

B

 8

 

9

 

4

 

C

3

9

 

3

8

 

D

 

 

3

2

 

E

 

 4

8

2

 

7

F

 


 

 

7

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

 

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

A

B

C

D

E

F

A

2

19

B

2

11

3

8

C

11

4

D

3

2

E

19

8

4

2

6

F

6

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

 

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

 

A

B

C

D

E

F

A

4

8

24

B

4

3

C

8

3

3

8

14

D

3

12

E

8

5

F

24

14

12

5

 

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

 

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

 

A

B

C

D

E

F

Z

A

3

7

29

B

3

2

C

7

2

4

7

14

D

4

99

11

E

7

99

5

F

14

11

5

5

Z

29

5

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

Решение. Есть прямой путь из A в Z, его длина 29. Поищем другие пути.

Видно, что сначала нужно попасть из A в C, потом - из  C в F и, наконец, из F в Z. И на каждом из этих участков надо выбрать самый короткий маршрут.

Из А в С есть два маршрута – по дороге AC и через пункт B. Второй маршрут короче – его длина 3+2 = 5.

Из C в F есть много маршрутов. Однако дорога DE очень длинная и ехать по ней заведомо не стоит – получится маршрут  более длинный, чем по дороге AZ. Осталось сравнить длины двух маршрутов – CDF  и CEF. Более короткий маршрут – CEF, его длина 7+5 = 12 (длина маршрута CDF равна 4+11 = 15).

Наконец, из F в Z есть единственная дорога, ее длина 5. Таким образом, кратчайший маршрут из A в  Z (не считая прямой дороги AZ) = это маршрут ABCEFZ. Его длина 5+ 12 + 5 = 22 < 29. Таким образом, длмна кратчайшего пути из A в Z равна 22.

Ответ: 22

 

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

 

A

B

C

D

E

F

Z

A

3

7

11

27

B

3

31

9

C

7

31

3

D

11

9

3

6

11

14

E

6

33

7

F

11

33

5

Z

27

14

7

5

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

 


Правильные ответы:    3.1:  15;        3.2:  15;       3.3:  20;           3.4:  22;             3.5:  23

5. Рекомендации для учителей: как разбирать задачу с учениками

            Эти рекомендации – не догма, а попытка сделать выводы из собственного опыта. Ждем комментариев и Ваших рекомендаций.

            В разделе 2 приведены два решения.

Второе решение лучше тем, что оно может быть выполнено «автоматически», в отличие от первого, оно не требует от ученика никаких догадок. Если граф путей по сложности примерно такой, как в демо-версии, или даже немного сложнее, на такое решение  вполне хватит двух минут.  При переборе можно использовать соображения, приведенные в замечании.

В первом решении используются два дополнительных соображения. Первое соображение – выделение «узких мест», которые разбивают граф на подграфы меньшего размера; такие подграфы можно исследовать независимо или почти независимо друг от друга. В рассмотренном примере «узкие места» - это вершины D и E. Второе соображение – «длинные» ребра можно игнорировать. В примере таким ребром является ребро BE.

Таким образом, при разборе этого задания с учениками можно поступать так.

1)      Научить учеников уверенно рисовать граф по заданной таблице.

2)      Научить решать задачу полным перебором путей (второе решение).При этом обращать внимание на особенности задачи (как в первом решении).

3)      Для сильных учеников – потренироваться в решении задачи с учетом особенностей («длинные ребра», «узловые точки» - как в первом решении).

4)      *Для сильных учеников - обсудить аналогию между заданием 2 и заданием 26 (С3). Решение задания 2 с помощью составления таблиц (второе решение задачи 26 (С3)).  См. лекцию М.А.Ройтберга "Графы. Подсчет путей и вариантов" в разделе ВИДЕО.

 

 
 

19 комментариев

  1. Торопыжкин:

    почему в А2.4 ответ 1?
    как получить 22?
    обьясните, пожалуйста

  2. A2.2
    ответ будет №1 т.е 13
    а у вас в ответах A2.2: №2 т.е 15
    это опечатка?

    • ege-go:

      Спасибо! Исправил. Наконец, понял, о чем писали михалыч и my65daysofstatic. И вам, ребята, спасибо!

      • Лена М.:

        опечатки вернулись обратно: цифры в условии и в решении расходятся

        • editor:

          В связи с атакой на сайт мы откатились к более ранней версии сайта. Приносим извинения 🙁
          Пересмотрел А2, исправил два бага. Уточните пож, что Вы имеете в виду Спасибо!

  3. прочитайте еще раз пост михалыча и исправьте опечатку пожалуйста. и в таблице первого задания четверка не на месте стоит

    • ege-go:

      Спасибо, четверку передвинул. 🙂
      А что с михалычем? У него вроде про A2.2, A2.3 . Или я ччего не досмотрел?

  4. у меня никак не получается с этим графиком... да и вообщем с задачей туговато...(((

  5. Ольга:

    Я прорешала А2 варианта №5 и у меня получилось 24.
    Из А в С (7), из С в Д (3), из Д в Z (14).
    Сумма 24. Короче пути не нашла.

    • ege-go:

      ACDEZ Длина 7+3+6+7 = 23
      Ребята! Рисуйте графы (т.е. картинки, как показано при разборе демо)!
      задача простая, будет обидно сделать ошибку

  6. ege-go:

    Ребята! При решении этой задачи стоит рисовать картинку (как показано при разборе демо). Если что непонятно - пишите. Удачи!

  7. Андрей:

    опечатки нет Всё верно ты не правильно посчитал!

  8. mihalich:

    а2.3
    вообще правильного варианта нет

  9. mihalich:

    а2.2
    ответ никак не 2, кратчайший путь равен 13, 15 никак не набрать.

  10. oval:

    А кратчайший маршрут из A в F – это маршрут ABCEF, его длина 7+2=9.
    опечатка, должно быть 9+2 = 11

 
 

Ответить ege-go

 




 
 

 
 
Яндекс.Метрика