Задание №1 ЕГЭ по информатике
Задание №1 ЕГЭ по информатике
Графы и таблицы расстояний
Тема: анализ графов Что нужно сделать: сопоставить граф с таблицей и найти длину нужной дороги.
📌 Условие задачи
1. Что нужно знать для задания №1
В задании №1 ЕГЭ по информатике обычно даются:
- граф — схема дорог между пунктами;
- таблица — длины дорог между пунктами;
- вопрос, например: "Найдите длину дороги из пункта В в пункт Д".
Главная сложность в том, что буквы на графе и номера в таблице не совпадают напрямую.
2. Что такое граф
Граф — это схема, состоящая из точек и линий.
| Элемент графа | Что означает в задаче |
|---|---|
| Вершина | Населённый пункт |
| Ребро | Дорога между пунктами |
Например, если на графе пункты А и Б соединены линией, значит между ними есть дорога.
А — Б
Если линии между пунктами нет, значит прямой дороги между ними нет.
3. Что такое таблица расстояний
В таблице указаны длины дорог между пунктами.
Например:
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 5 | 7 | ||
| 2 | 5 | 9 | ||
| 3 | 9 | 4 | ||
| 4 | 7 | 4 |
Из таблицы видно:
1 — 2 = 5
1 — 4 = 7
2 — 3 = 9
3 — 4 = 4
Пустая клетка означает, что дороги между пунктами нет.
4. Важная идея
В условии часто написано:
Таблицу и схему рисовали независимо друг от друга.
Это значит:
А — это не обязательно 1
Б — это не обязательно 2
В — это не обязательно 3
Нельзя просто взять букву и заменить её номером.
Нужно понять, какой номер соответствует каждой букве.
5. Главный инструмент — степень вершины
Степень вершины — это количество дорог, которые выходят из пункта.
Проще:
степень вершины = сколько линий выходит из точки
Например:
А соединена только с Б
Значит:
степень А = 1
Если из пункта выходит 4 дороги, значит степень вершины равна 4.
6. Общий алгоритм решения
Используй этот план почти для любого задания №1.
1. Посмотреть на граф.
2. Выписать все дороги между буквами.
3. Посчитать степень каждой буквы.
4. Посмотреть на таблицу.
5. Выписать все дороги между номерами.
6. Посчитать степень каждого номера.
7. Найти очевидные совпадения.
8. Сопоставить буквы и номера.
9. Найти нужную дорогу в таблице.
10. Записать ответ.
7. Разбор примера
Нужно найти длину дороги:
В — Д
Шаг 1. Выписываем связи на графе
По графу видим такие дороги:
А — Б
Б — В
Б — Д
В — Г
В — Е
В — Д
Г — Е
Е — Д
Е — К
Д — К
Шаг 2. Считаем степени букв
Теперь считаем, сколько дорог выходит из каждого пункта.
| Пункт | С кем соединён | Степень |
|---|---|---|
| А | Б | 1 |
| Б | А, В, Д | 3 |
| В | Б, Г, Е, Д | 4 |
| Г | В, Е | 2 |
| Д | Б, В, Е, К | 4 |
| Е | Г, В, Д, К | 4 |
| К | Е, Д | 2 |
Итого:
А: 1
Б: 3
В: 4
Г: 2
Д: 4
Е: 4
К: 2
Шаг 3. Выписываем связи из таблицы
Теперь смотрим на таблицу.
Если в клетке стоит число, значит между этими пунктами есть дорога.
Получаем:
1 — 2 = 4
1 — 7 = 5
2 — 5 = 8
2 — 6 = 9
2 — 7 = 6
3 — 6 = 10
3 — 7 = 7
4 — 5 = 11
5 — 6 = 12
6 — 7 = 13
Шаг 4. Считаем степени номеров
| Номер | С кем соединён | Степень |
|---|---|---|
| 1 | 2, 7 | 2 |
| 2 | 1, 5, 6, 7 | 4 |
| 3 | 6, 7 | 2 |
| 4 | 5 | 1 |
| 5 | 2, 4, 6 | 3 |
| 6 | 2, 3, 5, 7 | 4 |
| 7 | 1, 2, 3, 6 | 4 |
Итого:
1: 2
2: 4
3: 2
4: 1
5: 3
6: 4
7: 4
8. Сопоставляем буквы и номера
Теперь сравниваем степени.
Находим пункт А
На графе:
А имеет степень 1
В таблице:
номер 4 имеет степень 1
Значит:
А = 4
Находим пункт Б
На графе пункт А соединён с пунктом Б.
Мы уже знаем:
А = 4
В таблице номер 4 соединён только с номером 5.
Значит:
Б = 5
Находим пункты В и Д
На графе пункт Б соединён с тремя пунктами:
А, В, Д
Мы уже знаем:
А = 4
Б = 5
В таблице номер 5 соединён с номерами:
2, 4, 6
Номер 4 — это А.
Остаются номера:
2 и 6
Значит:
В и Д — это номера 2 и 6
9. Находим нужную длину дороги
В задаче спрашивают длину дороги:
В — Д
Мы выяснили:
В и Д — это номера 2 и 6
Теперь смотрим в таблицу дорогу между номерами 2 и 6.
2 — 6 = 9
Значит, длина дороги из пункта В в пункт Д равна:
9
10. Ответ
9
Почему не нужно точно знать, где В, а где Д
Мы нашли, что:
В и Д — это номера 2 и 6
Но нам не обязательно определять точно:
В = 2, Д = 6
или:
В = 6, Д = 2
Потому что дорога между ними одна и та же.
2 — 6 = 9
6 — 2 = 9
Ответ всё равно будет:
9
Быстрый способ решения на экзамене
На ЕГЭ можно рассуждать короче:
А имеет степень 1.
В таблице степень 1 имеет номер 4.
Значит, А = 4.
А соединена с Б.
4 соединён только с 5.
Значит, Б = 5.
Б соединён с А, В, Д.
5 соединён с 4, 2, 6.
Значит, В и Д — это 2 и 6.
2 — 6 = 9.
Ответ: 9.
Частые ошибки
Ошибка 1. Считать, что буквы совпадают с номерами
Нельзя думать так:
А = 1
Б = 2
В = 3
В условии сказано, что таблицу и граф рисовали независимо.
Ошибка 2. Сразу смотреть на длины дорог
Длины дорог нужны только в конце.
Сначала нужно понять, какой номер соответствует какой букве.
Ошибка 3. Путать пустую клетку с нулём
Пустая клетка означает:
дороги нет
Это не дорога длиной 0.
Ошибка 4. Не учитывать симметрию таблицы
Если есть дорога:
2 — 6 = 9
то это то же самое, что:
6 — 2 = 9
Мини-шпаргалка
| Что делаем | Как делаем |
|---|---|
| Анализируем граф | Считаем линии от каждой буквы |
| Анализируем таблицу | Считаем числа в каждой строке |
| Сопоставляем | Сравниваем степени |
| Уточняем | Смотрим соседей |
| Отвечаем | Берём нужную длину из таблицы |
Главное правило
Сначала сравниваем структуру графа и таблицы.
Потом определяем соответствия.
И только в конце смотрим длину дороги.
Итог по примеру
Мы получили:
А = 4
Б = 5
В и Д = 2 и 6
Нужная дорога:
В — Д
В таблице это:
2 — 6 = 9
Ответ:
9