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

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

Терминология

1. Граф - набор вершин и ребер, соединяющих их.

2. Смежность вершин - вершины смежные, если они соединены ребром

3. Таблица смежности - таблица, отображающая смежность вершин графа. Если в ячейке (1;2), (2;1) стоит звездочка, значит между первой и второй вершиной есть ребро.

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

5. Метка вершины - длина кротчайшего пути до этой вершины.

Заметим, что таблица симметрична относительно диагонали из левого верхнего угла в правый нижний. Происходит это потому, что если бы в (1;2) стояла звездочка, а в (2;1) — не стояла, то это значило бы что из первой вершины во вторую есть ребро, а из второго ребра в первую нет, но это абсурд. Также на диагоналях не может быть звездочек, потому что в заданиях не встречаются задачи с петлями (ребро из вершины в эту же вершину).

Когда мы разобрались с определениями, мы можем переходить к разбору задания. Всего у 1 задачи есть 3 типа: Неоднозначное и однозначное соотнесение таблицы с графом и задачи на алгоритм Декстера. Кардинальных различий между ними нет, лишь то, что в “Неоднозначных” не всегда можно точно определить полное соответствие между вершинами графа и их значением в таблице. Но в этих задачах это не требуется. Также в таблице смежности не указаны вершины, а их названия заменены на цифры. Обычно нам нужно найти соответствие между заданной вершиной и цифрой или длину ребра между двумя вершинами (если вместо звездочек стоят числа, соответствующие длине дороги).

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

Алгоритм решения:

1. Нужно у каждой вершины рядом записать ее степень

2. Разбить все вершины на группы по их степени

3. Установить соответствие между группой вершин и номерами вершин в таблице, которые им соответствуют. Если есть вершины со степенью, которая не повторяется у других вершин, то можно установить однозначное соответствие для этой вершины.

4. Разбить в одной группе на подгруппы по степени смежных с ними вершин

5. Проанализировать полученную информацию.

Неоднозначное соотнесение таблицы и графа

Пример 1.1:

В этой задаче нам необходимо определить под какими номерами записаны вершины A и G, причем нам не необязательно определять точное соответствие, достаточно найти два номера.

Начнем решать, пройдемся по пунктам нашего алгоритма

1. A – 3, B – 3, C –2, D – 3, E – 2, F – 6, G –3.

2. У нас получилось 3 группы. F-6 вершин, C и E – 2 вершины и A, B, D, G – 3 вершины.

3. Мы можем заключить, что вершине F соответствует номер 3, C и E — 4 и 5, а A, B, D и G — 1, 2, 6 и 7.

4. Заметим, что некоторые вершины графа симметричны C – E, D – B, G – A, также заметим, что группу степени 3 можно разбить на 2 подгруппы, те у которых смежные вершины имеют степень 3, 3, 6 и 3, 2, 6, вершины первой подгруппы - A, G, а вершины второй подгруппы - D, B.

5. Начнем анализировать информацию, вершины 4,5 (C, E) связаны с вершиными 3, 1, 2, мы знаем, что F-3, значит 1, 2 соответствуют B, D. Значит вершинам A и G соответствуют вершины 6 и 7.

Пример 1.2:

Рассмотрим еще одну задачу, в ней вместо звездочек нам даны числа, обозначающие длину ребер между вершин. Нам нужно найти сумму длин ребер Б - Д и В - Е.

Воспользуемся нашим алгоритмом

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

2. Здесь у нас получается всего две группы А - 2 вершины и Б, В, Г, Д, Е, К - 2 вершины.

3. Мы можем понять, что вершине А соответствует номер 4 из таблицы.

4. В группе Б, В, Г, Д, Е, К можем выделить подгруппу Б, В у них смежные вершины имеют степень 2, 3, 3, в то время как у всех остальных смежные вершины имеют степень 3, 3, 3.

5. Начнем анализировать информацию. Вершина А соединена с вершинами Б, В, а судя по таблице 4 вершина соединена с 3 и 6 вершиной, значит вершинам Б, В соответствуют вершины 3, 6. Рассмотрим вершины 3, 6, они соединены с вершинами 2, 4, 6 и 1, 3, 4 соответственно. Можем сделать вывод, что вершинам Д, Е соответствуют номера 1, 2. Тогда ребрам Б - Д и В - Е соответствуют ребра 3 – 2, 6 – 1. Их длина равна 14 и 8, а их сумма равна 22.

Пример 1.3:

В этой задаче нам необходимо найти сумму длин ребер D – B, A – E.

Воспользуемся нашим алгоритмом
1. A – 2, B – 3, C – 3, D – 3, E – 2, F – 2, G – 3.

2. В этой задаче у нас получится разделить все на 2 группы: A, E, F – 2 вершины, B, C, D, G – 3 вершины.

3. Пока что мы не можем определить какие вершины соответствуют каким номер, но мы можем понять, что вершинам A, E, F соответствуют номера 1, 6, 7, а вершинам B, C, D, G номера 2, 3, 4, 5

4. Заметим, что вершины со степенью 2 можно разделить на 2 подгруппы: A, E со смежными вершинами степени 2,3 и F со смежными вершинами степени 3, 3.

5. Начнем анализировать полученную информацию, начнем рассматривать с вершины F. Найдем в таблице вершину степени 2, которая соединена с 2 вершинами степени 3. Это номер 1, значит F – 1. Тогда по остатку заметим, что вершинам A, E соответствуют вершины 6, 7. Теперь заметим, что F соединена с вершинами B, G. Вершина B соединена с вершинами степени 3, 3, 2, а вершина G с вершинами степени 3, 2, 2. Рассмотрим таблицу, вершина F соединена с вершинами 4, 5. Заметим, что вершина 4 соединена с вершинами 1, 2, 7. Значит вершине G соответствует номер 4, тогда вершине B соответствует номер 5. Заметим, что вершины B, G имеют 2 общие смежные вершины F и C. Вернемся к таблице, вершины G, B смежные с вершинами 1, 2, 7 и 1, 2, 3, мы знаем, что номер 1 соответствует вершине F, тогда вершине C соответствует номер 2. Теперь мы можем понять, что вершине A соответствует номер 7, а вершине D соответствует номер 3. Вернемся к условию, нам нужно найти сумму длин ребер D – B, A – E. Длина A – E равна 39, а длина D – B равна 53, а их сумма равна 92.

Однозначные соотнесения таблицы и графа

Пример 2.1:

В этой задаче от нас требуется определить длину ребра B – E.

Пройдемся по нашему алгоритму

1. А - 2, Б - 2, В - 5, Г - 3, Д - 2, Е - 4, К - 2.

2. В этой задаче у нас получается 4 группы А, Б, Д, К со степенью 2, Г со степенью 3, Е со степенью 4 и В со степенью 5.

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

В этой задаче нам необходимо найти длину ребра Д - Е.

Пройдемся по пунктам алгоритма.

1. А - 1, Б - 4, В - 2, Г - 2, Д - 3, Е - 3, Ж - 5.

2. Заметим, что вершины Д, Е единственные вершины степени 3, значит мы можем понять, что им соответствуют номера 2 и 6. И сразу же получить, что длина ребра равна 25.

В этой задаче нам необходимо найти длину ребра А - Г.

1. А - 3, Б - 1, В - 4, Г - 4, Д - 2, Е - 1, К - 1.

2. У нас 4 группы, Б, Е, К имеют степень 1, Д имеет степень 2, А имеет степень 3, Г, В имеет степень 4.

3. Мы можем точно определить, что Д соответствует номер 4, вершине А соответствует номер 3, вершинам Г, В соответствуют номера 2, 5, вершинам К, Б, Е соответствуют номера 1, 6, 7.

4. Рассмотрим вершины В, Г. Заметим, что вершина Г соединена с вершиной Д. Вершина Д имеет номер 4, она соединена с вершинами 3 и 5, номеру 3 соответствует вершина А, значит вершине Г соответствует номер 5.

5. Теперь мы знаем номера вершин А, Г, их ребро равно 6.

Эти примеры показывают, что не обязательно полностью проходить по всем пунктам. Иногда для решения достаточно и нескольких пунктов.

Теперь давайте рассмотрим несколько заданий по теме алгоритм Декстера. Они отличаются от рассмотренных ранее, поэтому прошлый алгоритм здесь не подходит. Но у нас для этого задания есть алгоритм Декстера. Для начала введем новые определения

1. Метка вершины - длина кратчайшего пути до нее. Метку вершины можно вычислить если сложить каждую метку смежных вершин с длиной ребра от этой вершины до вычисляемой и взять наименьшее из полученных значений.

2. Обработка вершины - вычисление метки этой вершины.

Алгоритм Декстера:

1. Нарисовать начальную вершину нашего пути и сопоставить ей значение 0. Нарисовать все смежные с ней вершины и обработать их.

2. Поэтапная обработка всех вершин начиная с вершины с наименьшей меткой.

3. Когда все вершины обработаны, мы можем получить ответ.

Давайте научимся пользоваться этим алгоритмом на примере задач.

Алгоритм Декстера

Пример 3.1:

В этой задаче нам нужно найти длину кратчайшего маршрута из A в F.

Перед тем, как использовать алгоритм заметим, что из вершины С выходить 1 ребро. Это значит, что использовать вершину в пути от A до F не имеет смысла, потому что через нее пройти в другую вершину у нас не получится, а заходить и выходить не имеет смысла, поэтому будем строить граф без вершины C. Теперь можно воспользоваться алгоритмом.

1. Начнем наш путь из точки А, вершины B, D, F являются смежными для А, для каждой из этих вершин найдем их метку, так как мы только строим граф, то метка каждой вершины равняется длины ребра, соединяющего эту вершину с А.

2. Дорисуем все оставшиеся вершины. Заметим, что кратчайшее ребро в таблице имеет длину 2, значит до точки B нельзя добраться по пути короче, чем 2. Значит, можем считать, что точка В обработана. Сейчас нам нужно обработать вершину D. Чтобы попасть из точки А в точку D мы можем пойти 3 способами. Пройти напрямую из А в D, тогда длина маршрута будет 4. Пройти через точку F, тогда путь будет равен 36. Пройти через точку B, тогда путь будет равняться минимум 4 (2+2), потому что нам потребуется пройти хотя бы 2 дороги, а минимальная длина дороги равняется 2. Из этих трех вариантов наименьший путь имеет длину 4, значит у точки D метка равняется 4. Сейчас можем сказать, что мы нашли более короткий путь в точку F через вершину D, значит можем метку F уменьшить до 24.

Теперь рассмотрим вершину Е. В нее можно попасть 3 способами из точек B, D, F. Если мы пойдем из точки В, тогда путь будет равен 12, если пойдем из точки D, тогда путь будет равен 7, если пойдем из точки F, тогда путь будет равен 27. Значит можем сделать вывод, что метка Е равняется 7. И последний этап обработать точку F. В нее мы можем попасть из точек A, D, E. Если мы пойдем из точки А, тогда путь будет равен 36, если пойдем из точки D, тогда путь будет равен 24, если пойдем из точки Е, тогда путь будет равен 10. Значит метка вершины F равняется 10. Значит кратчайший путь из А в F будет также равняться 10.

Пример 3.2:

В этой задаче также нужно найти кратчайший путь из A в F.

Заметим, что вершина В имеет степень 1, значит мы можем смело ее не учитывать. Также заметим, что вершина F тоже имеет степень 1 и в F можно попасть только из вершины Е, значит можем вычислить метку Е и прибавить длину ребра в F. Теперь можно воспользоваться алгоритмом.

1. Построим вершину А и все смежные с ней. Построим метки для получившихся вершин.

2. Дорисуем оставшиеся ребра и начнем их обрабатывать. Заметим, что кратчайший путь равняется 3. Начнем обрабатывать вершину D. в нее мы можем попасть из вершины А и Е. Если мы пойдем из вершины А, то путь будет равняться 3, а если из вершины Е, то путь будет состоять минимум из 2 ребер, значит их длина будет равна 6. Значит метка D равняется 3. Теперь сразу перейдем к обработке вершины Е. В нее мы можем попасть из D, А или C, если пойдем из D, тогда длина маршрута будет составлять хотя бы 7. Если мы пойдем из А, тогда маршрут будет равен 8. И рассмотрим оставшийся вариант, когда мы идем из вершины С, в вершину С можно попасть из Е и А, но если мы попадаем из Е, а потом обратно идем в Е, то это полная бессмыслица, значит рассмотрим вариант, что мы идем в С из А, тогда путь А до Е будет составлять 14. Тогда метка Е равняется 7. Теперь нам остается к 7 прибавить длину пути Е - F, равный 4. Значит метка вершины F равняется 11, значит кратчайший путь A – F равняется 11.

Полезные факты

1. Сумма степеней всех вершин всегда равняется удвоенному числу ребер, происходит это потому, что каждое ребро мы считаем для двух вершин, которые оно соединяет. Этим можно пользовать, чтобы проверить себя. Например, вы выписали все степени вершин, посчитайте их сумму, если она окажется нечетной, тогда вы где-то ошиблись и стоит перепроверить.

2. Таблица симметрична относительно диагонали из верхнего левого угла в правый нижний, поэтому если в правой верхней половине у вас 5 звездочек, то и нижней левой у вас тоже будет 5. Это может пригодиться, если вы переписываете таблицу на листочек.

3. Если это задача на алгоритм Декстера и у вас есть вершина степени 1, которая не является началом или концом пути, то можно не рассматривать эту задачу.