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

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

Что нужно знать:

• если в город R можно приехать только из городов X, Y, и Z, то число различных путей из города A в город R равно сумме числа различных путей проезда из A в X, из A в Y и из A в Z, то есть

,

где обозначает число путей из вершины A в некоторую вершину Q

• число путей конечно, если в графе нет циклов – замкнутых путей

На карту нанесены 4 города (A, B, C и D). Известно, что

между городами A и С – три дороги

между городами C и B – две дороги

между городами A и B – две дороги

между городами C и D – две дороги

между городами B и D – четыре дороги

По каждой из этих дорог можно ехать в обе стороны. Сколькими различными способами можно проехать из города А в город D, посещая каждый город не более одного раза?

Решение:

1. нарисуем граф, в котором множественные дороги из одного города в другой будем обозначать одной дугой и подписывать около неё количество дорог:

1. выпишем все маршруты, по которым можно ехать из A в D так, чтобы дважды не проезжать один и тот же город:

   2 4	3 2	2 2 2	3 2 4
   A  B  D	A  С  D	A  B  С  D	A  C  B  D

2. теперь рассмотрим маршрут A  B  D; сначала можно двумя путями приехать из A в B, а затем – 4-мя путями из B в D; поэтому общее количество различных маршрутов равно произведению этих чисел: 2*4 = 8

3. аналогично находит количество различных путей по другим маршрутам

A  С  D: 3*2 = 6

A  B  С  D: 2*2*2 = 8

A  C  B  D: 3*2*4 = 24

1. всего получается 8 + 6 + 8 + 24 = 46.

2. Ответ: 46.