Что проверяет задание

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

Обычно спрашивают номера конкретных пунктов, длину дороги между пунктами или сумму длин.

Определения

Граф, набор вершин и рёбер. Вершина, пункт, ребро, прямая связь между двумя пунктами.

Неориентированный граф, связь двусторонняя: из A в B можно пройти тогда и только тогда, когда из B в A.

Ориентированный граф, связь может быть односторонней. На схеме её показывают стрелкой.

Степень вершины, сколько рёбер выходит из пункта. В неориентированном графе это число соседей. В ориентированном различают исходящую и входящую степень.

Вес ребра, число на связи: длина дороги, стоимость, время.

Матрица смежности, квадратная таблица. Строка и столбец с одним номером соответствуют одному пункту. Ячейка говорит, есть ли прямая связь между этими пунктами.

Матрица весов, та же таблица, но вместо отметки «есть дорога» стоит длина. Пустая ячейка означает отсутствие прямой дороги.

Петля, ребро из пункта в себя. На экзамене петель обычно нет, главная диагональ таблицы пустая.

Симметричная таблица, ячейка (i, j) совпадает с (j, i). Так бывает у неориентированного графа.

Изоморфизм моделей, такое сопоставление букв и номеров, при котором каждая связь на схеме есть в таблице, и наоборот. Если веса указаны, они тоже должны совпасть.

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

• отметка *, + или другое «есть связь», прямая дорога;
• число, длина этой дороги;
• пусто, прямой дороги нет.

Сумма отметок (или ненулевых длин) в строке пункта равна его степени, если граф неориентированный и петлей нет.

Общий алгоритм решения

1. Выписать степени всех вершин на схеме и все степени по строкам таблицы.
2. Сопоставить пункты, чья степень уникальна: такая буква может соответствовать только такому номеру.
3. Для неоднозначных пунктов смотреть соседей: набор степеней соседей (и веса рёбер) должен совпасть.
4. Если схема ориентированная, сопоставлять исходящие и входящие связи отдельно: строка таблицы, «куда можно из пункта», столбец, «откуда можно в пункт».
5. Когда соответствие восстановлено, ответить на вопрос условия, читая уже нужную ячейку таблицы.

Если подходящих сопоставлений несколько, ответ на вопрос всё равно должен быть одним и тем же при любом допустимом соответствии. Если это не так, сопоставление ещё не доведено до конца.