Понятная информатика

Дерево — это структура данных, которая служит для описания иерархии — многоуровневой схемы, где одни элементы подчинены другим.  Дерево состоит из узлов (вершин) и связей между ними — дуг. 

Граф — это набор вершин (узлов) и связей между ними (рёбер). Данные о структуре графа можно записать в виде матрицы смежности: таблицы, в которой единица на пересечении строки X и столбца Y означает, что между узлами X и Y есть связь; ноль указывает на то, что связи нет (рис. 1.12).

Строго говоря, граф — это математический объект, а не рисунок. Конечно, его можно нарисовать на плоскости, но матрица смежности (и список смежности) не даёт никакой информации о том, как именно располагать узлы друг относительно друга. Для таблицы на рис. 1.12 возможны, например, такие варианты, как на рис. 1.13.

Путь — это последовательность рёбер, по которым можно перейти из одного узла в другой.

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

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

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

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

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

№ 1281 Открытый вариант КЕГЭ (Уровень: Базовый)

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

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

Решение

Здесь одна уникальная вершина - А (2 степени), все остальные вершины - по 3 степени. Схема симметричная относительно А и К, ищем сумму вершин, поэтому не нужно точно устанавливать их соответствие с номерами.

Вершина А = 4, которая соединена с Б =3 (расстояние АБ = 13) и В = 6 (расстояние АВ = 11). Тогда Д = 4 и БД =14, а Е = 1 и ВЕ = 8. Тогда искомая сумма Д + ВЕ =14+8 = 22.

Ответ:  22

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

Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта D в пункт G и из пункта A в пункт C.

Решение

В данной задаче четыре вершины 3 степени (C, D, F, G) и три - 2 степени (А, В, С).

Уникальная вершина здесь G = 5, так как только она соединена со всеми остальными вершинами 3 степеней (1, 3 и 6). При этом вершина Е (2 степени) лежит между С и F 3 степеней), то Е = 7, а вершина С (3 степени) соединена с G, а также с А и Е (обе 2 степени), то С = 1, А = 4, D = 6, Е = 7, F = 3.

Тогда искомая сумма DG + АС = 8 + 30 = 38.

Ответ:  38

№ 1887 (Уровень: Базовый)

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

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями  на графе.

Определите, какова протяжённость дороги из пункта Д в пункт Е. В ответе запишите целое число – так, как оно указано в таблице.

Решение

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

Ответ:  7

№ 1429 (Уровень: Средний)

На рисунке изображена схема дорог Н-ского района, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.

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

Решение

Уникальные вершины - Ж и К (2 степеней, все остальные -3 степеней), тогда Ж и К - это вершины 2 и 7. Вершина Д лежит между Ж и К, тогда Д = 3.  Вершина Е соединена с двумя вершинами 3 степеней (Б и В) , а также с вершиной К. При этом К и В соединены с Д.

Вершина В (единственная 3 степеней) связана с Д, то В = 4. При этом В связана с Ги Е,  которая связана с А и Е. Здесь Е связана с К, то Е = 6 и К = 2, тогда Ж = 7. Отсюда получаем, что Б = 1, А = 5 и Г = 8. Тогда БВ = 14.

Ответ: 14

№ 1247 (Уровень: Средний)

Ha рисунке схема дорог Н-ского района изображена в виде графа, в таблице звездочкой отмечено наличие дороги между пунктами.

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Установите соответствие между номерами пунктов в таблице и буквенными обозначениями на графе. В ответе запишите последовательность номеров пунктов, соответствующую последовательности пунктов АБВГДИК, без пробелов и дополнительных символов.

Решение

Уникальная точка здесь - Г (1 степень), тогда Г = П4. С нею связаны вершина Б (4 степени), то Б = 5. Вершина Б связана с А (2 степени), В (4 степени),  Г и Д (2 степени), тогда А = 1, В = 6 и Д = 2. Вершина В (3 степени) соединена с А = 1, И (3 степени) и К (2 степени), то  И = 3 и К = 7. Оставшаяся вершина Д  соединена с Б = 5 и И = 3, то Д = 2.

Тогда искомая последовательность АБВГДИК = 1564237.

Ответ: 1564237

Решение

Уникальная вершина здесь - Г (4 степени) = П5, у вершин А и Б - по 3 пути, при этом А и Г соединены напрямую и через В, Б и Г - через Д. У остальных вершин, в том числе и у искомых - по 2 пути.

Искомые вершины Д и Е не пересекаются друг с другом, но обе они связаны с вершиной Б, а Д - так же и с Г. Вершина Б (3 степени) НЕ пересекается с Г, тогда Б = П2. При этом она пересекается с А (3 степени), а так же с Д и Е - искомыми вершинами. Тогда А = П4, а Е и Д = П3 и П7.

Ответ: 37

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

В таблице в левом столбце указаны номера пунктов, откуда совершается движение, в первой строке – куда. Определите длину дороги между пунктами Г и Е.  Передвигаться можно только по указанным дорогам.

Решение

В этой задаче задан ориентированный граф, то есть идти по нему можно только в направлении, указанном стрелками. При этом исходяшие пути указаны по столбцам, а входящие - по строкам. При этом запись  0 -> А -> 2 (Б, В) означает, что в вершине А нет входящих путей, но есть два исходящих.Продолжим описывать схему:

 2 -> Б -> 1,   3 -> В -> 1,   2 -> Г -> 3,   2 -> Д -> 1,   2 -> Е -> 1,   0 -> К -> 2.

Из вершин А и К исходят по два пути, но входящих путей нет ни одного, то это вершины П6 и П7. Пусть А = П6 и К = П7.  У вершины Б два входящих пути и один исходящий, то Б = П5, В = П3, Г = П4, Д = П1, Е = П2.  Тогда длина дороги ГЕ = 10.

Ответ: 10

Решение

Заметим, что данная схема симметрична как по горизонтали, так и по вертикали, при этом здесь две вершины (С и F - номера П3 и П7) - по 4 степени, все остальные - по 3 степени. Решать такую задачу стандартным способом, рассматривая вначале схему и связывать её с таблицей сложно. Поэтому будем решать в обратную сторону, начнём с таблицы.

С вершиной П3 соединены вершины с номерами П1, П6, П7 и П8 в неопределённом порядке. При этом П1, П3 и П8 пересекаются в точке П6. Как определить, чему равна П3 - это С или F? Для ответа на этот вопрос найдём сумму, заданную в условии: П1-П8 + П1-П6 = 20 + 21 = 41 > 25, что нарушает условие задачи, то есть П6 - это не G. Тогда П6 = А, и длина пути П3-П6 = 10.

Проверка решения

С вершиной П7 соединены вершины с номерами П2, П3, П4 и П5 в неопределённом порядке. При этом вершины П2 и П5 пересекаются в П4. Тогда сумма путей П2-П4 + П2-П5 = 5 + 12 = 17 < 25, что соответствует условию задачи. Отсюда следует, что П2 = G. Решение верно.

Ответ: 10

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

Известно, что длина кратчайшего пути из пункта A в пункт Д не превышает 30 километров. Определите длину кратчайшего пути между пунктами Ж и Г. Передвигаться можно только по указанным дорогам.

Решение

Здесь уникальные вершины - Ж и Д (по 2 степени), то Ж и Д - это П3 и (или) П7. Вершины Б, Г и Е - по 4 степени, при этом Е лежит между Ж и Д., то Е = П2, так как только эта вершина связана одовременно с П3 и П7. У вершин А и В - по 3 степени.

Отметим, что схема симметрична относительно оси А-Е. Тогда обозначим остальные вершины, взяв Ж и Д как П3 и П7 соответственно. После связки всех остальных вершин (точек пересечения) схема совпала с таблицей.

Отметив номера вершин в схеме черным цветом, а длины всех путей соответственно таблице - синим цветом, получаем самый короткий путь из Ж в Г (3 в 1) будет ЖЕГ = ЖЕ + ЕГ = 28.

Ответ: 28

№ 484 Джобс 19.10.2020 (Уровень: Сложный)

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

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

Решение

В условии сказано, что нужно пройти через все пункты, а о прохождении всех дорог - ни слова, поэтому берём все пути по одному разу, петли не рассматриваем!

Если взять А = 1 и обозначать далее все вершины аналогично А1, то путь в соответствии с таблицей можно обозначить так: 

А1 - Б3 - В2 - Г8 - Д5 - Е4 - И6 - К7 - А1 = 9 + 7 + 10 + 12 +17 + 11 + 8 + 9 = 83

Ответ: 83

Решение

Граф в этой задаче - несимметричный, так как все пути идут только в указанном направлении. Обозначим долги, используемые в этой игре как данные, привычными нам дорогами (путями), что не изменит суть задачи. При этом входящие дороги идут по горизонтали таблицы, исходящие - по вертикали.

В точку Б входят три пути (из А, С и Т) и выходит из Б путь в точку И, то Б = Г1 и И = Г4. Также в И входит путь из В = Г6 и один выходит в Т = Г3. При этом в В входит путь из точки А, то А = Г2. Путь из А идет в С, то С = Г5.

Тогда долг В-И = Г6 - Г4 = 300.

Ответ: 300