§ 26. Графы. Деревья

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

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

Вершина обозначает объект, а ребро — связь между двумя вершинами. Если вершины представляют населённые пункты, ребро может обозначать дорогу между ними; если вершины — людей, ребро может показывать знакомство. Такое разделение помогает не смешивать сами объекты и отношения между ними.

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

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

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

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

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

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

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

Дерево соединяет все свои вершины, но не содержит лишних связей, которые замкнули бы цикл. Если у дерева n вершин, рёбер в нём n − 1: первое соединение присоединяет вторую вершину, а каждое последующее добавляет одну вершину к уже связанным. Поэтому для дерева достаточно проверить связность и отсутствие циклов; известное число рёбер служит дополнительной проверкой.

Сравнение графа и дерева

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

Разбор задач

Степени вершин

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

1. Для A подходят рёбра A–B и A–C, значит, её степень равна 2.
2. Для B подходят A–B и B–C, поэтому степень B равна 2.
3. Для C подходят A–C, B–C и C–D, значит, степень C равна 3.
4. Для D подходят C–D и D–E, поэтому степень D равна 2; к E подходит только D–E, значит, степень E равна 1.

Ответ. Степени A, B, C, D и E равны соответственно 2, 2, 3, 2 и 1. Проверка: сумма степеней равна 10, а каждое из пяти рёбер учитывается у двух своих концов, поэтому сумма должна быть вдвое больше числа рёбер.

Связность и цикл на схеме дорог

Условие. Населённые пункты A, B, C и D соединены дорогами A–B, B–C, C–A и C–D. Нужно определить, связен ли граф и есть ли в нём цикл. Указанные пары обозначают прямые дороги, а не любые маршруты между пунктами.

1. Начни с A: по дороге A–B можно попасть в B, а по A–C — в C.
2. Из C ведёт дорога C–D, значит, достижим и D; все четыре вершины связаны с A путями.
3. Проверь маршрут A–B–C–A: он проходит по рёбрам и возвращается в начальную вершину, поэтому образует цикл.

Ответ. Граф связен и содержит цикл A–B–C–A. Дорога C–D присоединяет D к остальным пунктам, но не нужна для замкнутого маршрута.

Проверка дерева по числу рёбер

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

1. Для шести вершин формула дерева даёт 6 − 1 = 5 рёбер, и число рёбер совпало.
2. Предположим, что в графе есть цикл. Одно ребро этого цикла можно убрать: оставшиеся рёбра цикла всё ещё соединят его вершины, поэтому граф останется связным.
3. После удаления останется пять вершин и четыре ребра. Но связный граф из шести вершин должен иметь не меньше пяти рёбер: чтобы присоединить каждую из пяти вершин к начальной, требуется как минимум пять связей. Получилось противоречие.

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

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

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

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

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

Формула n − 1 не заменяет проверку свойств дерева. Граф с таким числом рёбер может оказаться несвязным и содержать цикл в одной из частей. Сначала проверь связность и отсутствие циклов, а затем сравни число рёбер с n − 1 как дополнительный контроль.

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

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

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

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

• Вершины изображают объекты, рёбра — связи между ними.
• Степень вершины равна числу рёбер, которые к ней подходят.
• Связный граф позволяет добраться по рёбрам от любой вершины до любой другой.
• Цикл — замкнутый путь по рёбрам графа.
• Дерево — связный граф без циклов.
• В дереве с n вершинами n − 1 ребро.