Симметричные и несимметричные графы в ЕГЭ по информатике (№ 1)

Граф — это рисунок, где объекты (города, пункты) показаны точками, а связи между ними — линиями.

Вершина (узел) — точка графа. На схемах ЕГЭ это всегда населённый пункт: его обозначают буквой (А, Б, В…) или номером (П1, П2…).

Ребро — линия, соединяющая вершины. Если на линиях нет стрелок, граф неориентированный (дорога работает в обе стороны); в ЕГЭ почти всегда именно такие графы.

Степень вершины — число рёбер, выходящих из неё. Для решения задания это самая важная характеристика. Простой пример: если из города А ведут 3 дороги к соседям, его степень равна 3.

В задании дают рисунок (граф с буквами) и таблицу с номерами (П1, П2…). Их рисовали независимо друг от друга, поэтому буква А не обязательно соответствует П1.

Таблица всегда симметрична относительно главной диагонали: если есть дорога из П1 в П2, то есть и дорога из П2 в П1.

Чтобы сопоставить буквы с номерами, нужно найти пункт, который нельзя ни с чем перепутать.

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

Действуем так:

1. Считаем число дорог у каждой буквы на схеме.
2. Считаем число дорог у каждого номера в таблице (сколько чисел в строке).
3. Ищем уникальную степень — ту, которая встречается только один раз.

Например, если у буквы Б степень 2 и в таблице ровно у одного номера, П6, тоже степень 2, — значит, Б = П6. Мы нашли «уникум». Чаще всего уникальными оказываются вершины с самой большой степенью или, наоборот, с самой маленькой — всего с одной дорогой.

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

Допустим, остались две буквы (Г и К) и два номера (П5 и П7). У всех степень 2. Как их различить?

Нужно посмотреть на их соседей. Мы уже знаем, где какие буквы (нашли «уникумы» ранее).

• Смотрим на графе: буква Г соединена с пунктами A и B.
• Ищем в таблице: какой номер (П5 или П7) соединяется с номерами, которые мы уже присвоили буквам A и B?
• Чей набор соседей совпал — тот и есть пункт Г.

Задание 1

На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта Г в пункт В и из пункта А в пункт З. В ответе запишите целое число.

Решение

Дорога А-З. На графе это единственные соединённые между собой вершины степени 2. В таблице им соответствует единственная пара взаимосвязанных вершин степени 2 — П1 и П5. Длина дороги между ними равна 43.

Дорога Г-В. На графе это вершины степени 3, которые одновременно соединены с вершиной Б (степень 3, связана с А). В таблице вершина Б — это П7 (так как она связана с П5(А)). Из таблицы видно, что П7 соединена с П2 и П8. Дорога между П2 и П8 существует и равна 18, что соответствует ребру Г–В.

43 + 18 = 61.

Ответ: 61.

Задание 2

На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта Б в пункт Д и из пункта Ж в пункт З. В ответе запишите целое число.

Решение

Вершины В и Г. На графе это вершины степени 2, связанные между собой. В таблице единственная связанная пара вершин степени 2 — это П1 и П6.

Дорога Б-Д. На графе Б и Д — это вершины степени 3, соединённые ребром. Эти вершины связаны с парой В и Г. В таблице единственная подходящая и связанная пара вершин степени 3 — это П8 и П5 соответственно. Длина дороги между ними равна 39.

Дорога Ж-З. Вершина З имеет степень 2 и соответствует П2, так как она соединена с двумя вершинами — П4 и П7, — которые связаны между собой. Вершина Ж имеет степень 3 и соединена с двумя вершинами степени 2; в таблице этому условию соответствует П4. Значит, дорога Ж–З — это П2–П4, её длина равна 53.

39 + 53 = 92.

Ответ: 92.

Задание 3

На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта Ж в пункт Д и из пункта Ж в пункт Е. В ответе запишите целое число.

Решение

Определение вершины Ж. На графе вершина Ж имеет степень 2 (две дороги) и соединена с Д и Е. В таблице вершины со степенью 2 — это П2, П3 и П4. Из них только П4 имеет обе дороги к вершинам степени 3 (П1 и П6), что соответствует вершинам Д и Е.

Поиск суммы. Нам нужно найти сумму дорог из Ж в Д и Е, то есть полную сумму длин всех дорог, выходящих из вершины Ж (П4). Это дороги к П1 (8) и П6 (30).

8 + 30 = 38.

Ответ: 38.

Задание 4

На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта Г в пункт В и из пункта Д в пункт Е. В ответе запишите целое число.

Решение

Определение вершины А. На графе вершина А имеет степень 6 (связана со всеми остальными пунктами). В таблице строка с шестью связями — это П2.

Дорога Г-В. На графе пункты Б и Ж имеют степень 2. В таблице строки с двумя связями (кроме связи с П2(А)) — это П5 (связи с П1, П2) и П6 (связи с П2, П4). Значит, Б и Ж — это П5 и П6. Их соседи (помимо А) — это П1 и П4, которые соответствуют вершинам В и Е.

Нам нужна вершина Г, которая имеет степень 3 и соединена с В(П1/П4) и Д. В таблице оставшиеся вершины — это П3 и П7. Посмотрим на связи: П3 соединена с П1(7) и П2(А), а П7 соединена с П4(13) и П2(А). Также П3 и П7 соединены между собой (14). Значит, П3 и П7 — это и есть вершины Г и Д, а П1 и П4 — это В и Е.

Соответственно, дороги Г-В и Д-Е — это связи между парами {П3, П7} и {П1, П4}. По таблице это дороги П3–П1 (7) и П7–П4 (13).

7 + 13 = 20.

Ответ: 20.

Задание 5

На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта Б в пункт В и из пункта Д в пункт Е. В ответе запишите целое число.

Решение

Определение вершин Г, В, Д. На графе вершина Г имеет степень 2 (две дороги). В таблице степень 2 имеет П1, которая соединена с двумя пунктами П2 и П6, которые не пересекаются между собой. Значит, это вершины В и Д.

Поиск дорог Б-В и Д-Е. Вершины В и Д соединены с Б и Е соответственно. Из таблицы видно, что соседи П2 — это П4 (длина 6), а соседи П6 — это П3 (длина 11). Эти дороги и являются искомыми путями Б-В и Д-Е.

6 + 11 = 17.

Ответ: 17.

В задании № 1 главное — правильно сопоставить буквы на схеме с номерами в таблице. Для этого считают степень каждой вершины: сначала находят «уникумы» — пункты с неповторяющейся степенью, а затем по соседям различают вершины с одинаковой степенью. Как только соответствие установлено, остаётся взять из таблицы нужные длины дорог и сложить их. Освоив подсчёт степеней и анализ соседей, ты сможешь быстро решать и «симметричные», и «несимметричные» варианты задания № 1.