Главная страница
Навигация по странице:

  • Известно, что длина кратчайшего пути из пункта А в пункт Ж не больше 15.

  • ege полякова 1. Использование и анализ информационных моделей (таблицы, диаграммы, графики)


    Скачать 1.12 Mb.
    НазваниеИспользование и анализ информационных моделей (таблицы, диаграммы, графики)
    Анкорege полякова 1
    Дата06.02.2022
    Размер1.12 Mb.
    Формат файлаdoc
    Имя файлаege1.doc
    ТипДокументы
    #352780
    страница2 из 8
    1   2   3   4   5   6   7   8

    Ещё пример задания:


    Р-09. На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Известно, что длина кратчайшего пути из пункта А в пункт Ж не больше 15. Определите, какова длина кратчайшего пути из пункта Д в пункт В. В ответе запишите целое число – так, как оно указано в таблице.

    ðŸð¾ð»ð¾ñ‚ð½ð¾ 195

    Решение:

    1. сложность этой задачи в том, что схема симметрична; легко понять, что без дополнительных данных (используя только степени вершин – количество связанных с ними ребёр) мы не сможем различить вершины А и В, Г и Е, Д и Ж

    2. определим степени вершин:







    П1

    П2

    П3

    П4

    П5

    П6

    П7




    Г, Е

    П1




    11

    7

    5







    12

    4

    Б

    П2

    11










    13

    8

    14

    4

    Д, Ж

    П3

    7







    15




    10




    3

    Д, Ж

    П4

    5




    15







    9




    3

    А, В

    П5




    13










    6




    2

    Г, Е

    П6




    8

    10

    9

    6







    4

    А, В

    П7

    12

    14
















    2




    1. как и видно из рисунка, у нас две вершины степени 2 (А и В), две вершины степени 3 (Д и Ж) и три вершины степени 4 (Б, Г и Е), причем вершина Б однозначно определяется как вершина степени 4, которая связана с двумя вершинами степени 2

    2. для того, чтобы различить оставшиеся вершины, определим длины путей ЖГА, ЖЕВ, ДГА и ДЕВ; мы не знаем, где какой маршрут, но точно знаем, что эти четыре маршрута

    П3  П1  П7 = 7 + 12 = 19

    П3  П6  П5 = 10 + 6 = 16

    П4  П1  П7 = 5 + 12 = 17

    П4  П6  П5 = 9 + 6 = 15

    1. из дополнительного условия (Известно, что длина кратчайшего пути из пункта А в пункт Ж не больше 15.) находим, что маршрут ЖГА – последний, так что П4 = Ж, П6 = Г и П5 = А; в итоге получается




      Е

      Б

      Д

      Ж

      А

      Г

      В

      Е




      11

      7

      5







      12

      Б

      11










      13

      8

      14

      Д

      7







      15




      10




      Ж

      5




      15







      9




      А




      13










      6




      Г




      8

      10

      9

      6







      В

      12

      14
















    2. кратчайший путь из Д в В можно найти с помощью дерева возможных маршрутов – это будет путь ДЕВ длиной 19

    3. Ответ: 19.



    1   2   3   4   5   6   7   8


    написать администратору сайта