Здравствуйте, меня зовут Илья Сагалов! Если вы открыли эту статью — то точно готовите к ЕГЭ по информатике. Я с радостью помогу вам в этом. Перед вами подробная инструкция о том, как объяснить даже самым сложным ученикам всю теорию графов.

Содержание:

Ищем тех, кто влюблен в IT!

Открыт набор преподавателей компьютерных курсов для детей и репетиторов для подготовки
к ОГЭ/ЕГЭ по информатике

Начать преподавать
banner article 8 Skyteach

Что такое граф

Первое, что нужно объяснить выпускнику, — что же такое граф? Если бы мы готовились к русскому языку, то, скорее всего, ответ был бы «дворянский титул». Но для нас графом будет являться обыкновенная стрелочка или линия между двумя точками, которая чаще всего показывает нам:

ege po informatike teoriya grafov 1 Skyteach

Есть всего 3 термина, которые пригодятся школьнику при работе с графами:

  1. Ориентированный граф — просто граф со стрелочкой. Он покажет ученику, куда именно идти, прямо как указатель.
  2. Неориентированный граф — дорога есть, но в какую сторону идти — без разницы.
  3. Взвешенный граф — значит, что школьнику неважно знать, куда идти, а необходимо знать лишь, сколько по времени займет маршрут или какая у него длина.
Ученик может спросить о том, как же вообще какое-то расстояние может быть связано с экзаменом? На самом деле, это поможет ему решить задание 1 ЕГЭ по информатике.

Еще полезные статьи по информатике и компьютерным курсам:

Задание 1

Если ученик хоть раз решал пробник, то уже знаком с тем самым случаем, когда кто-то в первом задании рисует таблицу, другой рисует схему из графов, а выпускнику приходится мучаться и пытаться понять: какие цифры каким буквам соответствуют? Чтобы стало понятнее, давайте объясним школьнику на примере:

Есть два человека, которых попросили исследовать местность.

Первого человека попросили узнать,
из какого города в какой есть
дороги. Он называл каждый город
его первой буквой и зарисовывал
все схематически на бумаге.

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

И вот что из этого вышло:

ege po informatike teoriya grafov 2 Skyteach
Все полученные задачи выполнены, и ученику в руки несут два совершенно разных проекта — картинку и таблицу. Теперь выпускнику нужно разгадать, какой букве будут соответствовать какие цифры, ведь те, кто это рисовал, куда-то испарились и спросить у них уже ничего нельзя.

Представим, что ученику звонит знакомый и спрашивает: «Подскажи, пожалуйста, какое расстояние из города Д в город Е?»

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

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

ege po informatike teoriya grafov 7 Skyteach

После этого стоит то же самое проделать в таблице. Выпускнику нужно найти уникальную строку с самым большим или маленьким количеством записей.

ege po informatike teoriya grafov 8 Skyteach
Ученик только что узнал, что буква Г — это номер 5 в таблице.

Продолжаем искать что-то уникальное, может, есть еще какой-то город, который выделяется среди остальных?

ege po informatike teoriya grafov 9 Skyteach

Город А — единственный, в который попадают три графа, а значит, нужно искать
такой же в таблице.

ege po informatike teoriya grafov 10 Skyteach
Выходит, что мы раскрыли еще один город:
Буква А — это номер 2 в таблице.

Если попробовать сделать так еще раз, то больше ничего уникального мы не найдем, а значит — пора начать анализировать.

Обратим внимание, что город А на рисунке соединен с тремя городами: Б, В и Г.

ege po informatike teoriya grafov 11 Skyteach

Про то, что Г — это 5, мы уже знаем, а значит, самое время обратиться к таблице для того, чтобы узнать, какие есть варианты для городов Б и В. Ученику нужно смотреть на вторую строчку, ведь она отвечает за город А.

ege po informatike teoriya grafov 12 Skyteach

Как можно заметить, у нас три кандидата на буквы Б и В: 3, 4 и 5.

Но ведь 5 уже занята буквой Г, а значит — под 3 и 4 скрываются буквы Б и В.
Самое крутое — нам абсолютно все равно, кому какую цифру отдать, ведь нас не интересуют буквы Б и В, а вот оставшиеся две буквы очень даже.

Давайте выпишем все, что мы уже имеем:

2 — А
3 и 4 — Б и В
5 — А

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

1 и 6 — это те самые искомые города Д и Е.

Осталось дать ответ на вопрос, какое расстояние между ними. Смотрим
по таблице — получается 34, ученик может звонить другу и говорить точную информацию.

Чтобы стающему ЕГЭ по информатике было легче запомнить — я составил небольшую схему, которая поможет не забыть, что делать. Если следовать ей при решении таких задач, то у школьника все получится.

ege po informatike teoriya grafov 14 Skyteach

Поздравляю, один балл на ЕГЭ уже в кармане вашего ученика.

Что такое компьютерные курсы Skyeng?

Рассказываем, о направлениях преподавания в нашей онлайн-школе

Узнать подробно
banner article new 10 Skyteach
Другие статьи о преподавании в Skyeng для учителей информатики:

Экс-Задание 13

Чтобы ученик отработал графы, можно дать ему прошлогоднее Задание 13 из ЕГЭ. Давайте изменим задачу, оставим только картинку с графами, а также добавим щепотку ориентированности при помощи стрелочек.

ege po informatike teoriya grafov 3 1 Skyteach

Предложим ученику представить, что ему звонит друг, чтобы узнать ответ на еще один вопрос: «А сколько вообще путей из города А в город Е?» Несмотря на то что вопрос странный, попробуем на него ответить.

Научим самому простому способу.

Начальный путь возьмем за единицу, ведь нужно именно из города А начать, а это возможно сделать единственным способом.

ege po informatike teoriya grafov 4 Skyteach

Дальше задаем вопрос, сколько у нас вариантов попасть из А в Б, к примеру? Разумеется, у нас он всего один, значит, над буквой Б тоже пишем 1, как и над буквой В.

ege po informatike teoriya grafov 5 Skyteach

Теперь мы добрались до города Г. Этот город мы будем называть узлом, потому что в него входит и выходит из него больше одного графа.

Попасть в город Г мы могли из А, Б или В. Нам нужно сложить то, что мы писали над предыдущими буквами, и мы получим 3, а значит, уже есть три варианта попасть в город Г, что и так видно.

ege po informatike teoriya grafov 6 Skyteach

Теперь мы придерживаемся тех же правил: смотрим какие стрелки входят в город, и пишем их сумму. Таким образом, в Д ведет стрелка только из Г, а значит, складывать нечего и Д тоже будет равен 3. А вот в город Е ведут уже две стрелки — из Г и Е, но мы то уже знаем, что они равны 3 каждый, а значит, Е будет равен их сумме, то есть 6.

ege po informatike teoriya grafov 15 Skyteach
Вот и ответ на второй вопрос, всего из A в E 6 дорог.

Теперь ваш ученик знает, как разобраться с графами на ЕГЭ по информатике. А чтобы узнать, как получить максимум баллов, выпускник может присоединиться к моей группе: ВКонтакте или Телеграм.

Добавить комментарий

Ваш адрес email не будет опубликован.

×