Деревья свойства деревьев перечисление деревьев

LK / Лекция 11

Баранов Виктор Павлович. Дискретная математика. Раздел 3. Графы, сети, коды.

Лекция 11. Деревья и их свойства. Задача поиска кратчайшего остова

Лекция 11. ДЕРЕВЬЯ И ИХ СВОЙСТВА. ЗАДАЧА ПОИСКА КРАТЧАЙШЕГО ОСТОВА

1. Введение.
2. Определение дерева и его свойства.
3. Задача поиска кратчайшего остова.

1. Введение

Одним из наиболее важных понятий, которое часто используется в различных приложениях теории графов, является дерево. С помощью деревьев легко описывается структура самых различных объектов: организаций и учреждений, книг и документов, математических формул, химических соединений, компьютерных файловых систем, программ и многое другое. Принято считать, что первым использовал понятие дерева Кирхгофф в 1847 г. при исследовании электрических цепей. Спустя десять лет химик Кэли ввел термин «дерево» при изучении структуры углеводородных соединений и получил первые важные результаты в этом разделе теории графов.

1. Определение дерева и его свойства

Граф без циклов называется ациклическим или лесом. Связный ациклический граф называется деревом. Если – лес, то каждая его компонента является деревом. Листом называют вершину, степень которой равна 1, если она не рассматривается как корень. В качестве корня в неориентированном дереве можно принять любую вершину. Существует несколько эквивалентных определений неориентированного дерева, каждое из которых отражает различные свойства последнего. Приведем некоторые из них. Теорема. Следующие определения дерева эквивалентны:

1. дерево – это связный граф без циклов;
2. дерево – это связный граф, в котором каждое ребро является мостом;
3. дерево – это связный граф, цикломатическое число которого равно нулю;
4. дерево – это граф, в котором для любых двух вершин существует ровно одна соединяющая их цепь.

Эти утверждения выводятся одно из другого по схеме 1)2) 3) 4) 5). Из свойства 3) имеем: или , то есть в любом дереве число ребер на единицу меньше числа вершин. Рассмотрим связный граф и будем из него удалять по одному цикловые ребра до получения ациклического подграфа. В результате получим остовное дерево графа , для которого , . Так как удаление цикловых ребер можно вести разными способами, то один и тот же граф в общем случае имеет несколько остовных деревьев. На рис. 1. представлен граф и три его остовных дерева.                                     Рис. 1. Граф и его остовные деревья , и Ребра графа , не вошедшие в его остовное дерево , называются хордами дерева . Лемма. В графе для любого остовного дерева и любой хорды этого дерева существует единственный цикл, содержащий хорду и не содержащий других хорд. Доказательство. Пусть . В дереве имеется единственная цепь, соединяющая вершины и . Присоединяя к этой цепи ребро , получим требуемый цикл.

1. Задача поиска кратчайшего остова

Задача поиска кратчайшего остова состоит в следующем: для нагруженного графа требуется построить остовное дерево , сумма длин ребер которого минимальна. Этой задаче можно дать такую интерпретацию: пунктов на местности нужно связать сетью дорог, трубопроводов или линий телефонной связи. Для каждой пары пунктов и задана стоимость их соединения , которая представляет длину ребра . Требуется построить связывающую сеть минимальной стоимости, которую называют кратчайшей связывающей сетью. Очевидно, что эта сеть будет остовным деревом графа , при этом среди всех остовных деревьев она будет иметь минимальную сумму длин входящих в нее ребер. Алгоритм построения кратчайшей связывающей сети состоит из шагов, на каждом из которых присоединяется одно ребро. Правило для выбора этого ребра следующее: среди еще не выбранных ребер берется самое короткое, не образующее цикла с уже выбранными ребрами. Пример. Дана матрица расстояний , в которой элемент – вес ребра, который указывает в условных единицах затраты, необходимые для того, чтобы связать пункт с пунктом . Требуется с наименьшими затратами связать все пункты друг с другом. Применение сформулированного выше алгоритма выглядит следующим образом. В матрице отыскивается минимальный элемент, который вычеркивается, а соответствующее ему ребро заносится в сеть, если при этом не образуется цикл. Затем эти действия повторяются. Таким образом, на первых пяти шагах работы алгоритма будут выбраны ребра , , , , . Из оставшихся ребер минимальную длину имеет ребро , но в сеть оно не включается, так как образует цикл с уже выбранными ребрами. На следующих этапах алгоритма в сеть будут включены ребра , и . Для обоснования алгоритма предположим, что дерево , которое он строит, состоит из ребер , для которых . Рассмотрим любое другое дерево и упорядочим его ребра по возрастанию длин. Пусть первые ребер дерева такие же, как в дереве , а -е ребро отличается от (). Присоединим к дереву ребро . Тогда возникнет цикл, в который входит ребро и какие-то ребра из дерева . Среди этих ребер обязательно найдется ребро , длина которого не меньше, чем длина ребра : иначе ребро образовало бы цикл с ребрами меньшей длины, что исключается правилом выбора очередного ребра в рассмотренном алгоритме. Удалим из дерева ребро , заменив его ребром . В результате получим дерево, длина которого не больше, чем длина дерева . Аналогичным путем вводим в дерево ребра , при этом всякий раз длина дерева не увеличится. Это означает, что дерево действительно кратчайшее. 2

Источник

Глава 9 Деревья

Деревья заслуживают отдельного и подробного рассмотрения по двум причинам.

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

9.1. Свободные деревья

9.1.1. Определения

Граф без циклов называется ациклическим, или лесом. Связный ациклический граф называется (свободным) деревом. Таким образом, компонентами связности леса являются деревья. ЗАМЕЧАНИЕ Прилагательное «свободное» употребляется в том случае, когда нужно подчеркнуть от­личие деревьев от других объектов, родственных деревьям: ориентированных деревьев, упорядоченных деревьев и т. д. В связном графе G выполняется неравенство q(G)  p(G) — 1. Граф G, в котором q(G)=p(G)-1, называется древовидным. В ациклическом графе G z(G) = 0. Пусть u, v — несмежные вершины графа G, х = (u, v)  Е. Если граф G + х имеет только один простой цикл, z(G + х) = 1, то граф G называется субциклическим. Пример На рис. 9.1 показаны диаграммы всех различных (свободных) деревьев с 5 вер­шинами, а на рис. 9.2 — диаграммы всех различных (свободных) деревьев с 6 вершинами Рис. 9.1. Свободные деревья с 5 вершинами Рис. 9.2. Свободные деревья с 6 вершинами

9.1 .2. Основные свойства деревьев

Следующая теорема устанавливает, что два из четырех свойств — связность, аци­кличность, древовидность и субцикличность — характеризуют граф как дерево. ТЕОРЕМА Пусть G(V, Е) — граф с р вершинами, q ребрами, k компонентами связности и z простыми циклами. Пусть далее х — ребро, соединяющее любую пару несмежных вершин в G. Тогда следующие утверждения эквивалентны: 1. G — дерево, то есть связный граф без циклов, k(G)=1&z(G)=0; 2. любые две вершины соединены в G единственной простой цепью, u, v  ! ; 3. G — связный граф, и любое ребро есть мост, k(G) = l&eЕ k(G – е) > 1;. 4. G — связный и древовидный, k(G) = l&q(G)=p(G)-l; 5. G — ациклический и древовидный, z(G) = 0&q(G)=p(G)-l; 6. G — ациклический и субциклический, z(G) =0&z(G + x) = 1; 7. G — связный, субциклический и неполный, k(G) = l&GK_p&p3&z(G + x) = 1; 8. G — древовидный и субциклический (за двумя исключениями), q(G)=p(G)-l&GK₁K₃&GK₂K₃&z(G + x) = l. доказательство [1 2.] От противного. Пусть существуют две цепи (рис. 9.3 слева). Тогда w₁, w₂ — простой цикл. Рис. 9.3. К доказательству теоремы о свойствах деревьев [2 3.] Имеем: u,v ! , следовательно, k(G) = 1. Далее от противного. Пусть ребро х — не мост. Тогда в G — х концы этого ребра связаны цепью. Само ребро х — вторая цепь. [3 4.] Индукция по p. База: р=1  q = 0. Пусть q(G) = p(G) —1 для всех графов G с числом вершин меньше р, у которых любое ребро суть мост. Тогда удалим из G ребро х (которое является мостом). Получим две компоненты G’ и G», удовлетворяющие индукционному предположению. Имеем: q’ = р’ — 1, q» = р» — 1, q = q’ + q» + 1 = р’ — 1 + р» — 1 + 1 = р — 1. [4 5.] От противного. Пусть есть цикл с n вершинами и n ребрами. Остальные р — n вершин имеют инцидентные им ребра, которые связывают их с циклом. Следовательно, q  р, что противоречит условию q = р — 1. [51.] Граф без циклов, следовательно, его компоненты — деревья. Пусть их k. Имеем: Ho q = p — 1, следовательно, k = 1. [56.] По ранее доказанному 5  1 2. Имеем: u,v ! . Соединив две несмежные вершины, получим единственный простой цикл. [67.] При р  3 граф К_р содержит цикл, следовательно, G  К_р. Далее от противного. Пусть G несвязен, тогда при соединении ребром двух ком­понент связности цикл не возникнет. [72.] Имеем k(G) = 1, следовательно, u,v  . Пусть цепь не единственная. Тогда существует цикл Z, причем Z = К₃ = C₃. Действительно, пусть Z > Сз, тогда, соединив две несмежные вершины этого цикла, получим два цикла. Но G связен и G  K₃, следовательно, существу­ет другая вершина w, смежная с Z = К₃ (см. рис. 9.3 справа). Если w смежна с более чем одной вершиной Z, то имеем больше одного цикла. Если w смежна только с одной вершиной Z, то соединив ее с другой вершиной, получим два цикла. [78.] Имеем k(G) = 1, следовательно, G  К₂  K₃, G  K₁  K₃. Имеем по доказанному: 723 4, то есть q = р — 1. [85.] От противного. Пусть в G есть цикл Z = С_n. Если n > 3, то если внутри Z уже есть смежные вершины, имеем два цикла. Если в Z нет смежных вершин, то, соединив несмежные вершины в Z, получим два цикла. Сле­довательно, Z = К₃. Этот цикл Z является компонентой связности G. Действительно, пусть это не так. Тогда существует вершина w, смежная с Z. Если w смежна более чем с одной вершиной Z, то имеем больше одного цикла. Если w смежна только с одной вершиной Z, то, соеди­нив ее с другой вершиной, получим два цикла. Рассмотрим G’: = G — Z. Имеем: р = р’ + 3, q = q’ + 3. Но q = р — 1, следовательно, q’ = р’ — 1. От­сюда z(G’) = 0, так как один цикл уже есть. Следовательно, компоненты G’ — деревья. Пусть их fc. Имеем: но q’ = p’ — 1, следовательно, k = 1, то есть дерево одно. Если в этом дереве соединить несмежные вершины, то получим второй цикл. Два исключения: деревья, которые не имеют несмежных вершин, — это К₁ и К₂. Общая схема доказательства представлена на рис. 9.4. Граф доказательства силь­но связен, следовательно, теорема доказана. Рис. 9.4. Схема доказательства теоремы о свойствах деревьев СЛЕДСТВИЕ В любом нетривиальном дереве имеются по крайней мере две ви­сячие вершины. доказательство Рассмотрим дерево G(V,E). Дерево — связный граф, следовательно, v_iV d(v_i)1. Далее от противного. Пусть i l..p — l d(v_i) > 1. Тогда . Но q = р — 1, то есть 2q = 2р — 2. Имеем противоречие: 2р — 2 > 2р — 1.

Источник