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

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



НазваниеТема : Графы. Поиск путей
Дата конвертации17.09.2012
Размер110.29 Kb.
ТипРешение

© К. Поляков, 2009-2012

B9 (повышенный уровень, время – 3 мин)


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

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

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

,

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

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

Пример задания:


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



Решение (1 вариант, подстановки):

  1. начнем считать количество путей с конца маршрута – с города К

  2. будем обозначать через NX количество различных путей из города А в город X

  3. общее число путей обозначим через N

  4. по схеме видно, что NБ = NГ = 1

  5. очевидно, что если в город X можно приехать только из Y, Z, то NX = NY + N­Z, то есть нужно сложить число путей, ведущих из A во все города, откуда можно приехать в город X

  6. поскольку в K можно приехать из Е, Д, Ж или И, поэтому

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

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

  2. в город Ж можно приехать только из Е и В, поэтому

Ж = NЕ + NВ

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

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

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

Д = NБ + NВ

так что

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

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

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

  1. по схеме видно, что NБ = NГ = 1, кроме того, NВ = 1 + N­Б + NГ = 3

  2. окончательно N = 2NБ + 3NВ + 2NГ = 2·1 + 3·3 + 2·1 = 13

  3. Ответ: 13.


Решение (2 вариант, удобная форма записи):

  1. начнем считать количество путей с конца маршрута – с города К

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

К  ИДЖЕ

И  Д

Ж  ВЕ

Е  Г

Д  БВ

Г  А

В  АБГ

Б  А

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

Б  А

Г  А

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

В  АБГ

Е  Г

далее добавляем все вершины, куда можно доехать из А, Б, Г, В и Е:

Д  БВ

Ж  ВЕ

на следующем шаге добавляем вершину И

И  Д

и, наконец, конечную. вершину

К  ИДЖЕ

именно в таком порядке мы и будем вычислять количество путей для каждой вершины

  1. теперь идем по полученному списку вершин, полагая, что количество вариантов попасть в вершину равно суммарному количеству вариантов попасть в ее непосредственных предшественников.

NБ = 1, NГ = 1

NВ = 1+1+1 = 3, NЕ = 1

NД = 1+3 = 4, NЖ = 3 + 1 = 4

NИ = 4,

N = NК = 4 + 4 + 4 + 1 = 13

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

  2. Ответ: 13.

^ Возможные ловушки и проблемы:

    • очень важна аккуратность и последовательность; сначала идем от конечной точки к начальной, выписывая все вершины, из которых можно приехать в данную; затем идем обратно, определяя числовые значения

    • построение полного дерева маршрутов – занятие трудоемкое и достаточно бесперспективное, даже грамотные учителя информатики здесь в большинстве случаев что-то забывают и ошибаются

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

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

Б  А

В  АБГ

Г  А

Д  БВ

Е  Г

Ж  ВЕ

И  Д

К  ИДЖЕ

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

    вершина

    откуда?

    N

    Б

    А

    1

    В

    АБГ

    Г

    А

    1

    Д

    БВ

    Е

    Г

    Ж

    ВЕ

    И

    Д

    К

    ИДЖЕ


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

    вершина

    откуда?

    N

    Б

    А

    1

    В

    АБГ

    3

    Г

    А

    1

    Д

    БВ

    Е

    Г

    1

    Ж

    ВЕ

    И

    Д

    К

    ИДЖЕ


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

    вершина

    откуда?

    N

    Б

    А

    1

    В

    АБГ

    3

    Г

    А

    1

    Д

    БВ

    4

    Е

    Г

    1

    Ж

    ВЕ

    4

    И

    Д

    К

    ИДЖЕ


  4. и последние 2 шага

    вершина

    откуда?

    N

    Б

    А

    1

    В

    АБГ

    3

    Г

    А

    1

    Д

    БВ

    4

    Е

    Г

    1

    Ж

    ВЕ

    4

    И

    Д

    4

    К

    ИДЖЕ

    13


  5. Ответ: 13.

Решение (4 вариант, перебор всех путей с начала, А. Яфарова):

  1. запишем все вершины, в которые есть прямой путь из вершины A: Б, В и Г; получается три начальных отрезка:

АБ, АВ, АГ

  1. рассмотрим маршрут АБ: из Б можно ехать в В и Д, поэтому получаем два маршрута:

АБВ, АБД

  1. рассматриваем конечные точки этих маршрутов: из В можно ехать в Д и Ж, а из Д – в И и К:

АБВД, АБВЖ, АБДИ, АБДК

  1. снова смотрим на конечные точки: из Д едем в И и К, из Ж и И – только в К:

АБВДИ, АБВДК, АБВЖК, АБДИК, АБДК

  1. из И едем только в К, таким образом, все возможные маршруты, содержащие участок АБ, доведены до конечной точки К, всего ^ 5 таких маршрутов:

АБВДИК, АБВДК, АБВЖК, АБДИК, АБДК

  1. затем аналогично рассматриваем маршруты, которые начинаются с АВ:

АВД, АВЖ

АВДИ, АВДК, АВЖК

АВДИК, АВДК, АВЖК

всего 3 маршрута

  1. наконец, остается рассмотреть маршруты, которые начинаются с АГ:

АГВ, АГЕ

АГВД, АГВЖ, АГЕЖ, АГЕК

АГВДИ, АГВДК, АГВЖК, АГЕЖК, АГЕК

АГВДИК, АГВДК, АГВЖК, АГЕЖК, АГЕК

всего 5 маршрутов

  1. складываем количество маршрутов для всех начальных участков: 5 + 3 + 5 = 13

  2. Ответ: 13.

Возможные проблемы:

    • при большом количестве маршрутов легко запутаться и что-то пропустить

^ Решение (5 вариант, графический, О.О. Грущак, КузГПА):

  1. Главную идею решения: (число дорог в город N есть сумма дорог, приводящих в города, из которых есть прямой проезд в город N), отразим на самой схеме, показывая на ней ЧИСЛО ДОРОГ, приводящих в каждый город.

  2. Последовательность очевидна: начинаем с Б и Г (городов, куда есть по 1-й дороге из А)

полотно 82

  1. Посчитаем дороги в В: 1 (из A)+ 1(дороги города Б)+ 1(дороги города В)= 3

полотно 109

  1. Аналогично посчитаем дороги в Д, И, Е, Ж:

полотно 136

  1. Определяем число дорог в город К, как сумму дорог в города, с которыми он связан: Д, И, Ж, Е.

полотно 169

  1. Ответ: 13.

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


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



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



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



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




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




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



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



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



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



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




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



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



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



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



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



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



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



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



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



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



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





1 Такая процедура называется топологической сортировкой графа.

2 Источники заданий:

  1. Тренировочные работы МИОО 2011-2012.

  2. Авторские разработки.




Похожие:

Тема : Графы. Поиск путей iconТема : Графы. Поиск путей
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении,...
Тема : Графы. Поиск путей iconПоложение о конкурсе «Ученик года»
...
Тема : Графы. Поиск путей iconУрок по теме: "Поиск информации во Всемирной паутине"
Тема урока – поиск информации во Всемирной паутине (поиск информации в Интернет). Сегодня на уроке вы познакомитесь, как искать информацию...
Тема : Графы. Поиск путей iconПротокол №6 директор моу сош №23 З. В. Хворова
Развитие школы в данный период предлагает поиск путей и создание условий для личностного роста учащегося, его подготовки к полноценному...
Тема : Графы. Поиск путей iconЗадачи на 2011 – 2012 учебный год
Ориентировать весь учебно-воспитательный процесс на развитие зоны ближайшего развития каждого школьника; активизировать поиск новых...
Тема : Графы. Поиск путей iconПоиск путей достижения сбалансированности городского бюджета analysing services to balance the budget
В другом городе выяснилось, что местный госпиталь вот уже много лет платит за водопровод по особому льготному тарифу, поскольку когда-то...
Тема : Графы. Поиск путей iconПлан работы моу соколовская средняя общеобразовательная школа на 2007 2008 учебный год
Ориентировать весь учебно-воспитательный процесс на развитие зоны ближайшего развития каждого школьника; активизировать поиск новых...
Тема : Графы. Поиск путей icon[ вернуться к содержанию сайта
Но есть несколько путей лишения этого доказательства законной силы. Один из наиболее многообещающих путей – использование для света...
Тема : Графы. Поиск путей iconТема урока: «Поиск информации в Интернете»
Каждый компьютер, подключенный к Интернет, имеет Интернет адрес? Доменное имя?
Тема : Графы. Поиск путей iconГнездилова Наталья Юрьевна Цель: Бухгалтер Образование: 2009 г. Московский Государственный Университет Путей Сообщения (миит) Специальность: Национальная экономика Тема диплом
Предоставляла исходные данные для составления проектов хозяйственно-финансовой и коммерческой деятельности
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©podelise.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы

Разработка сайта — Веб студия Адаманов