Анализ информационных моделей. Решение задач ЕГЭ.

Тема: Анализ информационных моделей.

Что нужно знать:

• граф – это набор вершин и соединяющих их ребер; он описывается в виде таблицы (матрицы смежности или весовой матрицы)

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

• рассмотрим граф (рисунок слева), в котором 5 вершин (A, B, C, D и E); он описывается таблицей, расположенной в центре; в ней, например, число 4 на пересечении строки В и столбца С означает, что, во-первых, есть ребро, соединяющее В и С, и во-вторых, вес этого ребра равен 4; пустая клетка на пересечении строки А и столбца В означает, что ребра из А в В нет

• обратите внимание, что граф по заданной таблице (она еще называется весовой матрицей) может быть нарисован по-разному; например, той же таблице соответствует граф, показанный на рисунке справа от нее

• в приведенном примере матрица симметрична относительно главной диагонали; это может означать, например, что стоимости перевозки из В в С и обратно равны (это не всегда так)

• во многих задачах вес – это длина дороги из одного пункта в другой; для рассмотренного примера длина дороги из А в С равна 3, дороги из А в Е нет

• степень вершины – это количество рёбер, которые соединены с этой вершиной; при определении степени вершины по таблице нужно считать число непустых ячеек весовой матрицы в соответствующей строке (или столбце); в примере степень вершины А равна 2 (в первой строке две непустых ячейки со значениями 3 и 1)

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

Решение:

1. определим для каждой вершины её степень, то есть, количество рёбер, в которыми она связана; в таблице степень вершины – это количество заполненных клеток в строке (или в столбце)

3

1. сопоставление степеней вершин в таблице и на рисунке позволяет сразу обнаружить в таблице вершины А (она имеет № 3), Ж (№ 4) и Б (№ 6)

2. нас интересуют вершины Г и Ж; вершину Ж мы нашли, вершина Г имеет степень 2 и связана, кроме вершины Ж, с вершиной Д степени 3;

3. степень 2 имеют вершины № 1 и 2, но только вершина № 1 связана, кроме Ж, с вершиной степени 3 (№ 7), поэтому вершина № 1 – это Г

4. по таблице определяем протяжённость дороги из пункта Г в пункт Ж, она равна 9.

5. Ответ: 9.

На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Известно, что длина кратчайшего пути из пункта А в пункт Ж не больше 15. Определите, какова длина кратчайшего пути из пункта Д в пункт В. В ответе запишите целое число – так, как оно указано в таблице.

Решение:

1. сложность этой задачи в том, что схема симметрична; легко понять, что без дополнительных данных (используя только степени вершин – количество связанных с ними ребёр) мы не сможем различить вершины А и В, Г и Е, Д и Ж

2. определим степени вершин:

1. как и видно из рисунка, у нас две вершины степени 2 (А и В), две вершины степени 3 (Д и Ж) и три вершины степени 4 (Б, Г и Е), причем вершина Б однозначно определяется как вершина степени 4, которая связана с двумя вершинами степени 2

2. для того, чтобы различить оставшиеся вершины, определим длины путей ЖГА, ЖЕВ, ДГА и ДЕВ; мы не знаем, где какой маршрут, но точно знаем, что эти четыре маршрута

П3  П1  П7 = 7 + 12 = 19

П3  П6  П5 = 10 + 6 = 16

П4  П1  П7 = 5 + 12 = 17

П4  П6  П5 = 9 + 6 = 15

1. из дополнительного условия (Известно, что длина кратчайшего пути из пункта А в пункт Ж не больше 15.) находим, что маршрут ЖГА – последний, так что П4 = Ж, П6 = Г и П5 = А; в итоге получается

   	Е	Б	Д	Ж	А	Г	В
   Е		11	7	5			12
   Б	11				13	8	14
   Д	7			15		10
   Ж	5		15			9
   А		13				6
   Г		8	10	9	6
   В	12	14

2. кратчайший путь из Д в В можно найти с помощью дерева возможных маршрутов – это будет путь ДЕВ длиной 19

3. Ответ: 19.

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

Решение:

1. для того чтобы определить нужные нам вершины В и Е в весовой матрице, легче всего подсчитать степени вершин, то есть для каждой вершины найти количество рёбер, с которыми она связана (петля – ребро, которое соединяет вершину саму с собой, как кольцевая дорога, считается дважды)

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

1. по изображению графа находим, что вершина В имеет степень 5, а вершина Е – степень 4

2. в таблице есть ровно одна вершина, степень которой 5 (это П6) и одна вершина, степень которой – 4 (П4), их соединяет ребро длиной 20 (эти ячейки выделены в весовой матрице фиолетовым фоном).

3. Ответ: 20.

4. Бонус: попытаемся теперь определить, как обозначены остальные вершины в таблице. Каждая из вершин Д (степени 2) и Г (степени 3) соединена с уже известными вершинами В и Е, по таблице находим, что вершина Д – это П7, а вершина Г – это П2. Тогда вершина К соединяется с Е (П4) и Г (П2), то есть К – это П1. А вот различить вершины А и Б по этим данным не удаётся.

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

Решение:

1. определим степени вершин по весовой матрице и по изображению графа (как в предыдущей задаче):

1. по изображению графа находим, что обе интересующих нас вершины, А и Д, имеют степени 3; кроме того, степень 3 имеет еще и вершина Г

2. в таблице тоже есть три вершины со степенью 3 (это П1, П4 и П6), но вершина П1 (это вершина Г на рисунке!) не имеет общих ребёр с вершинами П4 и П6 (а это А и Д!);

3. таким образом, ответ – это длина ребра между вершинами П4 и П6 (эти ячейки выделены в весовой матрице фиолетовым фоном).

4. Ответ: 46.

5. Бонус: вершины В и Е, имеющие степени 5 и 4, это П3 и П7; с вершиной Г (П1) связана ещё вершина К, имеющая степень 2 – это П5; с Е связана ещё вершина Д – это П6; тогда П4 – это А, а П2 – это Б.

Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт E и не проходящего через пункт B. Передвигаться можно только по указанным дорогам.

Решение:

1. поскольку нас интересуют только маршруты, НЕ проходящие через пункт В, столбец и строку, соответствующие этому пункту, можно удалить из таблицы:

   	A	C	D	E	F
   A		4	8		16
   C	4		3
   D	8	3		5	3
   E			5		5
   F	16		3	5

2. дальше действуем так же, как показано при решении следующих далее разобранных задач; причем из всех маршрутов нужно оставить только те, которые проходят через пункт Е

3. первый шаг от А (в скобках указаны длины маршрутов):

АС (4), AD (8)

прямой маршрут AF не рассматриваем, потому что он не проходит через пункт E

1. второй шаг

ACD (7), ADC (11), ADE (13)

маршрут ADF не рассматриваем, потому что он не проходит через пункт E

1. третий шаг:

ACDE (12), ADEF (18)

маршрут ADEF дошел до пункта назначения;

маршрут ADC продолжать не имеет смысла, потому что из C можно проехать только в пункты A и D, где мы уже были;

маршрут ACDF не рассматриваем, потому что он не проходит через пункт E

1. четвертый шаг:

ACDEF(17)

1. этот маршрут тоже дошел до пункта назначения, его длина меньше, чем для предыдущего, его и выбираем

2. Ответ: 17.

Между населёнными пунктами A, B, C, D, E, F, G построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

Определите длину кратчайшего пути между пунктами A и G (при условии, что передвигаться можно только по построенным дорогам).

Решение:

1. начнём строить возможные маршруты из пункта A; за 1 шаг можно приехать в B, D или сразу в G (в скобках показаны длины маршрутов):

AB(5), AD(12), AG(25)

заметим, что G – это целевая точка (конечный пункт), поэтому мы уже имеем один полный маршрут длиной 25

1. строим двух шаговые маршруты: из B дальше можно ехать в D (возврат в А неинтересен!)

ABD (5 + 8 = 13)

этот маршрут нет смысла продолжать, поскольку в D можно приехать быстрее: длина уже найденного маршрута AD равна 12

1. из D можно ехать в B и C:

ADB (12 + 8 = 20)

ADC (12 + 2 = 14)

1. третий шаг: маршрут ADB продолжать бессмысленно: из B можно вернуться только в A и D

2. продолжаем маршрут ADC (14):

ADCE (14 + 4 = 18)

ADCF (14 + 5 = 19)

ADCG (14 + 10 = 24)

в последнем варианте мы приехали в конечный пункт, причем новый маршрут имеет длину 24

1. четвёртый шаг: продолжаем маршрут ADCE:

ADCEG (18 + 5 = 23)

и маршрут ADCF:

ADCFG (19 + 5 = 24)

1. других продолжений (без возврата в уже посещённые пункты) нет, поэтому кратчайший маршрут – ADCEG, он имеет длину 23.

2. Ответ: 23.

3. Заметим, что эти рассуждения можно зарисовать в виде дерева возможных маршрутов. После первого шага:

После второго шага:

После третьего шага:

После четвёртого шага: