Погода
Календарь
Май 2019
Пн Вт Ср Чт Пт Сб Вс
« Сен    
 12345
6789101112
13141516171819
20212223242526
2728293031  
Страницы сайта

Поиск путей в графе.

  • Если в город R из города A можно добраться только из городов XY и Z, то количество различных путей из города A в город R равно сумме числа различных путей проезда из A в X, из A в Y и из A в Z, то есть:
    NR = NX + NY + NZ
    где NR — это количество путей из вершины A в вершину R
    Число путей не бесконечно, исключением является только граф, в котором есть циклы – замкнутые пути.
    Часто задачи с графами целесообразней решать с конца.

Решение заданий

Задание 1:  На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей, ведущих из города А в город М и проходящих через город В?

Решение:

  • для того, чтобы оставить только маршруты, проходящие через вершину В, нужно представить граф в таком виде, «собрав его в пучок» около вершины В:
  • проведём сечение графа через вершину В:
  • обратим внимание на такой факт: если мы перешли через линию сечения из левой части в правую по ребру ГЕ или через вершину Ж, мы уже никак не попадём в вершину В (нет рёбер с «обратным направлением», поэтому эти маршруты запрещены; для более сложных случаев, когда такие рёбра с «обратным направлением» есть, нужно перерисовать граф (или провести сечение иначе) так, чтобы все вершины, ИЗ которых можно попасть в В, оказались слева от линии сечения
  • в данном случае выбрасывается вершина Ж, все связанные с ней рёбра, и ребро ГЕ:
  • дальше используем стандартный метод (см. разбор следующей задачи)
  • покажем только окончательный результат:

Ответ: 16.

Задание 2:   На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л?

Решение:

  • будем обозначать через NX количество различных путей из города А в город X
  • для города А есть только один маршрут – никуда не двигаться, поэтому NA = 1
  • для любого города X количество маршрутов NX можно вычислить как

Nx = Ny + … + Nz

где сумма взята по всем вершинам, из которых есть прямой путь в вершину X; например,

     NЛ = NИ + NЖ + NК

  • около каждого города будем записывать количество маршрутов из А в этот город
  • начнем считать количество путей с начала маршрута – с города А:
  • теперь находим те вершины, в которые можно попасть напрямую из уже рассмотренных вершин (пока – только из А), это Б и Г, для них тоже количество путей равно 1:
  • теперь можно определить количество путей для В и Е; в В можно приехать только из А, Б и Г, а в Е – только из Г:

     NВ = NА + NБ + NГ = 1 + 1 + 1 = 3

     NЕ = NГ = 1

  • теперь можно определить количество путей для Д, Ж и К; в Д можно приехать только из Б и В, в Ж – из В и Е, а в Е – только из Г:

     NД = NБ + NВ = 1 + 3 = 4

     NЖ = NВ + NЕ = 3 + 1 = 4

     NК = NЕ­ = 1

  • теперь можно определить количество путей для И, куда можно приехать только из Д (NИ = NД) и, наконец, для Л:

     NЛ = NД + NИ + NЖ + NК = 13

Ответ: 13.

Задание 3:  Города A, B, C и D связаны дорогами. Известно, что существуют дороги между городами  A и С, C и B (две дороги), A и B, C и D (две  дороги), B и D. Сколькими различными способами можно проехать из города А в город D, не заезжая дважды в один город?

Решение:

  • нарисуем граф, в котором множественные дороги из одного города в другой будем обозначать одной дугой и подписывать около неё количество дорог:
  • выпишем все маршруты, по которым можно ехать из A в D так, чтобы дважды не проезжать один и тот же город:
  • теперь рассмотрим маршрут  A => B => D; на всех участках только одна дорога, поэтому есть только один такой маршрут
  • для маршрута A => С => D: на первом участке только одна дорога, на втором – две, общее число маршрутов равно произведению этих чисел: 1*2 = 2
  • аналогично находит количество различных путей по другим маршрутам

A => B => C => D         1*2*2 = 4

A => C => B => D:        1*2*1 = 2  

  • всего получается 1 + 2 + 4 + 2 = 9.

Ответ: 9.

Задание 4:   На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

Решение:

  • начнем считать количество путей с конца маршрута – с города К
  • будем обозначать через NX количество различных путей из города А в город X
  • общее число путей обозначим через N
  • по схеме видно, что NБ = NГ = 1
  • очевидно, что если в город X можно приехать только из Y, Z, то NX = NY + N­Z, то есть нужно сложить число путей, ведущих из A во все города, откуда можно приехать в город X
  • поскольку в K можно приехать из Е, Д, Ж или И, поэтому

N = N­К = NД + NЕ + NЖ + NИ

  • в город И можно приехать только из Д, поэтому NИ = NД
  • в город Ж можно приехать только из Е и В, поэтому

Ж = NЕ + NВ

  • подставляем результаты пп. 6 и 7 в формулу п. 5:

N = NВ + 2NЕ + 2NД

  • в город Д можно приехать только из Б и В, поэтому

Д = NБ + NВ

так что

N = 2NБ + 3NВ + 2NЕ

  • в город Е можно приехать только из Г, поэтому N­Е = NГ так что

N = 2NБ + 3NВ + 2NГ

  • по схеме видно, что NБ = NГ = 1, кроме того, NВ = 1 + N­Б + NГ = 3
  • окончательно N = 2NБ + 3NВ + 2NГ  = 2·1 + 3·3 + 2·1 = 13

Ответ: 13

Задание 5. Демоверсия ЕГЭ 2018 информатика (ФИПИ).
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город М, проходящих через город Ж?

Ответ: 20

Top