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

  • Решение (1 способ, перебор вариантов)

  • Решение (2 способ, через построение графа, М.В. Кузнецова)

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


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

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


    Р-05. Между населёнными пунктами A, B, C, D, E, F, Z построены дороги с односторонним движением. В таблице указана протяжённость каждой дороги. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет. Например, из A в B есть дорога длиной 4 км, а из B в A дороги нет.




    A

    B

    C

    D

    E

    F

    Z

    A




    4

    6










    30

    B







    3













    C










    11







    27

    D













    4

    7

    10

    E
















    4

    8

    F













    5




    2

    Z

    29



















    Сколько существует таких маршрутов из A в Z, которые проходят через 6 и более населенных пунктов? Пункты A и Z при подсчете учитывать. Два раза проходить через один пункт нельзя.

    Решение (1 способ, перебор вариантов):

    1. обратим внимание, что числа в таблице нас совсем не интересуют – достаточно знать, что между данными пунктами есть дорога

    2. нам нужно найти все пути, которые проходят через 6 и более пунктов, считая начальный и конечный; то есть между A и Z должно быть не менее 4 промежуточных пункта

    3. начнем с перечисления всех маршрутов из А, которые проходят через 2 пункта; по таблице видим, что из A можно ехать в B, C и Z; количество пунктов на маршруте будем записывать сверху:

      2

      3

      4

      5

      6

      7

      AB
















      AC
















      AZ
















    4. маршрут AZ нас не интересует, хотя он и пришел в конечный пункт, он проходит меньше, чем через 6 пунктов (только через 2!); здесь и далее такие «неинтересные» маршруты из A в Z будем выделять серым фоном

    5. теперь ищем все маршруты, проходящие через 3 пункта; из B можно ехать только в C, а из С – в D и Z:

      2

      3

      4

      5

      6

      7

      AB

      ABC













      AC

      ACD













      ACZ













      AZ
















    6. далее из C едем в D и Z, а из D – в E, F и Z:

      2

      3

      4

      5

      6

      7

      AB

      ABC

      ABCD










      ABCZ










      AC

      ACD

      ACDE










      ACDF










      ACDZ










      ACZ













      AZ
















    7. строим следующий уровень только для тех маршрутов, которые ещё не пришли в Z:

      2

      3

      4

      5

      6

      7

      AB

      ABC

      ABCD

      ABCDE







      ABCDF







      ABCDZ







      ABCZ










      AC

      ACD

      ACDE

      ACDEF







      ACDEZ







      ACDF

      ACDFE







      ACDFZ







      ACDZ










      ACZ













      AZ
















    8. следущие два уровня дают «интересные» маршруты, проходящие через 6 или 7 пунктов:

    2

    3

    4

    5

    6

    7

    AB

    ABC

    ABCD

    ABCDE

    ABCDEF

    ABCDEFZ

    ABCDEZ




    ABCDF

    ABCDFE

    ABCDFEZ

    ABCDFZ




    ABCDZ







    ABCZ










    AC

    ACD

    ACDE

    ACDEF

    ACDEFE




    ACDEFZ




    ACDEZ







    ACDF

    ACDFE

    ACDFEF




    ACDFEZ




    ACDFZ







    ACDZ










    ACZ













    AZ



















    1. на последней схеме зелёным фоном выделены «интересные» маршруты, их всего 6; красным фоном отмечены маршруты, в которых получился цикл – они дважды проходят через один и тот же пункт; такие маршруты запрещены и мы далее их не рассматриваем

    2. Ответ: 6.

    3. можно было нарисовать схему возможных маршрутов в виде дерева:



    Решение (2 способ, через построение графа, М.В. Кузнецова)

    1. Построим граф, соответствующий таблице. Наличие значений преимущественно на диагонали таблицы говорит о наличии дорог, последовательно связывающих указанные населенные пункты (A-B, B-C, …). Построение графа начнем с размещения узлов (населенных пунктов), располагая их «по кругу», а затем последовательно изобразим все указанные в таблице дороги. Так как нас интересует только число дорог, проходящих через 6 и более пунктов, то длины дорог (веса ребер) указывать не будем.

      ðŸð¾ð»ð¾ñ‚ð½ð¾ 1

      ðŸð¾ð»ð¾ñ‚ð½ð¾ 37

      Из А исходит три дороги, но ясно, что дорога A-Z нас не интересует.

      Из B исходит одна дорога,
      из С - две…

      ðŸð¾ð»ð¾ñ‚ð½ð¾ 61

      ðŸð¾ð»ð¾ñ‚ð½ð¾ 88

      Из D исходит три дороги, из Е – две.

      Из F выходят две дороги, причём одна возвращает в Е (рисуем новую стрелку, FE и EF – разные дороги).

    2. Анализ графа.

    Общее число пунктов 7. Есть дороги, последовательно связывающие все 7 пунктов, значит 1-й путь: ABCDEFZ.

    ðŸð¾ð»ð¾ñ‚ð½ð¾ 120

    Есть 3 дороги, которые позволяют «проехать мимо» соседнего пункта (AC идёт «мимо» B, DF – мимо E,…), значит, есть 3 способа проехать через 6 пунктов (ACDEFZ, ABCDFZ, ABCDEZ).

    ðŸð¾ð»ð¾ñ‚ð½ð¾ 148 ðŸð¾ð»ð¾ñ‚ð½ð¾ 176
    Есть одна «обратная дорога», позволяющая изменить порядок прохождения пунктов – FE. Эта дорога при наличии дороги DF, идущей «мимо» Е, создает дополнительные маршруты: один через 7 пунктов ABCDFEZ и один через 6 пунктов ACDFEZ.

    ðŸð¾ð»ð¾ñ‚ð½ð¾ 204 ðŸð¾ð»ð¾ñ‚ð½ð¾ 232 ðŸð¾ð»ð¾ñ‚ð½ð¾ 288


    1. Вывод: общее число дорог, соответствующих условию: 1+3+2=6

    2. Ответ: 6
    1   2   3   4   5   6   7   8


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