Допустим, степени вершин следующие:

Теперь посмотрим на таблицу дорог.

Количество ненулевых значений:

Сразу получаем:

А = P4
Е = P3
В = P6

Почему?

Потому что степени 4, 1 и 2 встречаются только по одному разу.

Остаются:

Б
Г
Д

и:

P1
P2
P5

У всех степень 3.

Теперь смотрим связи.

Вершина Д соединена с Е. Мы уже определили, что Е = P3. Поэтому ищем среди P1, P2 и P5 вершину, которая соединена с P3.
В таблице с P3 соединена P5. Значит, Д = P5.

После этого остаются только:

Б и Г
P1 и P2

Их можно различить по связям с уже найденными вершинами.

В итоге получаем полное соответствие.

Только после этого смотрим длины дорог.

Почему не нужно начинать с длин дорог

Одна из типичных ошибок — сразу смотреть на числа:

«Здесь 5, здесь 7, наверное, это нужная дорога».

Но длины дорог обычно никак не помогают определить соответствие вершин.

Сначала нужно восстановить:

А = P?
Б = P?
В = P?
...

И только затем использовать числа.

Правильная последовательность:

структура → соответствие → длина.

А не наоборот.

Как понять количество дорог по таблице

Допустим, строка выглядит так:

P2 | 7 | — | 9 | 4 | — | 6

В ней четыре числа:

7
9
4
6

Следовательно:

степень P2 равна 4.

Само значение чисел пока не важно.

Нам интересно только:

сколько ячеек заполнено.

Что делать, если уникальных степеней нет

Иногда граф составлен так, что несколько вершин имеют одинаковое число дорог.

Это не означает, что задача не решается.

Например:

А — 2
Б — 2
В — 3
Г — 3
Д — 2

Здесь одного подсчёта степеней недостаточно.

Тогда используйте комбинацию признаков.

Для каждой вершины спросите:

1. Сколько у неё дорог?
2. С какими вершинами она соединена?
3. Каковы степени её соседей?
4. Соединена ли она с уже найденной вершиной?

Чем больше вершин вы нашли, тем проще становится задача.

Можно ли решить задание №1 программой?

Технически — да.

Граф и таблицу можно представить программно и искать правильную комбинацию графов.

Но для стандартного задания №1 ЕГЭ это обычно совершенно не нужно.

Ручное решение:

• быстрее;
• проще;
• надёжнее;
• не требует написания и отладки программы.

Главное — научиться быстро видеть структуру графа.

Ошибка №1.  Перепутать наличие дороги и её длину

Запомните:

число в таблице одновременно говорит о двух вещах:

1. дорога существует;
2. число показывает её длину.

Для сопоставления графа и таблицы сначала важен только первый пункт.

Ошибка №2.  Смотреть только на степени вершин

Совпало количество дорог — ещё не значит, что вершины одинаковые.

Например:

Б — степень 3
Г — степень 3

Нужно дополнительно посмотреть их соседей.

Ошибка №3.  Найти одно соответствие и начать угадывать остальные

Лучше проверять каждое новое соответствие через связи.

Каждая найденная вершина должна сохранять структуру исходного графа.

Ошибка №4.  Перепутать строку и столбец

Для неориентированного графа это не страшно с точки зрения структуры: таблица симметрична.

Но при быстром чтении таблицы можно легко посмотреть не в ту ячейку.

Всегда проверяйте:

пересечение нужной строки и нужного столбца.

Ошибка №5.  Ошибиться в последнем действии

Иногда вся сложная часть выполнена правильно, но ученик неверно складывает длины нужных дорог.

Например, требуется найти:

АБ + БГ

После сопоставления получили:

А = P4
Б = P2
Г = P1

Тогда нужно найти:

P4–P2

и

P2–P1

а затем сложить именно эти два значения.

Проверьте вычисление отдельно.

Как проверить себя

Перед тем как вводить ответ, задайте себе три вопроса.

1. Все ли найденные дороги существуют одновременно и на графе, и в таблице?

Если на графе А соединена с Б, соответствующие P-вершины тоже должны быть соединены.

2. Не появилась ли лишняя дорога?

Если А и Д на графе не соединены, в таблице между соответствующими строками тоже не должно быть числа.

3. Точно ли я взял нужные значения после сопоставления?

Очень часто ошибка происходит уже после правильно решённого графа.

Короткий FAQ

Что проверяется в задании №1 ЕГЭ по информатике?

Умение считывать и сопоставлять информацию, представленную в различных информационных моделях. На практике обычно приходится работать с графом и таблицей дорог.

Нужно ли знать программирование?

Для стандартного решения — нет.

Что такое степень вершины?

Количество рёбер, выходящих из вершины.

Что означает число в таблице?

Между соответствующими вершинами существует дорога, а само число показывает её длину.

Что означает пустая ячейка?

Прямой дороги между этими вершинами нет.

Что делать, если две вершины имеют одинаковую степень?

Сравнивать их соседей и связи с уже найденными вершинами.

Нужно ли восстанавливать весь граф?

Не всегда. Если вопрос касается только нескольких вершин, иногда достаточно точно определить только их.

В чём главная ошибка учеников?

В спешке: неверно подсчитали степень, перепутали вершины или взяли не ту длину дороги.