§ 51. Простейшие свойства графов

Определения и обозначения

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

Вершина и ребро — основные элементы графа: вершины изображают объекты, а рёбра показывают связи между ними. Обычно вершины рисуют точками или кружками, а рёбра — линиями между ними. Разделение на объекты и связи помогает не путать сами элементы системы с отношениями между ними.

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

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

Как это устроено

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

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

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

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

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

Основные элементы и свойства графа

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

Разбор задач

Задача 1. Неориентированный граф задан вершинами A, B, C, D и рёбрами AB, AC, BC, CD. Определить число вершин и рёбер, а также степени всех вершин. Список рёбер удобен тем, что каждая связь записана ровно один раз. При подсчёте степени нужно учитывать, входит ли вершина в каждое ребро.

1. Пересчитаем названия вершин: A, B, C, D. Значит, вершин четыре.
2. Пересчитаем рёбра AB, AC, BC, CD. Их четыре, так как в списке каждая пара обозначает одно ребро.
3. Для A подходят AB и AC, поэтому deg(A) = 2. Для B подходят AB и BC, поэтому deg(B) = 2.
4. Для C подходят AC, BC и CD, поэтому deg(C) = 3. Для D подходит только CD, поэтому deg(D) = 1.
5. Проверим ответ: 2 + 2 + 3 + 1 = 8, а 2m = 2 · 4 = 8. Равенство подтверждает подсчёт степеней.

Ответ: 4 вершины, 4 ребра; степени A, B, C, D равны соответственно 2, 2, 3, 1.

Задача 2. В неориентированном графе вершины A, B, C, D соединены рёбрами AB, BC и CD. Проверить, существует ли путь из A в D, и выяснить, связен ли граф. Недостаточно увидеть только первое и последнее ребро: нужно проверить переходы между ними. Для связности проверяют достижимость не одной выбранной пары, а всех вершин.

1. Начинаем в A и по ребру AB переходим в B.
2. Из B по ребру BC переходим в C, а затем по CD — в D. Получилась последовательность A–B–C–D, значит, путь из A в D есть.
3. При этом из A достижимы также B и C, а D достигнута последним переходом. Все четыре вершины отмечены.
4. Поскольку из A достижимы все вершины, между любой парой вершин есть путь: путь между двумя из них можно составить через A, если потребуется. Следовательно, граф связен.

Ответ: путь A–B–C–D существует; граф связен.

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

1. Складываем степени: 3 + 3 + 1 + 1 = 8. Значит, предполагаемое число рёбер равно 8 ÷ 2 = 4.
2. Проверим возможность таких степеней в простом графе с четырьмя вершинами. Вершина степени 3 должна соединяться со всеми остальными вершинами.
3. Две вершины степени 3 должны обе соединяться с каждой из двух оставшихся. Тогда у каждой из последних вершин уже есть как минимум две связи.
4. Это противоречит указанной для них степени 1. Следовательно, такой набор степеней не может соответствовать простому графу, хотя сумма степеней чётная.

Ответ: по формуле получилось бы 4 ребра, но простой граф с такими степенями невозможен.

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

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

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

Если найден путь между A и D, это ещё не доказывает связность всего графа: отдельная вершина может оставаться недостижимой. Эту ошибку допускают, когда проверяют только пару из условия и забывают об остальных вершинах. Начните обход с одной вершины и отметьте каждую достигнутую; связность подтверждается лишь тогда, когда отмечены все.

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

Связь с другими темами

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

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

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

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