Привет! Сегодня я хочу рассказать вам как решать задание № 1 из ЕГЭ по информатике.
Вот наш план как научиться решать первое задание:
1. Алгоритм решения
2. Примеры
Алгоритм решения
Подход к решению подобных задач можно разделить на несколько шагов:
1. Анализ графа. Определить степень каждой вершины — количество соединений с другими пунктами. Если указаны длины дорог, записать их отдельно для каждой пары вершин. Найти уникальные вершины или дороги — они помогут быстрее сопоставить схему и таблицу.
2. Сопоставление данных схемы и таблицы. Сравнить связи между вершинами на схеме и данные в таблице смежности. Для вершин, соединённых с известными пунктами, определить недостающие свойства (номера вершин в таблице, протяжённость дорог, количество соединений или маршрутов).
3. Вычисление нужных величин. Если требуется сумма протяжённостей, сложить длины нужных рёбер.
Примеры
Пример задачи:
На рисунке схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).
Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта G в пункт E и из пункта F в пункт H.
В ответе запишите целое число.
Решение:
Определение уникальных вершин по числу рёбер. Например, вершины A, С, Н и G соединены с тремя пунктами, а вершины B, D, F и Е соединены с 2 пунктами.
1. Определение номеров для вершин C и G. После того как определены номера вершин A и D, нужно обратить внимание на вершины C и G, которые соединены с этими двумя пунктами.
2. Определение номера для вершины F. Вершина F имеет два соединения, но не соединена с D. Поскольку вершина D уже сопоставлена с номером 7, нужно найти среди оставшихся номеров тот, который имеет два соединения, но не связан с D. Единственный номер, который подходит под эти условия, — это 5. Таким образом, вершина F соответствует номеру 5.
На этом всё, спасибо за внимание!
