Данное задание ЕГЭ по информатике основано на теме “Графы”. Похожее задание есть и в экзамене для девятого класса (четвёртое задание в ОГЭ). Как и в экзамене девятого класса здесь присутствуют неориентированные графы.
По неориентированному графу можно передвигаться в двух направлениях. У ориентированного графа ситуация же иная, есть одно заданное направление и передвигаться можно только по нему.
На рисунке выше представлены два вида графов (если быть точнее, то отдельные их части). Первым идёт неориентированный граф, на котором мы можем перемещаться из точки A в точку B и наоборот, из точки B в точку A. Второй же, ориентированный, на нём строго из точки A в точку B и никак иначе.
Между пунктами также есть некоторый параметр — вес. Проще всего этот параметр легче понять на примере. У нас есть маршрутная карта из разных городов в других города. Вес в данном случае будет обозначать стоимость путешествия из города A в город B. Когда у нас будет такой граф, то мы легко построим более экономный маршрут.
Из теории больше ничего особо знать для этого задания не потребуется, дальше уже важным умением будет — анализ. Суть будет заключаться в умении анализировать граф и приложенную к нему таблицу со значениями.
Всего на экзамене пока что существуют лишь две разновидности данного задания. В одном известен вес между пунктами, а во втором — нет. Но метод решения в любом случае одинаков.
Задание №1
Задание:
Необходимо определить длину дороги между пунктами. Б и Д. В ответ запишите целое число.
Решение:
Как видим из задания, то ничего особо решать нам не потребуется. Здесь лишь нужно проанализировать граф и сверяться с таблицей. Для удобства запишем в виде таблицы сколько путей имеет каждый пункт на графе.
В таблице же каждое числовое значение говорит о количестве путей (число под каждым пунктом).
После этого уже начинаем методом исключения и логического мышления находить соответствия между пунктами на графе и пунктами в представленной таблице. Исходя из наблюдений с данными в таблице, можно попробовать составить новую таблицу соответствий.
Здесь видно, что однозначно определить получилось лишь пункт В и пункт Е. Как же быть с остальными, ведь нам надо определить расстояние между пунктами Б и Д? Далее уже включаем мышление и смотрим на таблицу.
Поскольку точно знаем о пунктах В и Е, а они, в свою очередь, связаны с пунктами Б и Д, то сможем отбросить один из трёх вариантов (для обоих пунктов). От сюда находим, что пункт Б — П3.
Дальше понимаем, что пунктом Д, может быть как П2, так и П7. Смотрим по таблице, можем ли попасть из П3 (Б) в П2 или нет? — не можем. А посмотрим на пункт П7. Да, здесь получается попасть из П3 в П7.
Следовательно, нашли необходимые соответствия между пунктами, теперь осталось посмотреть (в таблице) на протяжённость дороги — 11.
Задание №2
Задание:
Необходимо определить номера населённых пунктов A и G. Ответ запишите в порядке возрастания номеров.
Решение:
Хоть тут и нет чисел в таблице, но решение от этого никак не поменяется. Составим также таблицу с количеством дорог.
Теперь можно и составить таблице соответствия, с использованием данных из двух таблиц (нашей и из задания).
Здесь ситуация чуть сложнее, однозначно определился только один пункт — F. Искомые же пункты (A и G) имеют по четыре варианта. Необходимо отбросить лишние. Если внимательно посмотреть на граф, то можно заметить, что пункты C и E связаны с B и D. Следовательно, можно отбросить сразу два пункта и тем самым найти решение.
Населённые города П1 и П2 оказались связаны с П4 и П5. Получается, что они нам не подходят (их занимают B и D). И для наших городов (A и G) подходят П6 и П7. Определять, кто есть кто нам не требуется. Даже протяжённость дорог определять, нет необходимости. Ответ запишем в порядке возрастания (как просили в задании) номеров — 67.
Если есть интерес и желание, то можно определить и остальные пункты в этих двух заданиях. Можете попробовать решить, а ответ отправить в комментарии.
Понравилась статья? Хочешь разбираться в информатике, программировании и уметь работать в разных программах? Тогда ставь лайк, подпишись на канал и поделись статьей с друзьями! Остались или появились вопросы — спроси в комментариях!
