kopilkaurokov.ru - сайт для учителей

Создайте Ваш сайт учителя Курсы ПК и ППК Видеоуроки Олимпиады Вебинары для учителей

Разработка задание ЕГЭ по теме: "Поиск путей в графе".

Нажмите, чтобы узнать подробности

Данную разработку можно использовать на уроках информатики при подготовке к ЕГЭ.

Вы уже знаете о суперспособностях современного учителя?
Тратить минимум сил на подготовку и проведение уроков.
Быстро и объективно проверять знания учащихся.
Сделать изучение нового материала максимально понятным.
Избавить себя от подбора заданий и их проверки после уроков.
Наладить дисциплину на своих уроках.
Получить возможность работать творчески.

Просмотр содержимого документа
«Разработка задание ЕГЭ по теме: "Поиск путей в графе".»


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


В этой задаче мы имеем дело с ориентированным графом (графом, у которого ребра имеют направление). То есть ребра имеют вид стрелок. Две вершины, соединенные напрямую стрелкой, называются смежными. Вершина, из которой выходит стрелка, называется предком, а вершина, в которую входит стрелка, - потомком.

Несложно понять, что количество путей, которыми можно попасть в некоторую вершину, равно сумме количеств путей предков этой вершины.


Подсчет путей в ориентированном графе



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















Решение


Каждой вершине, начиная с начальной (А), поставим в соответствие индекс, равный количеству путей, которыми можно попасть в эту вершину. Для вершины А (начало пути) индекс всегда равен 1 (в начало пути можно попасть единственным образом — никуда не двигаясь). Теперь сформулируем правило: индекс вершины равен сумме индексов его предков. Исходя из этого индекс Б равен 1 (предок у Б один — вершина А).

У вершины Д предками являются А и Б, значит, индекс вершины Д равен 1+1 = 2.













Очевидно, что мы можем посчитать индекс только тех вершин, индексы предков которых уже посчитаны. Например, мы не можем посчитать индекс Г, пока не посчитан индекс В. Двигаясь последовательно, мы рассчитаем индексы всех вершин. Индекс вершины Ж и будет ответом задачи.














Ответ: 11.




На рисунке — схема дорог, связывающих города A, B, C, D, E, F, G, H, G, K, L, M, N, Z. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Z?














Решение


Задача решается абсолютно так же, как предыдущая. Присваиваем начальной вершине

А индекс 1 и последовательно считаем индексы всех вершин до Z:


Ответ: 34.


Получите в подарок сайт учителя

Предмет: Информатика

Категория: Прочее

Целевая аудитория: 9 класс

Скачать
Разработка задание ЕГЭ по теме: "Поиск путей в графе".

Автор: Могилевская Юлия Гильфановна

Дата: 30.11.2020

Номер свидетельства: 564935

Похожие файлы

object(ArrayObject)#851 (1) {
  ["storage":"ArrayObject":private] => array(6) {
    ["title"] => string(97) "Методическая разработка "Графы. Поиск путей в графе". "
    ["seo_title"] => string(56) "mietodichieskaia-razrabotka-grafy-poisk-putiei-v-ghrafie"
    ["file_id"] => string(6) "132517"
    ["category_seo"] => string(11) "informatika"
    ["subcategory_seo"] => string(11) "presentacii"
    ["date"] => string(10) "1416341122"
  }
}

Получите в подарок сайт учителя

Видеоуроки для учителей

Курсы для учителей

ПОЛУЧИТЕ СВИДЕТЕЛЬСТВО МГНОВЕННО

Добавить свою работу

* Свидетельство о публикации выдается БЕСПЛАТНО, СРАЗУ же после добавления Вами Вашей работы на сайт

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

Ваш личный кабинет
Проверка свидетельства