Привет! 👋 Первая задача в ЕГЭ по информатике проверяет умение работать с графами - одной из важнейших тем дискретной математики. Давайте разберемся, что это такое и где с этим сталкиваемся в жизни.
📌 Что такое граф?
Граф – это набор объектов (вершин) и связей между ними (рёбер). 🕸️
- Вершины (узлы): могут обозначаться буквами (A, B, C…) или цифрами (1, 2, 3…). Например, города или пользователи соцсетей.
- Рёбра (связи): линии, соединяющие вершины. Например, дороги или дружба.
- Вес рёбер: число, которое показывает длину дороги, стоимость, время и т.д. 🏷️
🌍 Примеры из жизни, где используются графы
1. Социальные сети
Что является графом? Вся структура социальной сети.
- Вершины: Пользователи (вы, ваши друзья, блогеры).
- Рёбра: Дружба, подписки, лайки.
Как используется?
- «Возможные друзья»: Алгоритм анализирует граф ваших связей и предлагает вам в друзья людей, с которыми у вас много общих друзей (то есть которые находятся на расстоянии 2 шага в графе от вас).
- Распространение информации: Как мем или новость становится вирусной? Она распространяется по рёбрам этого графа от одного пользователя к другому.
2. Транспорт и навигация
Что является графом? Дорожная сеть.
- Вершины: Перекрестки, населённые пункты.
- Рёбра: Дороги, магистрали.
- Вес рёбер: Протяжённость, время в пути с учетом пробок.
Как используется?
Приложения-навигаторы вроде Яндекс.Карт или Google Maps - это одна большая программа для работы с графами. Когда вы строите маршрут из точки А в точку Б, приложение ищет кратчайший путь в графе, используя алгоритмы (например, алгоритм Дейкстры).
Схематичное изображение
Связь между вершинами схематично удобно изображать графически (в виде графа), а вес ребер - в виде таблицы:
🔍 Разберем ДЕМО-задание №1 ЕГЭ 2026
На рисунке схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).
Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта G в пункт E и из пункта F в пункт H. В ответе запишите целое число.
Алгоритм решения задачи
ШАГ 1: Анализируем граф
ШАГ 2: Анализируем таблицу
ШАГ 3: Устанавливаем соответствие
Шаг 4: Отвечаем на вопрос задачи
ШАГ 1: Анализируем граф
На первом шаге посчитаем и выпишем количество дорог (степень вершин) для каждой буквы.
- A: 3 дороги (к D, G, C)
- B: 2 дороги (к C, H)
- C: 3 дороги (к G, A, B)
- D: 2 дороги (к H, A)
- E: 2 дороги (к F, G)
- F: 2 дороги (к H, E)
- G: 3 дороги (к E, C, A)
- H: 3 дороги (к D, F, B)
Итог по графу:
У нас есть вершины со степенями 2 и 3. Вершин со степенями 1 или 4 нет. ✅
ШАГ 2: Анализируем таблицу
Проделаем то же самое для таблицы. Посчитаем, сколько дорог ведёт к каждому пронумерованному пункту. Для этого просто посчитаем, сколько раз встречается каждая цифра в строках таблицы.
- Пункт 1: есть дороги 1-2, 1-5, 1-8 → 3 дороги
- Пункт 2: есть дороги 1-2, 2-7 → 2 дороги
- Пункт 3: есть дороги 3-5, 3-6 → 2 дороги
- Пункт 4: есть дороги 4-6, 4-8 → 2 дороги
- Пункт 5: есть дороги 1-5, 3-5, 5-8 → 3 дороги
- Пункт 6: есть дороги 3-6, 4-6, 6-7 → 3 дороги
- Пункт 7: есть дороги 2-7, 6-7 → 2 дороги
- Пункт 8: есть дороги 1-8, 4-8, 5-8 → 3 дороги
То же самое можно сделать прямо на полях таблицы:
Итог по таблице:
- Пункты с 3 дорогами: 1, 5, 6, 8 ✅
- Пункты с 2 дорогами: 2, 3, 4, 7 ✅
Сравниваем с графом:
- На графе 4 вершины с 3 дорогами: A, C, G, H. ✅
- Значит, числа {1, 5, 6, 8} в таблице это и есть буквы {A, C, G, H} на графе, но в каком порядке?
ШАГ 3: Устанавливаем соответствие (самая интересная часть) 🔎
Давайте найдём "якорь" - точку, с которой начнём расшифровку. Посмотрим на вершину A.
На графе A соединена с D, G, C. Мы уже знаем, что D - это НЕ число из {1,5,6,8} (потому что у D только 2 дороги). Значит, D - это одно из чисел {2,3,4,7}. А вот G и C - это числа из нашего набора {1,5,6,8}.
Теперь смотрим в таблицу. Мы ищем пункт из {1,5,6,8}, у которого два соединения ведут на другие пункты из {1,5,6,8}, а одно - на пункт из {2,3,4,7}.
- Пункт 1: соединения 1-2, 1-5, 1-8. 2 - это "малый" пункт, 5 и 8 - "большие". Подходит под схему A (D - малый, G, C - большие).
- Пункт 5: соединения 1-5, 3-5, 5-8. 3 - малый, 1 и 8 - большие. Тоже подходит.
- Пункт 6: соединения 3-6, 4-6, 6-7. Все три соединения (3,4,7) - малые пункты! Это не может быть A, так как у A два соседа - большие.
- Пункт 8: соединения 1-8, 4-8, 5-8. 4 - малый, 1 и 5 - большие. Тоже подходит.
Итак, пункт 6 - уникален! У него все три соседа - "малые". Смотрим на граф: есть ли такая вершина среди {A, C, G}? Нет! У всех у них есть хотя бы один сосед из "больших" вершин.
- A: соседи G, C (большие) и D (малый).
- C: соседи A, G (большие) и B (малый).
- G: соседи A, C (большие) и E (малый).
Посмотрим на вершину H:
- H: с оседи B, D (малые) и F (малый).
Вот оно! У вершины H все три соседа (D, F, B) имеют по 2 дороги, то есть являются "малыми" пунктами. Это идеально совпадает с описанием пункта 6 в таблице!
Делаем первый вывод: H = 6. 🎯
Теперь легко пойдём дальше. Смотрим на соседей H (то есть пункта 6) по таблице: это 3, 4 и 7 (длины 43, 9, 37). Эти числа - наши "малые" пункты {D, F, B}.
Найдём среди них F. На графе F соединён с H и E. В таблице пункт 6 (H) соединён с 3, 4, 7. Какой из этих пунктов имеет только одно другое соединение? Смотрим:
- Пункт 3: соединён с 5 и 6.
- Пункт 4: соединён с 6 и 8.
- Пункт 7: соединён с 2 и 6.
Пока неочевидно. Давайте найдём E. E на графе соединён только с F и G. G - "большой" пункт. Значит, в таблице E - это "малый" пункт, который соединён с другим "малым" (это будет F) и с "большим" (G). Ищем в "малых" {2,3,4,7} такой, у которого есть связь с "большим" {1,5,8}.
- Пункт 3: соединён с 5 (большой). Подходит! Возможно, E = 3. Тогда его второй сосед - 5 (это G?).
- Проверим: Если E=3, а его сосед 5=G, то по графу второй сосед E - это F. Значит, F - это оставшийся сосед пункта 3, то есть пункт 6. Но 6 - это H! Противоречие.
Не то. Проверим другие "малые":
- Пункт 4: соединён с 6 (H) и 8 (большой). Если E=4, то его соседи: H и G=8. Тогда второй сосед E по графу - F. Но F нет среди соседей 4. Не подходит.
- Пункт 7: соединён с 2 и 6 (H). Нет связи с "большим". Не подходит.
- Пункт 2: соединён с 1 (большой) и 7. Если E=2, то его соседи: G=1 и F=7.
Отлично! Это похоже на правду. Пробуем: E = 2. ✅
Если E=2, то по графу его соседи: F и G. В таблице у пункта 2 соседи: 1 и 7. Значит, G = 1, а F = 7.
Давайте проверим нашу растущую схему: H = 6; E = 2; F = 7; G = 1
Проверим связь F-H: на графе она есть. В таблице связь 7-6 есть (длина 37). Всё сходится.
Теперь у нас остались "большие" пункты {5, 8} и буквы {A, C}. И "малые" пункты {3, 4} и буквы {B, D}.
Смотрим на граф. G (который у нас 1) соединён с E, C, A. E мы уже знаем (2), значит, C и A - это соседи 1 в таблице. Соседи 1 в таблице: 2 (это E), 5 и 8. Отлично! Значит, {A, C} = {5, 8}.
Теперь смотрим на C. На графе C соединён с G, A, B. G=1, A - это 5 или 8. Значит, B - это сосед C из "малых" пунктов. Посмотрим в таблице на пункты 5 и 8:
- Пункт 5: соединён с 1 (G), 3, 8 (A). Значит, его "малый" сосед - 3. Тогда если C=5, то B=3.
- Пункт 8: соединён с 1 (G), 4, 5 (A). Его "малый" сосед - 4. Тогда если C=8, то B=4.
Как выбрать? Смотрим на оставшуюся букву D. На графе D соединён с H и A. H=6. Значит, в таблице D - это "малый" пункт, соединённый с 6 и с A (который 5 или 8).
Смотрим на "малые" пункты 3 и 4:
- Пункт 3: соединён с 5 и 6. Если D=3, то A должно быть 5.
- Пункт 4: соединён с 6 и 8. Если D=4, то A должно быть 8.
Вспомним про C. Если мы предположим, что C=5, то B=3, а A=8. Но тогда для D=3, A должно быть 5 - противоречие, так как A у нас уже 8.
Значит, верен второй вариант: C = 8; B = 4; A = 5; D = 3 ✅
Финальная расшифровка: A = 5; B = 4; C = 8; D = 3; E = 2; F = 7; G = 1; H = 6 ✅
Шаг 4: Отвечаем на вопрос задачи
Нам нужна сумма протяжённостей дорог:
- G-E = 1-2 = 15
- F-H = 7-6 = 37
15 + 37 = 52
Ответ: 52 ✅
💎 Итог: Несмотря на кажущуюся сложность, задача решается чисто логически. Главное - действовать системно: анализ степеней вершин -> поиск уникальных совпадений -> проверка гипотез через длины рёбер.