Решение задачи 3 ЕГЭ-2019 по информатике

Для решения подобных задач необходимы знания о графах и умение преобразовывать таблицы в графы.

Текст задачи:

На рисунке слева изображена схема дорог Н-ского района, в таблице
звёздочкой обозначено наличие дороги из одного населённого пункта
в другой. Отсутствие звёздочки означает, что такой дороги нет.

Решение задачи 3 ЕГЭ-2019 по информатике

Решение задачи 3 ЕГЭ-2019 по информатике

Каждому населённому пункту на схеме соответствует его номер в таблице,
но неизвестно, какой именно номер. Определите, какие номера населённых
пунктов в таблице могут соответствовать населённым пунктам B и C на
схеме. В ответе запишите эти два номера в возрастающем порядке без
пробелов и знаков препинания.

Решение:

При решении кроме знаний очень важно сконцентрироваться и проявить максимальную внимательность.

Конечно можно перебрать все варианты из таблицы, проверяя их по графу. Но этот метод трудоемкий и занимает много времени. Можно обратить внимание, что из вершины D на графе выходят 2 ребра (также, как и из вершин A и E). Но при этом, вершины A, B, F, A образуют цикл так же как и вершины E, C, G, E. Вершина же D входит в состав цикла D, C, G, F, B, D. Рассмотрим на примере. Мы видим, что в таблице точка 1 связана напрямую с двумя точками 5 и 6. Предположим, что точка 1 в таблице — это вершина D у графа. Тогда, если посмотреть на граф, вершина D связана с вершинами B и C. В таблице это точки 5 и 6. В графе вершины B и C напрямую не связаны, а в таблице между точками 5 и 6 есть прямой маршрут. Значит, что точка 1 — не вершина D.

Кроме точки 1 в таблице есть еще точка 4, которая связана только с двумя точками — 2 и 6. Проверим, не является ли она вершиной D нашего графа. Как видим в таблице из точки 4 можно напрямую попасть в точки 2 и 6. И при этом точки 2 и 6 напрямую не связаны! Получается, что точка 4 — это и есть вершина D нашего графа. Но есть еще одна точка, связанная только с двумя другими — точка 7. Из нее мы можем напрямую попасть только в точки 2 или 3. Но точки 2 и 3 напрямую связаны между собой (см. таблицу). И получается, что точка 7 не может быть вершиной графа, так как вершина D графа связана с вершинами B и C, которые между собой прямой связи не имеют (см. граф).

Получаем, что точка 4 — вершина D графа. А точки 2 и 6 — это вершины B и C. Так как по условию номера нужно записать в порядке возрастания, ответ будет 26.

Второй вариант решения

Давайте построим граф по таблице. Для этого просто расставим числа от 1 до 7 по кругу и соединим их линиями, согласно таблице. Например, цифру 1 мы соединим с цифрами 5 и 6, цифру 2 с цифрами 3, 4 и 7 и так далее. В итоге получим следующий граф:

 

Задачи 3 ЕГЭ 2019 по информатике

Решение задачи 3 ЕГЭ 2019 по информатике с помощью графа

Конечно, полученный граф на первый взгляд не похож на тот, что в условии. Но давайте посмотрим внимательнее. Мы также видим три точки 1, 7 и 4 которые напрямую связаны только с двумя другими. И также видим, что точки 1, 5, 6, 1 образуют цикл (как и вершины графа A, B, F, A), а точки 7, 2, 3, 7 цикл (как и вершины C, E, G, C). А вот точка 4 цикла из 3-х вершин не образует — все также как и вершина D графа. Получаем, что точка 4 — это вершина D графа. А вершины B и C — это точки 6 и 2. Запишем их в порядке возрастания (по условию задачи) и получим ответ — 26.

Автор:

Оцените статью, это очень поможет развитию сайта.

Решение задачи 3 ЕГЭ по информатике (ФИПИ 2019)
Пока никто не оценил