Графы: понятие и представление

Что такое граф

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

Граф состоит из двух основных элементов: вершин и рёбер. Вершины обозначают объекты, а рёбра показывают связи между ними. Например, в графе городов вершины — это города, а рёбра — дороги. Граф обычно записывают как пару G = (V, E), где V — множество вершин, а E — множество рёбер.

Если связь не имеет направления, граф называют неориентированным. Так можно представить обычную дорогу между двумя городами. Если важно, откуда и куда движутся, используют ориентированный граф. Его ребро изображают стрелкой: A → B означает переход из A в B.

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

Основные виды и понятия

Две вершины называют смежными, если между ними есть ребро. Ребро, соединяющее вершины A и B, можно записать как AB или {A, B}. В ориентированном графе порядок важен: A → B и B → A — разные рёбра.

Путь — это последовательность вершин, в которой каждая соседняя пара соединена ребром. Длиной пути обычно считают количество пройденных рёбер. Если путь начинается и заканчивается в одной вершине, он называется циклом. Например, A → B → C → A — цикл длины 3.

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

Отдельный частый случай — дерево. Это связный неориентированный граф без циклов. Если в дереве n вершин, то рёбер ровно n − 1. Такое свойство помогает быстро проверять ответы в заданиях.

Как представить граф

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

Матрица смежности — квадратная таблица n × n. В строке и столбце указаны вершины. В ячейке ставят 1, если ребро между соответствующими вершинами есть, и 0, если его нет. Для неориентированного графа такая матрица симметрична относительно главной диагонали.

Список смежности для каждой вершины перечисляет все вершины, с которыми она соединена. Он экономнее, если рёбер мало. Например, запись A: B, C означает, что из A можно перейти в B и C.

Представление	Плюс	Когда удобно
Рисунок	Наглядность	Объяснение условия
Матрица	Быстрая проверка ребра	Плотный граф
Список	Экономия памяти	Разреженный граф

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

Разобранный пример

Рассмотрим карту маршрутов между пунктами A, B, C и D. Дороги двусторонние: A соединён с B и C, B — с C и D, C — с D. Нужно определить степени вершин, проверить связность и записать матрицу смежности.

Степень A: 2, потому что A соединён с B и C.
Степень B: 3, потому что B соединён с A, C и D.
Степень C: 3, потому что C соединён с A, B и D.
Степень D: 2, потому что D соединён с B и C.
Из A можно попасть в D: A → B → D, значит граф связный.
Матрица в порядке A, B, C, D:
0 1 1 0
1 0 1 1
1 1 0 1
0 1 1 0

На диагонали стоят нули, потому что петель из вершины в саму себя нет. Матрица симметрична: если есть дорога A—B, то одновременно выполняются записи A, B и B, A. Сумма всех степеней равна 2 + 3 + 3 + 2 = 10. Она вдвое больше числа рёбер, поэтому рёбер 10 ÷ 2 = 5. Это полезная проверка: в неориентированном графе каждое ребро учитывается у двух вершин.

После разбора можно потренироваться в личном кабинете с бесплатными заданиями, чтобы закрепить переход от рисунка к таблице.

Типичные ошибки

Первая ошибка — путать вершину и ребро. Город является вершиной, а дорога между городами — ребром. Вторая — забывать направление. В графе A → B нельзя автоматически двигаться из B в A, если обратная стрелка не указана.

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

Ещё одна ловушка — смешивать длину пути и число вершин в нём. В пути A → B → C три вершины, но два ребра, поэтому его длина равна 2. Если в задаче есть веса, уточни, что требуется найти: количество рёбер или сумму их весов.

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

Что запомнить

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

Граф можно представить рисунком, матрицей смежности или списками смежности. Матрица удобна для быстрого ответа на вопрос «есть ли ребро?», список — для хранения большого разреженного графа. В неориентированном графе сумма степеней всех вершин равна удвоенному числу рёбер.

Следующий шаг простой: зарегистрируйся и реши 5 заданий бесплатно. Начни с определения вершин и рёбер, затем проверь степени и связность. Такой порядок превращает даже сложную схему в последовательную проверку.