Ориентированный граф

Слайд 2

В9. Задача на «количество различных путей из одной вершины в другую»

Ориентированный граф.
Разрешимость

В9. Задача на «количество различных путей из одной вершины в другую» Ориентированный
задачи требует отсутствия циклов.

Слайд 4

Задача на «количество различных путей из одной вершины в другую»

Способ 1. Перебор

Задача на «количество различных путей из одной вершины в другую» Способ 1.
всех возможных путей «методом наблюдения»

Все пути с АБ:
АБДИЛ, АБДЖЛ, АБВДИЛ, АБВДЖЛ, АБВЖЛ
2. Все пути с АВ:
АВДИЛ, АВДЖЛ, АВЖЛ
3. Все пути с АГ:
АГВДИЛ, АГВДЖЛ, АГВЖЛ, АГЕЖЛ, АГЕКЛ

13 ПУТЕЙ

Слайд 6

Все пути с АБ:
АБДЛ, АБДИЛ, АБВДИЛ, АБВДЛ, АБВЖЛ
2. Все пути с АВ:
АВЖЛ,

Все пути с АБ: АБДЛ, АБДИЛ, АБВДИЛ, АБВДЛ, АБВЖЛ 2. Все пути
АВДИЛ, АВДЛ
3. Все пути с АГ:
АГВДИЛ, АГВДЛ, АГВЖЛ, АГЕЖЛ, АГЕКЛ

13 ПУТЕЙ

Слайд 7

2013-В9. Задача на «количество различных путей из одной вершины в другую»

Способ 2.

2013-В9. Задача на «количество различных путей из одной вершины в другую» Способ
Пошаговое построение всех возможных путей

Все вершины из А:
АБ, АВ, АГ
2. Все вершины, содержащие
2 ребра:
АБД, АБВ, АВД, АВЖ, АГВ, АГЕ
3. Все вершины, содержащие 3 ребра:
АБДИ, АБДЖ, АБВД, АБВЖ, АВДИ, АВДЖ, АВЖЛ, АГВД, АГВЖ, АГЕЖ, АГЕК
4. Все вершины, содержащие 4 ребра: АБДИЛ, АБДЖЛ, АБВДИ, АБВДЖ, АБВЖЛ, АВДИЛ, АВДЖЛ, АГВДИ, АГВДЖ, АГВЖЛ, АГЕЖЛ, АГЕКЛ
5. Все вершины, содержащие 5 ребер: АБВДИЛ, АБВДЖЛ, АГВДИЛ, АГВДЖЛ

13 ПУТЕЙ

Слайд 8

Задача на «количество различных путей из одной вершины в другую»

Способ 3. Подстановка

Задача на «количество различных путей из одной вершины в другую» Способ 3.
1.

13 ПУТЕЙ

1. Вершины, в которые можно прибыть
только из А: NБ=NГ=1
2. NЛ=NИ+NЖ+NК=
=NД+(NД+NВ+NЕ)+NЕ=
=2NД+2NЕ+NВ= 2(NБ+NВ)+2NГ+NВ=
=2NБ+2NГ+3(NБ+NА+NГ)=2+2+9=13

Слайд 9

Задача на «количество различных путей из одной вершины в другую»

Способ 4. Подстановка

Задача на «количество различных путей из одной вершины в другую» Способ 4. Подстановка 2. 13 ПУТЕЙ
2.

13 ПУТЕЙ

Слайд 10

Задача на «количество различных путей из одной вершины в другую»

Задачи для тренировки

Задача на «количество различных путей из одной вершины в другую» Задачи для тренировки