Деревья свойства деревьев графы

Глава 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.

Источник

Теория графов

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

1. Для – графа следующие утверждения эквивалентны:
   1. – дерево;
   2. Любые две несовпадающие вершины графа соединяет единственная простая цепь;
   3. – связный граф, и любое ребро есть мост;
   4. – связный граф и древовидный;
   5. – ациклический граф (лес) и древовидный;
   6. – ациклический граф (лес) и субцикличекий;
   7. – связный, субциклический и неполный, ;
   8. – древовидный и субциклический, исключая и ;

(1->2): Если – дерево, то любые две его несовпадающие вершины соединяет единственная простая цепь. От противного. Пусть существуют две цепи (см. рис.). Тогда — простой цикл. (2->3): Если любые две несовпадающие вершины графа соединяет единственная простая цепь, то – связный граф, и любое ребро есть мост. Имеем: (число компонент связности). Далее от противного. Пусть ребро — не мост. Тогда в концы этого ребра связаны цепью. Само ребро в исходном графе – вторая цепь, что противоречит условию. (3->4): Если – связный граф, и любое ребро есть мост, то – связный и древовидный (). Индукция по (числу вершин). Если , то (число ребер). Пусть равенство выполняется для всех графов с числом вершин меньше . Докажем, что оно выполняется и для вершин. Удалим из ребро , являющееся мостом. Получим две компоненты связности и , для которых верно равенство . Т.е. , . Тогда . (4->5): Если – связный и древовидный (), то – ациклический граф (лес) и древовидный (). От противного. Пусть есть цикл с вершинами и ребрами. Остальные вершин связаны с этим циклом ребрами, т.к. граф связный. Следовательно, , что противоречит условию . Остальное без док-ва.

1. Ориентированные деревья

1. Ориентированным деревом (или ордеревом, или корневым деревом) называется орграф со следующими свойствами:
• существует единственный узел, в который не входит ни один другой узел. Он называется корнем ордерева;
• во все остальные узлы входит только по одному узлу;
• каждый узел достижим из корня.
1. Ордерево обладает следующими свойствами:

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

1. Концевая вершина ордерева называется листом. Путь из корня в лист называется ветвью. Длина наибольшей ветви ордерева называется высотой. Уровень узла ордерева – это расстояние отт корня до узла. Сам корень имеет уровень 0. Узлы одного уровня образуют ярус дерева.

Источник

Лекция 11

Дерево. Лес (ациклический граф). Остовный подграф. Остов. Взвешенный граф. Минимальный остов. Кодирование деревьев.

Базовые понятия и утверждения

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

Определение. Граф называется деревом, если он связный и в нем нет циклов.

Одноэлементный граф, т.е. граф, имеющий одну вершину и не имеющий ребер, также считается деревом.

Граф называется лесом (или ациклическим графом), если в нем нет циклов. Очевидно, что каждая компонента связности леса — дерево.

Пример 1. Граф (рис. 3.19) не является ни деревом, ни лесом. Граф (рис. 3.20) — дерево. Граф (рис. 3.21) — лес, состоящий из четырех деревьев.

Пример 2. Представьте диаграммами все (с точностью до изоморфизма) деревья с пятью вершинами.

◄ Имеется три различных (с точностью изоморфизма) дерева с пятью вершинами (рис. 3.22 — 3.24). ►

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

1) граф — дерево в том и только в том случае, когда в нем нет циклов и ;

2) граф — дерево в том и только в том случае, когда он связный и ;

3) граф — дерево в том и только в том случае, когда он связный, и каждое его ребро является мостом;

4) граф — дерево в том и только в том случае, когда любые две вершины графа можно соединить простой цепью, притом единственной;

5) граф — дерево в том и только в том случае, когда в нем нет циклов и добавление к нему нового ребра приводит к образованию единственного простого цикла.

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

2. Остовы графа. Подграф графа называется остовным подграфом, если множество его вершин совпадает с множеством вершин графа .

Остовом обыкновенного графа называется его остовный подграф, являющийся деревом.

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

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

.

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

Пример 3. Построим остов графа , диаграмма которого изображена на рис. 3.25. Удалим из графа ребро ; получим граф (рис. 3.26). Из графа удалим ребро ; получим граф (рис. 3.27). Из графа удалим ребро ; получим граф (рис. 3.28), который является одним из остовов графа .

Источник

Читайте также:  Виды породы дерева клен