Немного теории
Схема дорог между городами, структура предприятия, генеалогическое дерево - это примеры информации, в которой графически отражена связь между объектами. В информатике (и дискретной математике) такие схемы называются графами.
Граф — это структура данных, где объекты (например, города) выражены узловыми точками (кружками), а связи между ними - линиями. Узлы графа называются вершинами, а линии между узлами - ребрами графа.
Согласитесь, что для человеческого глаза такое представление информации более наглядно и информативно (смотрим на схему метро), чем, предположим, просто перечень в виде списка.
А вот компьютерной программе схема в виде рисунка не понятна. И программист должен отобразить данные графа в другом представлении, например, в виде таблицы.
Таблица, в которой название столбцов и строк — это список вершин (городов) называется таблицей (матрицей) смежности. Обратите внимание, что данные по конкретной вершине графа в таблице будут одинаковы и по горизонтали, и по вертикали, т.е. столбец дублирует строку под тем же номером.
Количество ячеек с данными (не пустых) в столбце, или в соответствующей строке, — это количество ребер (дорог) исходящих из вершины. В информатике, количество ребер примыкающих к вершине принято называть степенью вершины.
Задание №1 ЕГЭ по информатике
Вот суть задания: Дана схема городов в виде графа и, соответствующая этому графу, таблица смежности. Сопоставив степень вершин на графе (количество исходящих ребер), обозначенных буквами, со степенью вершин в таблице (количество не пустых ячеек) в столбце (или строке), обозначенных цифрами, нужно найти их соответствие и ответить на вопрос задания.
При определенных навыках эта задача решается быстро и устно.
Навык 1. Увидеть симметрию, найти "уникальную вершину" (иногда пару вершин) - такие вершины, которые точно можно идентифицировать. Например, по количеству исходящих ребер (только одна вершина имеет степень 5) или по степени соседей (вершин степени 2 несколько, но только одна связана с вершинами степени 3).
Навык 2. Находить номер уникальной вершины (пары вершин) в таблице смежности.
Для этого подсчитываем в строках (или столбцах) количество не пустых ячеек, чтобы найти свою избранную.
Навык 3. Анализировать соседей выбранной вершины. Для этого мы должны обратить внимание на степень вершины соседей. Если на избранную вершину смотрим в столбце, то степень соседей смотрим в строке. На рисунке это понятней.
Стоит отметить, что, иногда в этом задании удобнее смотреть не на наличие данных, а на их отсутствие. Например, если уникальная вершина имеет большую степень, то выгоднее смотреть не на соседей, а на пустые ячейки. В этом случае именно они сообщат больше информации, чем соседи.
Отсутствие данных - это тоже информация, которую можно использовать. Если смежных вершин много и они все одинаковой степени, то скорее всего вопрос задания будет в поиске отдалённых вершин.
Попробуйте свои силы в решении этого задания в формате ЕГЭ.
Не спешите, решая данную задачу. В подобных задачах можно не заметить некоторые подвохи. Особенно, когда граф симметричный и нельзя точно определить соответствие. Как правило, в таких задачах вопрос заключается в нахождении пары взаимозаменяемых данных. Что-то типа “найдите сумму расстояний между пунктами A K и B C”. Это будут две симметричные ветви графа, и точно определить одно из них по предложенным данным не получится, а вот найти сумму этой симметричной пары — запросто.
Несмотря на то, что эту задачу можно решить устно, на экзамене обязательно делайте записи. Прописывайте степень вершины каждого узла. Наш ум иногда слеп к собственным ошибкам. Разработайте собственную систему записи решения данной задачи. Главное, чтобы вам было комфортно её решать.
Сделайте другие задания ЕГЭ или заметный перерыв, а потом обязательно вернитесь к простым заданиям и решите их заново. Если ответы совпадут — прекрасно. Надо научится решать подобные задания быстро и точно.
Ответы для проверки к заданиям: 1)34, 2)35, 3)37 4)34, 5)32, 6)45
