Графы информатика егэ как решать

Содержание:

• Объяснение заданий 13 ЕГЭ по информатике
  • Графы. Поиск количества путей
• Решение заданий 13 ЕГЭ по информатике

13-е задание: «Информационные модели»

Уровень сложности

— повышенный,

Требуется использование специализированного программного обеспечения

— нет,

Максимальный балл

— 1,

Примерное время выполнения

— 3 минуты.

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

13_1:

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

Сколько существует различных путей, ведущих из города А в город М и проходящих через город Г?

• Удалим ребра, которые проходят «мимо» вершины Г или до которых от пункта А можно дойти, минуя вершину Г:



• Вершина В удалена, т.к. возможны только следующие траектории движения через этот пункт (которые НЕ проходят через пункт Г):
• 1. А — Б — В — И — М
• 2. А — Б — В — Е — И — М
• 3. А — Б — В — Е — М
• 4. А — Б — В — Е — К — М
• Теперь посчитаем результаты по оставшимся вершинам:

М = И + Е + К 
-----
 И = Е 
   Е = Г + Ж 
    Г = Б + А + Д = 1 + 1 + 1 = 3 
    Ж = Г = 3
 К = Е + Ж

Теперь возвращаемся, подставляя найденные значения: ↑
   Е = Г + Ж = 3 + 3 = 6 
    Ж = Г = 3
 И = Е = 6 (получили из последующих шагов)
 К = Е + Ж = 6 + 3 = 9       
М = И + Е + К = 6 + 6 + 9 = 21  

Результат: 21

13_2:

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

Сколько существует различных путей, ведущих из города А в город М и не проходящих через город Г?

• Удалим ребра, которые проходят через вершину Г:



• Теперь посчитаем результаты по оставшимся вершинам:

М = И + Е + К
-----
И = В + Е
  В = 1
  Е = В + Ж
     Ж = 1

Теперь возвращаемся, подставляя найденные значения: ↑
  Е = В + Ж = 1 + 1 = 2
И = В + Е = 1 + 2 = 3 
К = Е = 2 
М = И + Е + К = 3 + 2 + 2 = 7  

Результат: 7

13 задание. Демоверсия ЕГЭ 2018 информатика:

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

Сколько существует различных путей из города А в город М, проходящих через город Ж?

13_4:

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

 Многие учащиеся задают этот вопрос приступая к работе с тренировочными вариантами по информатике. В предыдущей статье мы  уже познакомились с двумя способами решения первых заданий. Одним из которых является — способ построения информационного графа. Данный способ позволяет наглядно, в графической форме, увидеть все логические связки. Правильно составленный граф, позволит не потерять основные узлы и покажет всю структуру соединительных связей.

   Итак, перед нами типичное задание из первого блока ЕГЭ по информатике. Решим его с помощью построения графа.

Задание 1:

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

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите номера населенных пунктов A и G в таблице. В ответе запишите числа в порядке возрастания без разделителей.

Работаем по стандартному алгоритму:

• — выделяем горизонтальную линию столбцов;
• — двигаемся по столбцам слева на право;
• -строим графические связи согласно данным в столбцах;
• — выписываем всю информацию по мере построения графа;
• — корректируем готовую графическую структуру;
• -анализируем и выводим ответ.

Решение:

Рассмотрим первый столбик по горизонтали. Напротив цифр 2 и 4 стоят звездочки. Отсюда следует, что от произвольной точки №1,  есть два направления (2 и 4). Схематически это можно представить так:

Переходим в следующий столбик -№2. Он содержит три звездочки напротив цифр-1, 4, 6. Дополняем ранее построенную схему. При этом учитываем, что связь №1-№2, и №1-№4 уже построена. Таким образом наша схема будет (например) выглядеть так:

После третьего столбика построение приобретает вид:

Четвертый столбик содержит 5 звездочек. Значит от четвертой точки должны отходить 5 линий. Как видно из предыдущего рисунка, три линии уже существуют. Нам осталось достроить только 2 логические связи:

В пятом и шестом столбике подтверждаются уже ранее построенные связи. То есть перед нами готовый информационный граф, построенный по данной в задании таблице.

Теперь сравним нашу структуру с оригиналом в задании. Немного скорректируем (перевернем) изображение чтобы оно соответствовало оригиналу. Получим:

В задании нам нужно определить номера населенных пунктов A и G. Не трудно установить, что это цифры  5 и 3 из нашего графа. Ответ требуется записать в порядке возрастания. То есть наш окончательный ответ 35.

 Построение графа облегчает процесс анализа информации и помогает избежать путаницы. Но есть и другие способы решения таких заданий. Каким воспользоваться решаете только ВЫ!