Новиков Ф.А. Дискретная математика для программистов (860615), страница 55
Текст из файла (страница 55)
G — дерево, то есть связный граф без циклов,k(G) = 1 k z{G)= 0.294Глава8.Связность2. Любые две вершины соединены в G единственной простой цепью,Vu,v(|P(II,v)| =l).3. G — связный граф, и любое ребро есть мост,k{G) = \kMe£E{k(G - е) > 1).4. G — связный и древочисленный,k{G) =lkq(G)=p(G)-l.5. G — ациклический и древочисленный,z{G)=Okq(G)=p{G)-l.6. G — ациклический и субциклический,z{G) = 0b z(G + x) = l.7.
G — связный, субциклический и неполный,k{G) = 1 к G ф Кр к р > 3 к z{G + х) = 1.8. G — древочисленный и субциклический (за двумя исключениями),q(G) = p(G) - 1 к G ф Кг U К3 к G ф К2 U К3 к z{G + х) = 1.ДОКАЗАТЕЛЬСТВО[ 1=>2 ] От противного. Пусть существуют две цепи (и, v). Некоторые вершиныэтих цепей различны. Обозначим через w\ первую вершину при перечислениивершин от и к v, такую, что следующие вершины в цепях различны, а черезw2 обозначим первую вершину при перечислении вершин от г; к и, такую, чтоследующие вершины в цепях различны (рис. 9.3, слева). Рассмотрим отрезок(гух, W2) первой цепи при перечислении вершин от и к v и отрезок (w2,wi) второйцепи при перечислении вершин от г; к и.
Тогда (vji,W2) + {w2,wi) — цикл, чтопротиворечит ацикличности графа G.и •• VИ»Рис. 9.3. К доказательству теоремы о свойствах деревьев[ 2=>3 ] Любые две вершины соединены цепью (единственной), следовательно,k(G) = 1. Далее от противного. Пусть ребро х — не мост. Тогда в G — х концыэтого ребра связаны цепыо. Само ребро х — вторая цепь.2959.1. Свободные деревья[ 3=>4 ] Индукция по р. База: р = 1q = 0. Пусть q(G) = p(G) - 1 длявсех связных графов G с числом вершин меньше р, у которых любое ребро является мостом. Тогда удалим из графа G некоторое ребро х (которое являетсямостом). Получим две компоненты G' и G", удовлетворяющие индукционномупредположению. Имеем:q1 = р' - 1, q" = р" - 1,q=+ q" + 1 = р> - 1 +р"- 1+ 1 =р-1.[ 4 = ^ 5 ] От противного. Пусть есть цикл с п вершинами и п рёбрами.
Остальныер - п вершин имеют инцидентные им рёбра, которые связывают их с циклом.Следовательно, q ^ р, что противоречит условию q = р- 1.[ 5 = ^ 1 ] Граф без циклов, следовательно, его компоненты — деревья. Пусть их к.Имеем:ккqi = Yl(piq=г=1г= 1~=Pi — к = р — к.г=1Но q = р - 1, следовательно, к = 1.[ 5=>6 ] По ранее доказанному 51 =*• 2, то есть любые две несмежные вершины соединены единственной простой цепью. Соединив две несмежныевершины ребром, получим единственный простой цикл.[ 6 = ^ 7 ] При р ^ 3 граф Кр содержит цикл, следовательно, G ф- Кр.
Далее отпротивного. Пусть G несвязен, тогда при соединении ребром двух компонентсвязности цикл не возникнет.[ 7 = ^ 2 ] Имеем k(G) = 1, зиачит любые две несмежные вершины соединеныпростой цепыо. Пусть цепь пе единственная. Тогда существует цикл Z, причёмZ = К3 = Сз. Действительно, пусть Z > Сз, тогда, соединив две несмежныевершины этого цикла, получим два цикла. Но G связей и G Фследовательно,существует другая вершина w, смежная с Z = Кц (см. рис. 9.3, справа). Если wсмежна более чем с одной вершиной Z, то имеем больше одного цикла. Если wсмежна только с одной вершиной Z, то, соединив её с другой вершиной, получимдва цикла.[ 7=>8 ] Имеем k(G) = 1, следовательно, G Ф К2 U К3, G Ф Кi U Кз.
Имеем подоказанному: 7 =>• 234, то есть q = р- 1.[ 8 = ^ 5 ] От противного. Пусть в G есть цикл Z = Сп. Если п > 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' —деревья. Пусть их к. Имеем:q' =qi =г= 1- 1) = ^Ргг=1г=1- к = р' - к,296Глава8.Связностьно q' =р' — 1, следовательно, к = 1, то есть дерево одно.
Если в этом дереве соединить несмежные вершины, то получим второй цикл. Два исключения: деревья,которые пе имеют несмежных вершин, — это К\ и К2. Общая схема доказательства представлена на рис. 9.4. Граф доказательства сильно связей, следовательно,теорема доказана.•ВычислениеОт противногоРис. 9.4. Схема доказательства теоремы о свойствах деревьевСЛЕДСТВИЕ1В любом нетривиальном дереве имеются по крайней мере две ви-сячие вершины.Рассмотрим дерево G(V,E). Дерево — связный граф, следовательно, Mvi G V (d(vi) ^ 1). Далее от противного. Пусть Vi £ 1 ..р- 1 (d(vi) > 1).Тогдаv2q =d{vi) >2{p-\)+ l = 2p-l.1Ho q = p — 1, то есть 2q = 2p — 2. Имеем противоречие: 2p — 2 > 2p — 1.•ДОКАЗАТЕЛЬСТВОЗАМЕЧАНИЕЛегко видеть, в частности, что висячими вершинами в дереве являются концы любогодиаметра.СЛЕДСТВИЕсочленения.2Каждая не висячая вершина свободного дерева является точкой9.2.
Ориентированные, упорядоченные и бинарные деревья297Пусть G(V,E) — дерево, v е V и d(v) > 1. Тогда, по определению, 3u,w е V (и ф w &; (и, v) G Е &; (v,w) е Е). Граф G связен, поэтомусуществует цепь (u,w). Если v g (u,w), то имеем цикл v, ( u , w ) , v , что противоречит тому, что G — дерево. Следовательно, 3u,w Е V (V (u,w) (v € (u,w))), ипо теореме 8.1.2 вершина v — точка сочленения.•ДОКАЗАТЕЛЬСТВОСЛЕДСТВИЕ 3Если в связном графе нет висячих вершин, то в нём есть цикл.О Т противного. Если связный граф пе имеет циклов, то онявляется деревом, и по следствию 1 обязан иметь висячие вершины.•ДОКАЗАТЕЛЬСТВО9.1.3. Центр дереваСвободные деревья выделяются из других графов тем, что их центр всегда оправдывает своё название.Центр свободного дерева состоит из одной вершины или из двух смежных вершин:ТЕОРЕМА(.z{G) = 0 & k{G) = 1)(C(G) = Ki V C{G) =K2).деревьев Ki и К2 утверждение теоремы очевидно.
Пустьтеперь G(V, Е) — некоторое свободное дерево, отличное от Ki и К2. Рассмотримграф G'(V', Е'), полученный из G удалением всех висячих вершин. Заметим, чтоG' — дерево, поскольку ацикличность и связность при удалении висячих вершинсохраняется. Далее, если эксцентриситет ec(v) = d(v,u), то и — висячая вершинав дереве G (иначе можно было бы продолжить цепь «за» вершину и). Поэтому\/г> б V' ( e c ( v ) = ес('о) + 1), и при удалении висячих вершин эксцентриситетыоставшихся уменьшаются на 1.
Следовательно, при удалении висячих вершинцентр пе меняется, C(G) = C(G'). Поскольку дерево G конечно, то, удаляя накаждом шаге все висячие вершины, в конце концов за несколько шагов придёмк К1 или К2.•ДОКАЗАТЕЛЬСТВОДЛЯ9.2. Ориентированные, упорядоченныеи бинарные деревьяОриентированные (упорядоченные) деревья являются абстракцией иерархических отношений, которые очень часто встречаются как в практической жизни, таки в математике и программировании. Дерево (ориентированное) и иерархия —это равиообъёмиые понятия.9.2.1.
Ориентированные деревьяОриентированным деревом (или ордеревом, или корневым деревом) называетсяорграф со следующими свойствами:1. Существует единственный узел г, полустепепь захода которого равна 0, d+(r) == 0. On называется корнем ордерева.2. Полустепепь захода всех остальных узлов равна 1, Vi> е V - г ( d + ( v ) = 1).3. Каждый узел достижим из корпя, У v е V - г (3(г7г;)).298Глава8.СвязностьПример На рис. 9.5 приведены диаграммы всех различных ориентированныхдеревьев с 3 узлами, а на рис.
9.6 показаны диаграммы всех различных ориентированных деревьев с 4 узлами.ТЕОРЕМАОрдерево обладает следующими свойствами:1.2.3.4.q = p- 1.Если в ордереве забыть ориентацию дуг, то получится свободное дерево.В ордереве нет контуров.Для каждого узла существует единственный путь, ведущий в этот узел из корня.5. Подграф, определяемый множеством узлов, достижимых из узла v, является ордеревом с корнем v (это ордерево называется поддеревом узла v).6. Если в свободном дереве любую вершину назначить корнем, то получится ордерево.Рис.
9.5. Ориентированные деревья с 3 узламиРис. 9.6. Ориентированные деревья с 4 узламиДОКАЗАТЕЛЬСТВО[ 1 ] Каждая дуга входит в какой-то узел. Из п. 2 определения 9.2.1 имеем:Vi> £ V — г (d + (v) = 1), где г — корень. Следовательно, q = р — 1.[ 2 ] Пусть G — ордерево, граф G' получен из G забыванием ориентации рёбер, г — корень. Тогда Vvi,v2 £ V (3{vi,r) £ G' & 3(r, v2) £ G'), следовательно,Vv\,v 2 (3(i>i, V2)) и граф G' связен. Таким образом, учитывая п. 4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
