§ 24*. Графы

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

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

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

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

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

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

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

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

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

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

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

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

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

Разбор задач

Задача 1. Граф дружеских связей

Четыре ученика Аня, Боря, Вика и Глеб дружат парами: Аня с Борей, Аня с Викой, Боря с Глебом и Вика с Глебом. Требуется изобразить граф дружеских связей. Одну дружескую связь считаем неориентированной: по ней можно перейти от одного ученика к другому.

1. Изобразим четыре вершины и подпишем их именами учеников.
2. Соединим Аню с Борей и Викой, затем Борю с Глебом и Вику с Глебом.
3. Других рёбер не добавляем, потому что о других парах друзей в условии не сказано.

Ответ: граф имеет вершины Аня, Боря, Вика и Глеб и четыре ребра: Аня—Боря, Аня—Вика, Боря—Глеб, Вика—Глеб.

Задача 2. Степени вершин

В графе четыре вершины соединены пятью рёбрами. Нужно определить степени вершин и проверить подсчёт по числу рёбер. Для примера пусть рёбра имеют концы А—Б, А—В, А—Г, Б—В и В—Г.

1. У вершины А три ребра, поэтому её степень равна 3.
2. У Б два ребра, у В три ребра, у Г два ребра; степени равны соответственно 2, 3 и 2.
3. Складываем степени: 3 + 2 + 3 + 2 = 10.
4. Число рёбер равно 5, а 2 · 5 = 10, значит, проверка выполнена.

Ответ: степени вершин равны 3, 2, 3 и 2; их сумма равна 10, то есть удвоенному числу рёбер.

Задача 3. Дорога без повторения

Города А, Б, В и Г соединены дорогами А—Б, Б—В, В—Г, А—В и Б—Г. Можно ли проехать из А в Г, не проезжая повторно по одной дороге? Нужно использовать только дороги, указанные в условии.

1. Заменяем города вершинами, а дороги — рёбрами.
2. Ищем последовательность соединённых вершин: из А можно попасть в В, а из В — в Г.
3. Получаем маршрут А—В—Г; в нём две разные дороги, поэтому ни одна не повторяется.

Ответ: да, можно проехать по маршруту А—В—Г без повторного использования дороги.

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

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

Ошибка 2. Учитывать при степени только соседние вершины, а не рёбра. Два ребра могут вести к одному соседу и всё равно учитываются отдельно. Для проверки пересчитайте линии, имеющие конец в данной вершине.

Ошибка 3. Путать вершину и ребро: вершина — это объект или точка, ребро — связь между объектами. Ошибка появляется, когда называют линию городом или точку дорогой. Спросите себя: это элемент или соединение между элементами?

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

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

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

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

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

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