Приветствую! Продолжаем наш разговор о графах — удивительных объектах, которые рисуют связи между чем угодно: от друзей в соцсети до микросхем в вашем смартфоне.
Давайте освежим в памяти основные понятия (а заодно введем пару новых):
- Граф — это просто множество вершин (точек) и рёбер (линий), которые их соединяют. Представьте карту городов (вершины) и дорог (рёбра) между ними.
- Простой путь — это последовательность различных вершин и рёбер, где каждое ребро соединяет предыдущую вершину со следующей (вершина–ребро–вершина–ребро–...–ребро–вершина). Т.е. прогулка от одной вершины к другой без повторений. Вы не можете зайти в один и тот же город дважды и не можете дважды проехать по одной и той же дороге.
- Простой цикл — простой путь, в котором первая и последняя вершина совпадают.
- Связный граф — это граф, где из любого города можно добраться в любой другой, пусть даже с пересадками. Нет изолированных «островов».
А теперь — главный герой. Встречайте: Дерево!
Ключевое определение звучит элегантно и просто:
Дерево — это связный граф, в котором нет циклов.
Представьте себе схему родословной или иерархию файлов на компьютере — файловые системы Linux или Windows. Это и есть деревья. Никаких петель, только ветвление.
Часть 1: Теорема об эквивалентных определениях дерева
Оказывается, следующие три утверждения о графе T — это просто три разных способа сказать «это дерево». Они эквивалентны!
Теорема 1:
- Граф T дерево.
- Для любый двух вершин u, v существует единственный простой путь их связывающий.
- Граф T связный и Р = В - 1, где Р - количество ребер, В - количество вершин в графе.
Прежде чем доказывать основную теорему, докажем вспомогательные леммы.
Лемма 1.(Лемма о листе) В любом дереве есть вершина степени 1 - такие вершины называют листьями.
Доказательство:
Пусть в дереве нет ни одного листа, и из каждой вершины выходит не менее двух ребер.
Давайте отправимся на прогулку по этому графу: возьмем любую вершину, идем из нее по ребру в следующую и так далее. При заходе в новую вершину нам всегда будет куда выйти - нету листьев, а так как граф конечный, то при обходе мы когда-нибудь вернемся в начало. Получаем цикл. Противоречие.
Лемма 2. У любого связного графа есть связное поддерево содержащее все вершины исходного графа - остовное дерево или скелет.
Доказательство:
Наш граф связен, но в нем могут быть лишние ребра создающие циклы. Если нашли цикл в исходном графе - удаляем ребро. На связность это не влияет. В итоге придем к графу без циклов.
Доказательство Теоремы 1:
Эквивалентность (1) и (2) почти очевидна и доказывается от противного - если есть два пути соединяющих вершины, то найдется цикл.
Докажем, что (1) <=> (3).
(1) => (3)
Доказываем индукцией по числу вершин, что если граф T - дерево, то Р = В - 1.
Если В = 1, то вершина одна и граф просто точка - все верно.
Пусть верно для всех деревьев на n вершинах, доказываем для n+1.
По Лемме 1 в дереве найдется вершина степени 1, удалим ее, получим дерево, для него верна формула Р = В - 1, возвращаем ребро с вершиной. И формула доказана!
(3) => (2)
Применим Лемму 2 к исходному графу и получим остовное дерево. Но по доказанному ранее для него тоже верна формула Р = В - 1 ! Получается в процессе построения мы не удалили ни одного ребра и исходный граф был деревом.
Ч.т.д. Все три условия сошлись в одной точке, подтвердив удивительное единство разных свойств дерева. Кстати говоря, в процессе мы доказали еще одну:
Теорема 2(Дерево - минимально связный граф): Пусть граф Г связный, тогда Р ≥ В - 1 причем равенство достигается тогда и только тогда, когда Г - дерево.
Часть 2: Решим задачку
В некоторой стране 30 городов, причем каждый соединен с каждым дорогой. Какое наибольшее число дорог можно закрыть на ремонт так, чтобы из любого города можно было добраться в любой другой по дорогам?
Города это вершины графа на 30 вершинах.
Все вершины соединены ребрами - такие графы называются полными и обозначаются Kn, где n - число вершин.
Количество ребер в исходном графе n*(n-1)/2, где n = 30, формулу можно вывести из Леммы о рукопожатиях. Тогда число ребер Р_исх = 435
Количество ребер в остовном дереве Р_ост = 29.
Мы можем закрывать дороги, без потери связности, пока не дойдем до остова, поэтому ответ 435 - 29 = 406
Заключение
Сегодняшнее путешествие от определения к теореме — не просто академическое упражнение. Это фундамент для понимания:
- Поиск в ширину/глубину — работает именно на деревьях (и обобщается на графы через остовные деревья)
- Оптимальные сети — минимальные связные конструкции (деревья) экономят ресурсы
- Анализ данных — древовидные структуры (деревья решений, кластеризация) используют свойство уникальных путей
- Теория графов — теперь вы видите, как изящно связаны связность, циклы и подсчёт рёбер
Теорема о трёх эквивалентных определениях — не просто красивый факт, а инструмент мышления. Теперь, встречая дерево в любой области, вы сможете проверить:
«Есть ли здесь лишние связи? Можно ли упростить структуру, сохранив связность?»
Математика связывает абстракцию с реальностью — и деревья графов прекрасное тому доказательство.
👉 Подписаться на Telegram-канал
Задачи:
1. Если в дереве есть вершина степени r, то найдется по крайней мере r листьев.
2. Есть волейбольная сетка 5×10. Какое максимальное число веревок, её составляющих, можно разрезать так, чтобы она не распалась?
#теорияграфов #математика #леммаорукопожатиях #графы #математикапросто #этоинтересно #деревья