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

• Название: Графы. Поиск количества путей
• Дата: 12.12.2022
• Размер: 2.33 Mb.
• Имя файла: ege13.doc
• Тип: Решение; #840964
• страница: 5 из 9

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

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

Б  А

В  АБГ

Г  А

Д  БВ

Е  Г

Ж  ВЕ

И  Д

К  ИДЖЕ

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

   вершина	откуда?	N
   Б	А	1
   В	АБГ
   Г	А	1
   Д	БВ
   Е	Г
   Ж	ВЕ
   И	Д
   К	ИДЖЕ

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

   вершина	откуда?	N
   Б	А	1
   В	АБГ	3
   Г	А	1
   Д	БВ
   Е	Г	1
   Ж	ВЕ
   И	Д
   К	ИДЖЕ

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

   вершина	откуда?	N
   Б	А	1
   В	АБГ	3
   Г	А	1
   Д	БВ	4
   Е	Г	1
   Ж	ВЕ	4
   И	Д
   К	ИДЖЕ