На первый взгляд всё просто. Но именно из-за этого ученики часто начинают торопиться и теряют балл на невнимательности.

В этой статье разберём:

• что такое граф, вершина и ребро;
• как читать таблицу дорог;
• как сопоставлять вершины графа со строками таблицы;
• как решать задание №1 пошагово;
• какие ошибки встречаются чаще всего;
• как ускорить решение на экзамене.

Немного теории: что такое граф

Граф — это набор объектов и связей между ними.

Объекты называются вершинами, а связи между ними — рёбрами.

Например:

А — Б

Здесь:

• А и Б — вершины;
• линия между ними — ребро.

В заданиях ЕГЭ вершины часто обозначают населённые пункты:

А, Б, В, Г, Д...

А рёбра показывают дороги между ними.

Пример графа

Рассмотрим такой граф:

На рисунке видно несколько населённых пунктов и дороги между ними.

Важно понимать:

Если две вершины соединены линией, между ними существует прямая дорога.

Если линии нет — прямой дороги нет.

Например, если:

А — Б

но А и Е не соединены,

значит:

• из А в Б можно попасть напрямую;
• из А в Е прямой дороги нет.

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

Очень важное понятие для задания №1 — степень вершины.

Степень вершины — это количество рёбер, которые из неё выходят.

Представим:

    Б
    |
В — А — Г

Из вершины А выходят три дороги:

• А–Б;
• А–В;
• А–Г.

Значит:

степень вершины А равна 3.

Или проще:

Степень вершины = количество её соседей.

Это один из главных инструментов при решении первого задания.

Как читать таблицу дорог

Вторую часть задания обычно представляет таблица.

Например:

Что означает число 7 на пересечении P1 и P2?

Это значит, что:

между P1 и P2 есть дорога длиной 7.

А если ячейка пустая?

Значит:

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

Главное правило задания №1

Запомните одно правило:

Есть ребро на графе → есть число в таблице.

И наоборот:

Есть число в таблице → есть ребро на графе.

Именно на этом построено практически всё решение.

Почему таблица симметрична

Обратите внимание:

если из P1 в P2 дорога имеет длину 7, то и из P2 в P1 эта же дорога имеет длину 7.

Поэтому таблица получается симметричной:

Число записывается дважды.

Это нормально.

На самом графе при этом изображается всего одно ребро.

Самое главное: названия вершин не совпадают

Вот здесь начинается само задание.

На графе вершины могут называться:

А, Б, В, Г, Д, Е

а в таблице:

P1, P2, P3, P4, P5, P6

Нам неизвестно, какой букве соответствует какой номер.

Например:

А = ?
Б = ?
В = ?
Г = ?
Д = ?
Е = ?

Задача ученика — восстановить это соответствие.

После этого можно найти нужную длину дороги.

Лучше всего использовать один и тот же алгоритм.

Шаг 1. Посчитайте количество дорог у каждой вершины графа

Посмотрите на рисунок.

Например:

А — 4 дороги
Б — 3 дороги
В — 2 дороги
Г — 3 дороги
Д — 3 дороги
Е — 1 дорога

Эти числа лучше подписать прямо рядом с вершинами.

Так искать соответствия гораздо проще.

Шаг 2. Посчитайте количество дорог для каждой строки таблицы

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

Нужно посчитать количество ненулевых значений в каждой строке.

Например:

P1 → 3 числа
P2 → 3 числа
P3 → 1 число
P4 → 4 числа
P5 → 3 числа
P6 → 2 числа

Количество чисел в строке — это и есть степень соответствующей вершины.

Шаг 3. Найдите вершины с уникальной степенью

Начинать лучше всего не с вершин, у которых много похожих вариантов, а с тех, которые легко узнать.

Например:

На графе только у вершины А четыре дороги.

В таблице только у P4 четыре ненулевых значения.

Значит:

А = P4

Это уже надёжное соответствие.

Шаг 4. Найдите следующую уникальную вершину

Допустим, на графе только у вершины Е одна дорога.

В таблице только строка P3 содержит одно число.

Тогда:

Е = P3

Получаем уже две известные вершины:

А = P4
Е = P3

Но что делать, если степени одинаковые?

Это самая важная часть задания.

Представим, что:

Б — 3 дороги
Г — 3 дороги
Д — 3 дороги

А в таблице:

P1 — 3 дороги
P2 — 3 дороги
P5 — 3 дороги

По одной только степени определить соответствие невозможно.

И здесь нужно использовать соседей.

Метод соседей

Допустим, мы уже выяснили:

А = P4

Посмотрим на граф.

Пусть вершина Б соединена с А.

Значит соответствующая Б строка таблицы обязательно должна быть связана с P4.

Если:

P1 соединена с P4
P2 соединена с P4
P5 НЕ соединена с P4

то P5 уже нельзя считать вершиной Б.

Так постепенно количество вариантов уменьшается.

Главный принцип решения

Очень полезно мыслить так:

Я сравниваю не буквы и числа.
Я сравниваю структуру связей.

Например, вершина может иметь:

• три дороги;
• быть соединена с вершиной степени 4;
• быть соединена с вершиной степени 2;
• не быть соединена с вершиной степени 1.

Это уже почти уникальная характеристика вершины.

Такую вершину легко найти в таблице.