Rivalry2

HTML Diff

0 added 0 removed

Original 2026-01-01

Modified 2026-02-26

1 <p>В этом уроке мы изучим еще один вид графов - древовидные. Именно этот вид графов активно используется в программировании - он связан с алгоритмами сортировки и поиска.</p>

2 <h2>Деревья</h2>

3 <p><strong>Деревья</strong>- это связные графы без циклов. Их часто применяют в математике и информатике. Вот так они выглядят:</p>

4 <p>Как видно из примера, у деревьев определенная древовидная ветвистость, откуда они и получили свое название.</p>

5 <p>Благодаря связности и отсутствию циклов у деревьев есть ряд свойств:</p>

6 <ul><li>В любом дереве есть ровно один путь из каждой вершины в каждую другую. Например, если есть два пути к вершине, то их можно объединить, чтобы получить цикл</li>

7 <li>У деревьев наименьшее количество ребер, которое только может быть у графа. При этом они остаются связными. Каждое ребро дерева - режущее, значит, не лежит в цикле</li>

8 <li>У деревьев наибольшее число ребер, которое может быть у графа без циклов. Добавление любого ребра к дереву создает ровно один цикл. Например, если добавить ребро между вершинами u и v, то получится цикл, включающий ребро uv и путь. Он гарантированно существует между u и v</li>

9 </ul><h2>Листья и индукция</h2>

10 <p>С древовидными графами работает механизм<strong>индукции</strong>- это значит, что по каждому дереву с n вершинами можно перемещаться с шагом n-1 ребро.</p>

11 <p>Для этого нам понадобится<strong>лист в дереве</strong>- вершина, которая находится на концах каждого дерева.</p>

12 <p>Разберем следующую теорему: у каждого дерева с хотя бы двумя вершинами есть хотя бы два листа. Докажем это утверждение.</p>

13 <p>Рассмотрим любой путь максимальной длины в дереве. Поскольку у дерева две вершины и оно связное, этот путь должен существовать. У обеих конечных точек этого пути степень 1 в дереве. Их единственные соседи - вершины, которые располагаются перед ними на пути.</p>

14 <p>Обсудим, почему это работает именно так:</p>

15 <ul><li>У конечных точек не может быть других соседей на пути, поскольку это создало бы цикл, что невозможно в дереве</li>

16 <li>У конечных точек не может быть других соседей вне пути, поскольку тогда мы могли бы использовать такого соседа для расширения пути. Только это невозможно, так как у пути уже максимальная длина</li>

17 </ul><p>Воспользуемся индукцией, чтобы доказать, что каждое дерево с n вершинами имеет n - 1 ребро.</p>

18 <p>Предположим, что все деревья на n вершинах содержат n - 1 ребро. Пусть T - дерево на n + 1 вершинах. У T есть лист v. У графа T - v n вершин. При этом он является деревом, потому что удаление вершины не может создать цикл, а удаление листа не может разорвать граф.</p>

19 <p>По гипотезе индукции T - v имеет n - 1 ребер. Чтобы получить T - v из T было удалено одно ребро, у T должно быть n ребер. Таким образом, результат индукции верен. Такую же технику можно использовать в доказательствах с участием других деревьев.</p>

20 <h2>Альтернативные определения деревьев</h2>

21 <p>Любое из свойств дерева используют, чтобы переформулировать определение дерева.</p>

22 <p>Для графа T эквивалентны следующие утверждения:</p>

23 <ol><li>T - дерево</li>

24 <li>Каждая пара вершин графа T соединена ровно одним путем</li>

25 <li>T связно, и удаление любого ребра разъединяет его</li>

26 <li>У T нет циклов, и добавление любого ребра создает цикл</li>

27 <li>T - связный граф с n вершинами и n-1 ребрами</li>

28 <li>T - ациклический граф с n вершинами и n-1 ребром</li>

29 </ol><p>Доказательство любой части этого определения включает аргументы, аналогичные тем, которые мы приводили выше. Существуют и другие способы комбинирования свойств деревьев для получения альтернативных характеристик деревьев.</p>

30 <h2>Леса</h2>

31 <p>Если мы уберем связность из определения дерева, то получим<strong>лес</strong>- граф, в котором нет циклов. Он состоит из нескольких компонентов - деревьев:</p>

32 <p>Деревья и леса - двучленные, то есть у них нет циклов.</p>

33 <h2>Выводы</h2>

34 <p>У деревьев много применений, особенно в информатике. В ней основное внимание уделяется деревьям с корнями. В таких деревьях одна вершина обозначается как корень, и от нее дерево растет наружу. При корнях нужно рассматривать вершины как родителей других вершин, как в семейном дереве.</p>

35 <p>Еще есть бинарные деревья, в которых у каждой вершины не более двух дочерних вершин. Бинарные деревья важны во многих алгоритмах информатики, таких как поиск, сортировка и разбор выражений.</p>