ЕГЭ по информатике. Теория графов

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

Содержание:

• Что такое граф
• Задание 1
• Экс-Задание 13

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

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

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

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

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

Задание 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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