Дискретная математика (998286), страница 42
Текст из файла (страница 42)
Для иих выполняются многие свойства, которые ие всегда выполняются для графов в общем случае. Применительно к деревьям многие доказательства и рассуждеиия оказываются намного проще. Выдвигая какие-то гипотезы при решении задач теории графов, целесообразно сначала их проверять иа деревьях. а. Деревья являются самым распространенным классом графов, применяемых в программировании, причем в самых разных ситуациях. Более половины объема этой главы посвящено рассмотрению конкретных применений деревьев в программировании. 9.1.
Свободные деревья Изучение деревьев целесообразно начать с самых обших определений и устаио- влеиия основных свойств. 9.1.1. Определения Граф без циклов называется ациклическим, или лесом. Связный ациклический гРаф называется (свободны.м) деревом.
Таким образом, компонентами связности леса являются деревья. ЗАМЕЧАНИЕ Прилагательное «свободиое» употребляется в том случае, когда нужно подчеркнуть отличие деревьев от других объектов, родственных деревьям: ориентированных деревьев, упорядоченных деревьев и т. д. В связном графе С выполняется неравеиство д(С) ~ р(С) — 1, Граф С, в котоРом ч(С) = р(С) — Г, называется дрееавидньси.
235 9Л. Свободные деревья В ациклическом графе С з(С) = О. Пусть и, с — несмежные вершины графа С, х = (и, о) ф Е. Если граф С+ х имеет только один простой цикл, з(С+ х) = 1, то граф С называется субциклическим. Пример На рис. 9.1 показаны диаграммы всех различных (свободных) деревьев с 5 вершинами, а на рис, 9.2 — диаграммы всех различных (свободных) деревьев с б вершинами. Рис.
9.1. Свободные деревья с 5 вершинами Рис. 9.2. Свободные деревья с 6 вершинами 9.1.2. Основные свойства деревьев СледуюШая теорема устанавливает, что два из четырех свойств — связность, ацикличность, древовидность и субцикличносгь — характеризуют граф как дерево.
ТЕОРЕМА Пусть С()г, Е) — граф с р вершинами, 9 ребрами, (с компонентами связности и з простыми циклами. Пусть далее х — ребро, соединяющее любую пару несмежных вершин в С. Тогда следующие утверждения эквивалентны: 1. С вЂ” дерево, то есть связный граф без циклов, к(С) = 1йз(С) = О; 2.
любые две вершины соединены в С единственной простой цепью, Чщ ЯП (и,с); 3. С вЂ” связный граф, и любое ребро есть мост, Й(С) = 1 Й Ч е б Е /с(С вЂ” е) > 1; Глава 9. Деревья 4. С вЂ” связный и древовидный, й(С) = 1йй(С) = р(С) — 1; 5. С вЂ” ациклический и древовидный, х(С) = Ойд(С) = р(С) — 1; 6. С вЂ” ациклический и субциклический, (С) = Ой х(С+ х) = 1; 7. С вЂ” связный, субциклический и неполный, 1г(С) = 1ЙС ~ Крйр» )Зйз(С+х) = 1; 8, С вЂ” древовидный и субциклический (за двумя исключениями), я(С) = Р(С) — 1ЙС 1Кг О КзЙС Ф Кз ОКзйх(С+ х) = 1. Доказатвльство От противного. Пусть есть цикл с и вершинами и и ребрами. Остальные р — и вершин имеют инцидентные им ребра, которые связывают их с циклом.
Следовательно, д > р, что противоречит условию в = р — 1. Граф без циклов, следовательно, его компоненты — деревья. Пусть их Й Имеем: 4~5: ь ь ь д=~~ д;=~ (р; — 1) =~~ р,— к=р — к. 4=1 а=1 а=1 Но д = р — 1, следовательно, к = 1. По ранее доказанному 5 ~ 1 =ь 2. Имеем: Чи, и гП (и, в). Соединив две несмежные вершины, получим единственный простой цикл. При р > 3 граф Кр содержит цикл, следовательно, С ф К„.
Далее от противного. Пусть С несвязен, тогда при соединении ребром двух компонент связности цикл не возникнет. Имеем (г(С) = 1, следовательно, Чи, и 3 (и, в). Пусть цепь не единственная. Тогда сущесгвуег цикл 3, причем Я = Кз = Сз. Действительно, пусть Я > Сз, тогда, соединив две несмежные верщины этого цикла, полУчим два цикла.
Но С свЯзен и С ~ Кз, следовательно, существУ- ет другая вершина ш, смежная с Я = Кз (см. рис. 9.3 справа). Если гв От противного. Пусть существуют две цепи (и, в) (рис. 9.3 слева). Тогда и~и газ — простой цикл. Имеем: Чи, и 3! (и,в), следовательно, к(С) = 1. Далее от противного. Пусть ребро х — не мост. Тогда в С вЂ” х концы этого ребра связаны цепью. Само ребро х — вторая цепь.
Индукция по р. База; р = 1 =ь д = О. Пустыг(С) = р(С) — 1 для всех гра- фов С с числом вершин меньше р. Тогда удалим из С ребро х (которое является мостом). Получим две компоненты С' и С", удовлетворяющие индукционному предположению. Имеем: =р — 1 Ч =Р— 1, Я=Ч +Ч +1=р — 1+р — 1+1=р — 1. 9. т.
Свободные деревья смежна с более чем одной вершиной Я, то имеем больше одного цикла. Если тс смежна только с одной вершиной 2, то соединив ее с другой вершиной, получим два цикла. Рив. 9.3. Иллюстрации к доказательству теоремы о свойствах дврввьвв 7 =в 8: Имеем н(С) = 1, следовательно, С ф Кз ОКз, С ~ Кт ОКз. Имеем по доказанному: 7 =ю Я =ь 3 =ь 4, то встык = р — 1. 8 ~ 5: От противного. Пусть в С есть цикл л = С„. Если н > 3, то если внутри Я уже есть смежные вершины, имеем два цикла.
Если в Я нет смежных вершин, то, соединив несмежные вершины в л, получим два цикла. Следовательно, Я = Кз. Этот цикл а является компонентой связности С. Действительно, пусть это не так. Тогда существует вершина и, смежная с Я, Если те смежна более чем с одной вершиной Я, то имеем больше олного никла. Если и смежна только с одной вершиной Я, то, соединив ее с другой вершиной, получим два цикла. Рассмотрим С'. = С-Я. Имеем: р = р'+ 3, д = д'+ 3.
Но д = р — 1, следовательно, в' = р' — 1. Отсюда в(С') = О, так как один цикл уже есть. Следовательно, компоненты С' — деревья. Пусть их й. Имеем: ь ь ь 9 ~х д, - ~х (р, - 1) - ~х р, - й р - й, тьп т=т в т но д' = р' — 1, следовательно, й = 1, то есть дерево одно. Если в атом дереве соединить несмежные вершины, то получим второй цикл. Два исключения: деревья, которые не имеют несмежных вершин, — зто Кт и К2. Общая схема доказательства представлена на рис. 9.4. Граф доказательства сильно связен, следовательно, теорема доказана.
С3 СЛЕДСТВИЕ В любам нетривиальном дереве имеются но крайней мере две висячие вершины. Доказатвльство Рассмотрим дерево С(Ъ", Е). Дерево — связный граф, следовательно, Чв, Е 1' в(вт) > 1. Глава 9. Деревья Вычисление От противного Рис. 9.4. Схема доказательства теоремы о свойствах деревьев Далее от противного. Пусть т'гв Е 1..р — 1 Н(о) > 1. Тогда 29= 'т И(ст) >2(р — 1)+1= 2р — 1.
Но д = р — 1, то есть 2д = 2р — 2. Имеем противоречие: 2р — 2 > 2р — 1. 9.2. Ориентированные, упорядоченные и бинарные деревья Ориентированные (упорядоченные) деревья являются абстракцией иерархических отношений, которые очень часто встречаются как в практической жизни, так и в математике и в программировании. Дерева (ориентированное) и иерархия — это равнообъемные понятия.
9.2.1. Ориентированные деревья Ориентированным деревом (или ордеревам, или корневым деревом) называется орграф со следующими свойствами: 1. существует единственный узел, полустепень захода которого равна О. Он на- зывается корнем ордерева; 2. полустепень захода всех остальных узлов равна 1; 3.
каждый узел достижим из корня. 239 9.2. Ориентированные, упорядоченные и бинарные деревья Пример На рис. 9.5 приведены диаграммы всех различных ориентированных деревьев с 3 узлами, а на рис. 9.6 показаны диаграммы всех различных ориентированных деревьев с 4 узлами. Рис. 9.$. Ориентированные деревья с 3 узлами Рис. 9.6. Ориентированные деревья с 4 узлами ТЕОРЕМА Ордерево обладает следующими свойствами: 1. д=р — 1; 2.' если в ордеревв отменить ориентацию ребер, то получится свободное дерево; 3. в ордервве нет контуров; 4. для каждого узла сущвспгвует вдинспювнный путь, ведущий в этот узел из корня; 5. подграф, определяемый множеством узлов, достижимых из узла с, является ордерввом с корнем с (это ордерево называется поддеревом узла с); 6. если в свободном дереве любую вертану назначить корнем, то получится ор- дерево.
ДОКАЗАТЕЛЬСТВО 1. Каждое ребро входит в какой-то узел. Из п. 3 определения 9.2.1 имеем; Угс Е Ут,(и) й~(о) = 1, следовател но, д = р — 1. 2. Пусть С вЂ” рдерево, граф С' получен из С отменой ориентации ребер, и— корень. ТогдаУгстиг и У Э(ст,и) н С' 4гЗ(и,сз) н С', следовательно, Уст,сз 3(ст,сз) и граф т ' связен. Таким образом, у1итывая п. 4.
теоремы 9.1.2, С' — дерево. 240 Глава 9, деревья 3. Следует из 2. 1. От противного. Если бы в С существовали два пути из и в о, то в С' имелся бы цикл. х Пусть ф— правильный подграф, определяемый множеством узлов, достижимых нз о. Тогда йо+ (и) = О, иначе узел е был бы достижим из какого-то узла о' е С, и, таким образом, в С„, а значит, и в С имелся бы контур, что противоречит 3.
Далее имеем; т'и' ~ С„~(и) о+(и') = 1, так как С„с С. Все вершины С„ достижимы из и по построению. По определению 9.2.1 получаем, что ф— ордерево. 6. Пусть вершина и назначена корнем и дуги последовательно ориентированы «от корня» обходом в глубину.
Тогда о+(и) = О по построению; Уи е Ъ"\(и) о+(о) = 1, так как входящая дуга появляется цри первом посещении узла; все узлы достижимы из корня, так как обход в глубину посещает все вершины связного графа. Таким образом, по определению 9.2.1 получаем ордерево. П ЗАМЕЧАНИЕ Каждое свободное дерево определяет ве более р ориентированных деревьев. Таким образом, общее число различных ордеревьев с р узлами ве более чем в р раз превосходит общее число различных свободных деревьев с р вершинами. Концевая вершина ордерева называется листом.
Путь из корня в лист называется ветвью. Длина наибольшей ветви ордерева называется высотой. Уровень узла ордерева — зто расстояние от корня до узла Сам корень имеет уровень О. Узлы одного уровня образуют ярус дерева. ЗАМЕЧАНИЕ Нарялу с ~растительной» применяется еще и «генеалогическая» терминология. Узлы, достижимые из узла и, называются потомками узла и (потомки образуют поддерево). Если в дереве существует дуга (и,е), то узел и называется отцом (или родителем) узла т а узел е называется сыном узла и.
Сыновья одного узла называются братьями. 9.2.2. Эквивалентное определение ордерева Ордерево Т вЂ” зто конечное множество узлов, таких что: 1. имеется один узел г, называемый корнем данного дерева," 2. остальные узлы (исключая корень) содержатся в к попарно непересекающихся множествах Ты..., Ты каждое из которых является ордеревом (к > О). т = ((г),т,,...,Ть). 241 9дь Ориентированные, упорядоченные и бинарные деревья 9.2.3. Упорядоченные деревья Множества Т„..., Ть в зкивалентном определении ардерева являются поддеревьями.
Если относительный порядок поддеревьев Ты...,Ть фиксирован, та ордерево называется упорядоченным. Пример Ориентированные и упорядоченные ориентированные деревья интенсивна используются в программировании. 1. Выражения. Для представления выражений языков программирования, как правило, используются ориентированные упорядоченные деревья.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
