Спец часть (часть 1) (3 поток) (2015) (by Кибитова) (Ответы на спец часть), страница 7

Отсюда следует, что G — связный граф. Теорема доказана.5). Отсюда следует, что G — связный граф. Теорема доказана.§17. Корневые деревья. Верхняя оценка их числа.§17.КорневыеКорневыедеревья.деревья.ВерхняяВерхняяоценкаоценкаихихчисла.числа.§17.Определение 1. Любое дерево, в котором выделена одна вершина, называемая корнем,ОпределениеЛюбоедерево,дерево,ввкоторомкоторомвыделенавыделенаоднаоднавершина,вершина,называемаяназываемаякорнем,корнем,называетсякорневымОпределение1.1.деревом.Любоеназываетсякорневымдеревом.Определение2. деревом.1) Граф, состоящий из одной вершины, которая выделена, называетсяназываетсякорневымОпределение2.Граф,состоящийсостоящийизизоднойоднойвершины,вершины,котораякотораявыделена,выделена,называетсяназываетсякорневымдеревом.Определение 2. 1)1)Граф,корневымдеревом.2) Пустьимеются корневые деревья D1, D2, …, Dm с корнями v1, v2, …, vm, Di = (Vi, Ei),корневымдеревом.2)Пустьимеютсякорневыедеревьякорнями, …,v v,mD, D=i =(V(V2, …, Dmс скорнямиi, Ei),ПустьимеютсяDD1,1,DDv1v,1v, 2v, 2…,Vi ∩ V2)=∅(i≠j).Тогда корневыеграфD = деревья(V,E), полученныйследующимобразом:2, …, Dmmii, Ei),jV∩V=∅(i≠j).ТогдаграфD=(V,E),полученныйследующимобразом:Vi i∩ Vj j= ∅ (i ≠ j).

Тогда граф D = (V, E), полученный следующим образом:V = V1 ∪ V2 ∪ … ∪ Vm ∪ {v} (v ∉ Vi, ∀i ), E = E1 ∪ E2 ∪ … ∪ Em ∪ {(v, v1), (v, v2), …,(v, vm)}…∪∪VVm∪∪{v}{v}(v(v∉∉VV,i,∀i∀i),),EE==EE1∪∪EE∪…∪∪EEm∪∪{(v,{(v,v v),1),(v,(v,v v),2),…,(v,…,(v,v v)}2 ∪…m)}VV==VV11∪∪VV22∪∪…mi12m12mи в которомвыделена вершинаv, называетсякорневымдеревом.которомвыделенавыделенавершинавершинаv,v,называетсяназываетсякорневымкорневымдеревом.деревом.ииввкотором3) Толькоте объекты являютсякорневыми деревьями,которые можно построить со3) ТолькоТолько тете объекты являютсяявляютсякорневымикорневымидеревьями,деревьями,которыекоторыеможноможнопостроитьпостроитьсосогласно3)пунктам1) иобъекты2).гласнопунктам1)и2).гласно пунктам 1) и 2).17Vi ∩ Vj = ∅ (i ≠ j). Тогда граф D = (V, E), полученный следующим образом:V = V1 ∪ V2 ∪ … ∪ Vm ∪ {v} (v ∉ Vi, ∀i ), E = E1 ∪ E2 ∪ … ∪ Em ∪ {(v, v1), (v, v2), …,(v, vm)}и в котором выделена вершина v, называется корневым деревом.3) Только те объекты являются корневыми деревьями, которые можно построить согласно пунктам 1) и 2).При таком определении D1,D2,…,Dm называются поддеревьями дерева D.При таком определении D1,D2,…,Dm называются17поддеревьями дерева D.v1v2vm…При таком определении D1,D2,…,Dm называются поддеревьямидерева D.v1Dv11D1D1v2Dv22D2D2……………vmDvm mDmDmvvУтверждение.

Определения 1 и 2 эквивалентны.vУтверждение.1 и 2 эквивалентны.Определение Определения3. Упорядоченнымкорневымдеревом называется корневое дерево, вОпределение3.Упорядоченнымкорневымдеревомназывается корневое дерево, вкоторомУтверждение. Определения 1 и 2 эквивалентны.котором1)Определениезадан порядоки корневым деревом называется корневое дерево, в3. поддеревьевУпорядоченным1)заданпорядокподдеревьеви2) каждое поддерево Di является упорядоченным поддеревом.котором2)ДеревоподдеревоDi являетсяподдеревом.1)каждоезаданпорядокподдеревьевс однойвершинойтакжеиупорядоченнымявляется упорядоченнымподдеревом.Деревосоднойвершинойтакжеявляетсяупорядоченнымподдеревом.2)каждоеподдеревоDявляетсяупорядоченнымподдеревом.Теорема 3. Число упорядоченныхкорневых деревьев с q рёбрами не превосходит4q.iqТеоремаЧисловершинойупорядоченныхкорневыхдеревьевупорядоченногос q рёбрамине превосходит4.Дерево 3.с однойтакжеалгоритмявляется упорядоченнымподдеревом.Доказательство.Рассмотримобходадерева, называемогоДоказательство.РассмотрималгоритмобходаупорядоченногоназываемогоТеорема3.

Числоупорядоченныхкорневыхдеревьевсследующимq рёбрамидерева,непревосходит4q.«поискомв глубину».Этотобход описываетсярекурсивнообразом:«поискомв глубину».Этотобходописываетсяследующим образом:Рассмотрималгоритмрекурсивнообхода упорядоченногодерева, называемого1)Доказательство.Начатьс корня.Покаестьподдеревьявыполнять:1)Начатьскорня.Покаестьподдеревьявыполнять:«поискомв глубину».Этотобход описываетсярекурсивноследующим2) перейтив кореньочередногоподдерева,обойти этоподдеревообразом:«в глубину».2)3)1)перейтивкореньочередногоподдерева,обойтиэтоподдерево«вглубину».Начатьскорня.Покаестьподдеревьявыполнять:Вернуться в корень исходного поддерева.3)В2)результатеВернутьсякорень«вочередногоисходногоперейти ввобходкореньподдерева,обойтиэто поддерево«в глубину».глубину»поддерева.проходит покаждомуребру дереваровно 2 раза: одинВрезультатеобход«вглубину»проходитпокаждомуребрудереваровно2 раза:один В3)Вернутьсявкореньисходногоподдерева.раз при переходе в очередное поддерево, второй раз при возвращении из этогоподдерева.раз приВпереходев очередноеподдерево,второй разпри возвращениииз этогоподдерева.Врезультатеобход «в«в глубину»глубину»проходитпо каждомуребру дереваровно2 раза:одинсоответствиис обходомбудемстроитьпоследовательностьиз нулейи единиц,соответствиисобходом«вглубину»будемстроитьпоследовательностьизнулейиединиц,раз при переходев очередноеподдерево,второйраз привозвращениииз этого еслиподдерева.Взаписываяна каждомшаге нульили единицу,причёмнульбудем записывать,происхозаписываяна каждомшаге «внульили единицу,причём нульбудем записывать,если происхосоответствиисобходомглубину»будемстроитьпоследовательностьизнулейиединиц,дит переход в очередное поддерево, а единицу, если мы возвращаемся из поддерева.

Полудитпереход нав очередноеподдерево,а единицу,единицу, причёмесли мы возвращаемсяиз поддерева.Полузаписываякаждом шагебудемзаписывать,происхочимпоследовательностьиз нуль0 и 1илидлины2q, которую нульназовёмкодомдерева. еслиПо этомукодучимпоследовательностьиз0и1длины2q,которуюназовёмкодомдерева.Поэтомукодудит переходвосстанавливаетсяв очередное поддерево,а посколькуединицу, еслимы возвращаемсяиз поддерева.Полуоднозначнодерево,каждыйочереднойразрядоднозначноукаоднозначновосстанавливаетсяпосколькукаждыйназовёмочереднойразрядоднозначночим последовательностьиз 0дерево,и 1 длины2q, которуюкодомдерева.По этомуукакодузывает,начинатьлистроитьновоеочередноеподдеревоиливозвращатьсянаярусближезывает,начинатьли строить новоеочередноеподдеревоиливозвращатьсянаоднозначноярус ближеукак коднозначновосстанавливаетсядерево,посколькукаждыйочереднойразрядкорню.ТакимТакимобразом,образом,упорядоченныхупорядоченныхкорневыхкорневыхдеревьевq рёбрамибольше, чемкорню.деревьевс qсqрёбрамине небольше,по- позывает, начинатьли строить новое очередноеподдеревовозвращатьсяна ярусчемближек2qили2q2 =q 4 .

Теорема доказана.следовательностейиз0и1длины2q,аихчислоравноследовательностейиз 0 и 1упорядоченныхдлины 2q, а их числоравно2 = 4 . сТеоремадоказана.корню. Таким образом,корневыхдеревьевq рёбрамине больше, чем поИзоморфизмкорневыхкорневыхдеревьевдеревьев определяетсяже, qкаки изоморфизмграфов,Изоморфизмтактакже,изоморфизмграфов,но сно сследовательностейиз 0 и 1 длины 2q,определяетсяа их число равно22q =как4 .иТеоремадоказана.дополнительнымтребованием:кореньдолженотображатьсявкорень.Дляупорядоченныхдополнительнымтребованием:корень долженотображатьсякорень.Для упорядоченныхИзоморфизмкорневых деревьевопределяетсятак же, вкаки изоморфизмграфов, но скорневыхдеревьевтакжетребуетсясохранениепорядкаподдеревьев.корневыхдеревьев такжетребуетсясохранениепорядкаподдеревьев.дополнительнымтребованием:кореньдолженотображатьсяв корень.

Для упорядоченныхСледствие.Числонеизоморфныхкорневыхдеревьевq рёбрамии числонеизоморфСледствие.Числонеизоморфныхкорневыхдеревьевс qс рёбрамии числонеизоморфкорневыхдеревьевтакжетребуется сохранениепорядкаподдеревьев.qqныхдеревьевдеревьеврёбраминепревосходитпревосходитныхс сqqрёбрами4 .4 .Следствие.Число ненеизоморфныхкорневыхдеревьев с q рёбрами и число неизоморфДоказательство.Выделяявнеизоморфныхдеревьяходнойвершине,получимВыделяяв неизоморфныхдеревьяхпо пооднойвершине,мы мыполучимныхДоказательство.деревьев с q рёбрамине превосходит4q.неизоморфныекорневыедеревья.Упорядочиваяподдеревьяводнойнеизоморфныхкорневыхнеизоморфныекорневыедеревья.поддеревьякорневыхде- деДоказательство.ВыделяявУпорядочиваянеизоморфныхдеревьях впонеизоморфныхвершине,мыполучимревьях,мыполучимразличныеупорядоченныекорневыедеревья.Поэтомучислонеизоревьях,мыполучимразличныеупорядоченныекорневыедеревья.Поэтомучислонеизонеизоморфные корневые деревья.

Упорядочивая поддеревья в неизоморфных корневых деморфныхдеревьеврёбраминенепревосходитпревосходитчисланеизоморфныхкорневыхдеревьевморфныхс сq qрёбрамичисланеизоморфныхдеревьевс qс qревьях, деревьевмыполучимразличныеупорядоченныекорневыедеревья.корневыхПоэтомучислонеизорёбрами,которое,всвоюочередь,непревосходитчисларазличныхупорядоченныхкорнерёбрами,которое,всвоюочередь,непревосходитчисларазличныхупорядоченныхкорнеморфных деревьев с q рёбрами не превосходит числа неизоморфных корневых деревьев с qвыхдеревьевс сqqрёбрами.следуетутверждениеСледствиевыхдеревьеврёбрами.Отсюдаи иизтеоремыследуетутверждениеследствия.Следствиерёбрами,которое,в своюОтсюдаочередь,неизтеоремыпревосходитчисларазличных следствия.упорядоченныхкорнедоказано.доказано.вых деревьев с q рёбрами. Отсюда и из теоремы следует утверждение следствия. Следствиедоказано.§18.§18.ГеометрическаяГеометрическаяреализацияреализацияграфов.графов.оореализацииграфовтрёхмерномпространстве.§18.ТеоремаГеометрическаяреализацияграфов.Теоремареализацииграфовввтрёхмерномпространстве.Теорема о реализации графов в трёхмерном пространстве.Определение.графG =G (V,E).

E).Пустьлю-люОпределение.ПустьПустьзаданзаданнекоторыйнекоторыйнеориентированныйнеориентированныйграф= (V,Пустьдоказано.§18. Геометрическая реализация графов.Теорема о реализации графов в трёхмерном пространстве.Определение. Пусть задан некоторый неориентированный граф G = (V, E). Пусть любой вершине vi графа G сопоставлена некоторая точка ai: vi → ai, ai ≠ aj (i ≠ j), а любому ребруe = (a, b) сопоставлена некоторая непрерывная кривая L, соединяющая точки ai и aj и не проходящая через другие точки ak (k ≠ i, j).