Задание 1 ЕГЭ по информатике

💬 (0)

02.04.2024

Сборник необходимой теории и практики к заданию №1 ЕГЭ 2024 по информатике «Использование и анализ информационных моделей (таблицы, диаграммы, графики)».

• Вся теория по информатике для ЕГЭ
• Тренировочные варианты ЕГЭ по информатике

Формулировка задания №1 ЕГЭ 2024 из демоверсии ФИПИ

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

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

Все типы заданий №1 

Элементы теории графов

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

Вершины и рёбра графа 

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

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

Количество вершин графа называют его порядком. Количество рёбер называют размером графа.

Взвешенный граф

Рёбрам графа могут быть сопоставлены числовые значения, которые называют весами рёбер. Например, вес ребра в графе, обозначающем дорожную сеть, может представлять собой длину соответствующей дороги между вершинами графа, обозначающими населённые пункты.

• Взвешенный граф — это граф, рёбрам которого назначены значения весов. 

Мультиграф

Две вершины называют концевыми вершинами (концами) ребра, которое их соединяет. При этом говорят, что ребро инцидентно каждой из соединяемых им вершин, и наоборот, каждая концевая вершина называется инцидентной соединяющему их ребру. Две концевые вершины одного и того же ребра называют соседними.

Рёбра, имеющие общую концевую вершину, называют смежными. Рёбра, инцидентные одной и той же паре вершин (т.е. соединяющие одну и ту же пару вершин) называют кратными, или параллельными.

• Мультиграф — это граф с кратными рёбрами.

Псевдограф

Ребро, концами которого является одна и та же вершина, называется петлёй.

• Псевдограф — это граф , содержащий петли (и кратные рёбра).

Ещё немного о вершинах

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

Вершина называется изолированной, если она не является концом ни для одного ребра. Вершина называется висячей (листом), если она является концом ровно одного ребра.

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

Путь в графе

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

Циклом называют путь, в котором первая и последняя вершины совпадают. Путь (или цикл) называют простым, если рёбра в нём не повторяются. Простой путь (цикл) называют элементарным, если вершины в нём не повторяются.

Длиной пути (или цикла) называют количество составляющих его рёбер.

• Связный граф — это граф, в котором для любых двух вершин существует связывающий их путь.
• Сильно связный граф — это ориентированный граф, в котором существует маршрут из любой вершины в любую другую.

Неориентированный и ориентированный граф

В неориентированном графе связи между любыми парами концевых вершин являются двунаправленными, т.е. эти концевые вершины «равноправны» по отношению к этой связи.

В ориентированном графе связи между концевыми вершинами являются направленными. Рёбра ориентированного графа называют дугами. Пути в ориентированном графе называют ориентированными путями (маршрутами). Замкнутый путь (цикл) в ориентированном графе называют контуром.

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

Полный направленный граф называют турниром.

• Обратный граф — это ориентированный граф, полученный из исходного путём смены направлений рёбер на противоположные. 

Способы представления графов

1. Графический способ — изображение графа.

2. Список рёбер — перечисление всех рёбер графа как пар обозначений связываемых этими рёбрами вершин. Пример: {A, B}, {A, D}, {A, C}, {B, C}, {C, D}.

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

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

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

4. Матрица инцидентности — таблица, столбцы которой соответствуют вершинам, а строки – рёбрам. При этом в ячейках на их пересечении записываются числа:

• для неориентированного графа – число 1, если данная вершина инцидентна данному ребру, или 0 – в противном случае;
• для ориентированного графа – число -1, если данная дуга исходит из данной вершины, число 1, если данная дуга входит в данную вершину, число 2, если дуга представляет собой петлю, или 0 – в противном случае.

Как решать задание №1?

Пример 1: 

Пример 2:

Примеры заданий №1

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

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

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

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

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

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

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

Каждому населённому пункту на схеме соответствует его номер в таблице, но неизвестно, какой именно номер. Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам A и G на схеме. В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.

Ответы к примерам заданий №1

1. 16; 2. 33; 3. 66; 4. 67. 

Ниже представлены замечательные материалы, подготовленные Поляковым Константином Юрьевичем, доктором технических наук. В них вы найдёте всё самое полезное для себя — теория, решения заданий и практика. Все материалы для ЕГЭ по информатике: https://kpolyakov.spb.ru/school/ege.htm. 

Смотреть в PDF:

Или прямо сейчас: cкачать в pdf файле.