Главная страница

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


Скачать 2.33 Mb.
НазваниеГрафы. Поиск количества путей
Дата12.12.2022
Размер2.33 Mb.
Формат файлаdoc
Имя файлаege13.doc
ТипРешение
#840964
страница5 из 9
1   2   3   4   5   6   7   8   9

Р ешение (3 вариант, перебор вершин по алфавиту):

  1. Запишем вершины в алфавитном порядке и для каждой из них определим, из каких вершин можно в нее попасть

Б  А

В  АБГ

Г  А

Д  БВ

Е  Г

Ж  ВЕ

И  Д

К  ИДЖЕ

  1. теперь определяем количество путей; сначала ставим 1 для тех вершин, в которые можно проехать только из начальной (А):

    вершина

    откуда?

    N

    Б

    А

    1

    В

    АБГ

    Г

    А

    1

    Д

    БВ

    Е

    Г

    Ж

    ВЕ

    И

    Д

    К

    ИДЖЕ


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

    вершина

    откуда?

    N

    Б

    А

    1

    В

    АБГ

    3

    Г

    А

    1

    Д

    БВ

    Е

    Г

    1

    Ж

    ВЕ

    И

    Д

    К

    ИДЖЕ


  3. следующий шаг

    вершина

    откуда?

    N

    Б

    А

    1

    В

    АБГ

    3

    Г

    А

    1

    Д

    БВ

    4

    Е

    Г

    1

    Ж

    ВЕ

    4

    И

    Д

    К

    ИДЖЕ

    1   2   3   4   5   6   7   8   9


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