Определение. Пусть G - ориентированный граф. Пусть Mc - квадратная матрица, строки и столбцы которой обозначены вершинами ориентированного графа G. Элемент i-ой строки и j-гo столбца матрицы Mc, обозначаемый cij, равен единице, если имеется ребро из i-ой вершины в j-ую вершину, и равен нулю в противном случае. Матрица Mc называется матрицей смежности графа G. Замечание. Для сокращения записи обозначения строк и столбцов в матрицах смежности можно опускать, но рекомендуется их оставлять, особенно в матрицах больших размерностей...

В статье рассматривается решение задания из ЕГЭ по информатике, связанной с анализом графов и матриц смежности для определения номеров населённых пунктов на схеме дорог. Описан как краткий алгоритм решения подобных задач, так и подробное решение конкретной задачи из открытого варианта ЕГЭ. Задания №1 (по графам) из ЕГЭ по информатике проверяют навыки анализа и интерпретации информации, представленной в виде схем, таблиц или матриц смежности. Они могут включать: Основные понятия, необходимые для решения:...