Задачи на графы встречаются в ЕГЭ по информатике в разных форматах: в заданиях на маршруты, таблицы, схемы и анализ связей. Многие ученики их боятся, потому что слово «граф» звучит страшно и ассоциируется с чем-то из университетской математики. На деле большинство задач ЕГЭ на графы решаются одним методом — и когда он освоен, задача становится почти механической. Граф — это набор вершин (точек) и рёбер (связей между точками). Всё. Никакой магии. Когда вы рисуете схему городов с дорогами между ними, или рисуете связи между людьми в социальной сети — вы рисуете граф...

Задание 1 ЕГЭ по информатике направлено на проверку навыков представлять, считывать и анализировать данные в разных типах информационных моделей. Про информационные модели мы уже говорили ранее. В первых заданиях ЕГЭ нам предстоит работать с графами и таблицами. Граф в этих заданиях представляет собой упрощённую схему дорог между несколькими населёнными пунктами. Что же касается таблиц, точнее будет сказать матриц, то используются как матрицы смежности, так и весовые матрицы. Как раз по этим матрицам...