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

  • Возможные проблемы

  • ььь. Графы. Поиск количества путей


    Скачать 1.47 Mb.
    НазваниеГрафы. Поиск количества путей
    Дата23.09.2022
    Размер1.47 Mb.
    Формат файлаdoc
    Имя файлаege13 (2).doc
    ТипДокументы
    #691944
    страница5 из 7
    1   2   3   4   5   6   7

  • и последние 2 шага

    вершина

    откуда?

    N

    Б

    А

    1

    В

    АБГ

    3

    Г

    А

    1

    Д

    БВ

    4

    Е

    Г

    1

    Ж

    ВЕ

    4

    И

    Д

    4

    К

    ИДЖЕ

    13


  • Ответ: 13.

    Решение (4 вариант, перебор всех путей с начала, А. Яфарова):

    1. запишем все вершины, в которые есть прямой путь из вершины A: Б, В и Г; получается три начальных отрезка:

    АБ, АВ, АГ

    1. рассмотрим маршрут АБ: из Б можно ехать в В и Д, поэтому получаем два маршрута:

    АБВ, АБД

    1. рассматриваем конечные точки этих маршрутов: из В можно ехать в Д и Ж, а из Д – в И и К:

    АБВД, АБВЖ, АБДИ, АБДК

    1. снова смотрим на конечные точки: из Д едем в И и К, из Ж и И – только в К:

    АБВДИ, АБВДК, АБВЖК, АБДИК, АБДК

    1. из И едем только в К, таким образом, все возможные маршруты, содержащие участок АБ, доведены до конечной точки К, всего 5 таких маршрутов:

    АБВДИК, АБВДК, АБВЖК, АБДИК, АБДК

    1. затем аналогично рассматриваем маршруты, которые начинаются с АВ:

    АВД, АВЖ

    АВДИ, АВДК, АВЖК

    АВДИК, АВДК, АВЖК

    всего 3 маршрута

    1. наконец, остается рассмотреть маршруты, которые начинаются с АГ:

    АГВ, АГЕ

    АГВД, АГВЖ, АГЕЖ, АГЕК

    АГВДИ, АГВДК, АГВЖК, АГЕЖК, АГЕК

    АГВДИК, АГВДК, АГВЖК, АГЕЖК, АГЕК

    всего 5 маршрутов

    1. складываем количество маршрутов для всех начальных участков: 5 + 3 + 5 = 13

    2. Ответ: 13.

    Возможные проблемы:

      • при большом количестве маршрутов легко запутаться и что-то пропустить

    Решение (5 вариант, графический, О.О. Грущак, КузГПА):

    1. Главную идею решения: (число дорог в город N есть сумма дорог, приводящих в города, из которых есть прямой проезд в город N), отразим на самой схеме, показывая на ней ЧИСЛО ДОРОГ, приводящих в каждый город.

    2. Последовательность очевидна: начинаем с Б и Г (городов, куда есть по 1-й дороге из А)

    ðŸð¾ð»ð¾ñ‚ð½ð¾ 82

    1. Посчитаем дороги в В: 1 (из A)+ 1(дороги города Б)+ 1(дороги города В)= 3

    ðŸð¾ð»ð¾ñ‚ð½ð¾ 109

    1. Аналогично посчитаем дороги в Д, И, Е, Ж:

    ðŸð¾ð»ð¾ñ‚ð½ð¾ 136

    1. Определяем число дорог в город К, как сумму дорог в города, с которыми он связан: Д, И, Ж, Е.

    ðŸð¾ð»ð¾ñ‚ð½ð¾ 169

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


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