Спец часть (часть 1) (3 поток) (2015) (by Кибитова) (1161601), страница 6
Текст из файла (страница 6)
СвойстваСвойства деревьев.деревьев.§16.§16. ОпределениеДеревья. Свойствадеревьев.1. Деревомназывается связный граф без циклов.Определение 1. Деревом называется связный граф без циклов.Определение 2.2. ПодграфПодграф GG1 == (V(V1,, EE1)) графаграфа GG == (V,(V, E),E), называетсяназывается остовнымостовным деревомдеревом ввОпределение111 связныйОпределение1. Деревомназываетсяграфбезциклов.графеG=(V,E),еслиG=(V,E)—деревоиV=V.графеОпределениеG = (V, E), еслиG11 = (V11, EG111) =—(Vдеревои V11 = GV.
(V, E), называется остовным деревом в2.графПодграф1, E1) графаЛемма1.ЕслиG=(V,E)связныйи реброребро= (a,(a, b)b) содержитсясодержится вв некоторомнекотором циклецикле ввЛемма1.ЕслиграфG=(V,E)связныйиграфе G,G =то(V,E),выбрасыванииесли G1 = (V1, изE1)графа— деревои V1(a,= V.графеприGребраb)сноваполучитсясвязныйграф.графеЛеммаG, то привыбрасываниииз графаG ребраb) сноваполучитсясвязныйграф. цикле в1. ЕслиграфGутверждение= (V,E) связныйи (a,ребро(a, b)содержитсяв некоторомДоказательство.Этоследуетизтого,чтопривыбрасываниииз графаграфа GGДоказательство.Это утверждениеследуетиз b)того,чтополучитсяпри выбрасыванииизграфеG,топривыбрасыванииизграфаGребра(a,сновасвязныйграф.ребра (a,(a, b)b) вершинывершины aa ии bb всёвсё равноравно остаютсяостаются вв однойодной связнойсвязной компоненте,компоненте, посколькупоскольку изиз aa ввребраДоказательство.Это утверждениеследуетиздоказана.того, что привыбрасывании из графаGbможнопройтипооставшейсячастицикла.Леммаbребраможнопройтипооставшейсячастицикла.Леммадоказана.(a, b) вершиныa исвязныйb всё равнооднойкомпоненте,Теорема1.
ЛюбойЛюбойграф остаютсясодержитвхотяхотябысвязнойодно остовноеостовноедерево.поскольку из a вТеорема1.связныйчастиграфсодержитбыоднодерево.b можнопройтипооставшейсяцикла.Леммадоказана.Доказательство. ЕслиЕсли вв GG нетнет циклов,циклов, тото G являетсяявляется искомымискомым остовнымостовным деревом.деревом.
ЕсЕсДоказательство.Теорема1. Любойсвязныйграфсодержит Gхотябы одноостовноедерево.ливGестьциклы,тоудалимизGкакое-нибудьребро,входящеевцикл.Получитсянеколи в Gесть циклы, то удалимизнетG какое-нибудьвходящеев цикл.ПолучитсянекоДоказательство.Еслив 1Gциклов,тограф.G ребро,являетсяискомымостовнымдеревом.ЕсторыйподграфG.ПолеммеG—связныйЕсливGнетциклов,тоGиестьис1111торыйподграфG1. Полемме1изG1G—какое-нибудьсвязный граф.Есливходящеев G1 нет циклов,то G1 и естьнекоисливGестьциклы,тоудалимребро,вцикл.Получитсякомое остовноеостовное дерево,дерево, иначеиначе продолжимпродолжим этотэтот процесс.процесс.
Процесс должендолжен завершиться,завершиться, тактаккомоеторыйподграфG1.множество.По лемме 1ТеоремаG1 — связныйграф. ЕслиПроцессв G1 нет циклов,то G1 и есть искакE—конечноедоказана.какE —остовноеконечноедерево,множество.доказана.комоеиначеТеоремапродолжимэтот процесс. Процесс должен завершиться, таккак E — конечное множество. Теорема доказана.161616Лемма 2. Если к связному графу добавить новое ребро на тех же вершинах, то появится цикл.Доказательство.
Рассмотрим произвольный связный граф G = (V, E). Пусть u ∈ V,Лемма 2. Если к связному графу добавить новое ребро на тех же вершинах, то появится цикл.v ∈ V,Лемма(u, v) ∉Так как G —графусвязныйграф,новоето в нёместьпутьиз v в u. Тогдав G естьи про2. E.Если к связномудобавитьреброна техграфже вершинах,появитсяДоказательство.РассмотримпроизвольныйсвязныйG v.= Лемма(V,тоE).Пусть цикл.u ∈ V,стая цепьC из v в u. Поэтомув полученномграфе естьцикл C,(u, v),доказана.Доказательство.РассмотримпроизвольныйсвязныйграфизGv =(V,ТогдаE). Пустьu ∈V,v ∈ ЛеммаV,(u, v)3.∉ ПустьE. ТаквкакG —Gсвязныйто в нёместь путьвGи прографе= (V, E) граф,p вершини q рёбер.Тогда ввGu.неменееp –естьq связныхvстая∈ V,цепь(u, v)C∉изE.v ТакG — связныйграф, то в нёместьпутьв u.v.
ТогдаG есть и пров u. какПоэтомуполученноместьциклC,из(u,vpv),Леммав доказана.компонент.Если приэтом в G внетциклов, тографеG состоитровноиз– q связныхкомпонент.стая цепьCизvвu.ПоэтомувполученномграфеестьциклC,(u,v),v.Леммадоказана.Лемма 3. Пусть вПустьграфекGнекоторому= (V, E) p вершини qсодержащемурёбер. Тогда ввершиныG не менееpv,– добавляетq связныхДоказательство.графуH,uиЛемма 3.Пустьвэтомграфев GG нет= (V,циклов,E) p вершини q рёбер.Тогдавp Gнесвязныхменее pкомпонент.– q связныхкомпонент.ЕслипритоGсостоитровноиз–qсяребро (u, v).Тогдаuв Gи vнетлежатв разныхсвязныхровнокомпонентахграфа H,то число связкомпонент.Еслипри еслиэтомциклов,тографуG состоитиз p –вершиныq связныхДоказательство.Пустьк некоторомуH, содержащемуuкомпонент.и v, добавляетных компонентуменьшитсяна1.Еслиu,vлежатводнойсвязнойкомпонентеграфа H, тоДоказательство.Пустьu ки некоторомуграфусвязныхH, содержащемувершиныи v,тодобавляется ребро(u, v).
Тогда еслиv лежат в разныхкомпонентахграфаu H,число связчислосвязныхкомпонентнеизменится.Влюбомслучае,числосвязныхкомпонентуменьсяребро(u, v). Тогдаесли u и наv лежатв разныхсвязныхкомпонентахH, то числоныхкомпонентуменьшится1. Еслиu, v лежатв однойсвязной графакомпонентеграфасвязH, тошаетсяне более уменьшитсячем на 1. Значит,при добавленииqоднойрёберсвязнойчисло связныхкомпонентуменьныхкомпонент1.
Еслиu, Вv лежаткомпонентеграфа H,точислосвязных компонент ненаизменится.любомв случае,число связныхкомпонентуменьшаетсянеболеечемнаq.ТаккакграфGполучаетсяизграфаG=(V,∅)добавлениемqрё1числосвязныхкомпонентнеизменится.Влюбомслучае,числосвязныхкомпонентуменьшается не более чем на 1. Значит, при добавлении q рёбер число связных компонент уменьбер,то в Gболеене менее наp – q связныхприкомпонент. Пустьтеперьв Gсвязныхнет циклов, и пустьв прошаетсяq рёберчислоуменьшаетсянене болеечемчем на1.q. Значит,Так как графдобавленииG получаетсяиз графаG1 = (V, ∅)компонентдобавлениемq рёцессеполученияGизGдобавляетсяребро(u,v).Еслибыu,vлежалиужеводнойсвязной1 Так как граф G получается из графа G1 = (V, ∅) добавлением q рёшаетсянеболеечемнаq.бер, то в G не менее p – q связных компонент.
Пусть теперь в G нет циклов, и пусть в прокомпоненте,то менеев G,леммекомпонент.2, возникалбы Еслицикл.Следовательно,u, vвилежатразныхбер,тополученияв G не– 1q добавляетсясвязныхтеперьвGнет циклов,пусть ввсвязнойпроцессеG согласноизp Gребро (u,Пустьv).быu,v лежалиужеоднойсвязныхкомпонентахипридобавленииребра(u,v)числосвязныхкомпонентуменьшаетсяцессеполученияGизGдобавляетсяребро(u,v).Еслибыu,vлежалиужеводнойсвязной1компоненте, то в G, согласнолемме 2, возникал бы цикл. Следовательно, u, v лежат в разныхровнона1.ТогдаGсостоитровноиз2,pвозникал– qребрасвязныхкомпонент.Леммадоказана.компоненте,товG,согласнолеммебыСледовательно,u, v лежатв разныхсвязных компонентах и при добавлении(u, цикл.v)числосвязныхкомпонентуменьшаетсяТеорема2(оразличныхопределенияхдерева).Следующиепятьопределенийэквивасвязныхкомпонентахипридобавленииребра(u,v)числосвязныхкомпонентуменьшаетсяровно на 1. Тогда G состоит ровно из p – q связных компонент.
Лемма доказана.лентны(p1.—Тогдачисловершин,q—числорёбер):ровноТеореманаGсостоитровноизp–qсвязныхкомпонент.Леммадоказана.2 (о различных определениях дерева). Следующие пять определений эквиваТеорема2(о различныхдерева). Следующие пять определений эквива1)G—дерево;лентны (p — числовершин, q определениях— число рёбер):лентны(pG——числовершин,q—числорёбер):2)1) Gбезцикловиq=p–1;— дерево;1)—дерево;3)графq p= –p 1;– 1;2) GGG——связныйбез циклови qи =2)G—безцикловиq=p–1;4)3) GG——связныйграф,ноприлюбого ребра становится несвязным;связный граф и q = p –удалении1;3)G—связныйграфиq=p–1;5)G—безциклов,нопридобавлениилюбогоребрана становитсятех же вершинахпоявляется цикл.4) G — связный граф, но при удалении любогоребранесвязным;4)G—связныйграф,ноприудалениилюбогоребрастановитсянесвязным;Доказательство.Докажемследующиелюбогопереходы:2)же⇒вершинах3) ⇒ 4) ⇒5) ⇒ 1), цикл.откуда5) G — без циклов,но при добавленииребра1)на⇒техпоявляетсяG — без чтоциклов,но при добавлениилюбого любоеребра натех же вершинах появляется цикл.будет5)следовать,излюбогоусловиявытекаетдругое.Доказательство.
Докажем следующие переходы: 1) ⇒ 2) ⇒ 3) ⇒ 4) ⇒ 5) ⇒ 1), откудаДоказательство.следующие1) другое.⇒2) ⇒ 3)то⇒⇒ лемме1), откуда1)⇒ 2): так как—связныйграф вытекаети Gпереходы:не содержитциклов,p –4)q⇒= 5)1 по3. Отбудетследовать,чтоGизДокажемлюбогоусловиялюбоебудетследовать,чтоизлюбогоусловиявытекаетлюбоедругое.сюда q1)=⇒p –2):1. так как G — связный граф и G не содержит циклов, то p – q = 1 по лемме 3. От1)q⇒⇒таккак G3 —граф и Gне содержитциклов,q = 1Gпо—лемме3. Отсюда= 3):p2):–по1.2)леммев Gсвязныйчисло связныхкомпонентравноp – q =то1,pто– естьсвязныйграф.сюда q = p – 1.⇒4):3): припо лемме3 в G одногочисло связныхравно pпо– qлемме= 1, то3естьG—связныйкомпограф.3)2)⇒удаленииребра pкомпонент– q = 2.
Тогдачислосвязных2) ⇒ 3): по лемме 3 в G число связных компонент равно p – q = 1, то есть G — связный граф.нент не– q = 2. одного ребра p – q = 2. Тогда по лемме 3 число связных компо3)менее⇒ 4): чемприpудалении3) ⇒ 4): при удалении одного ребра p – q = 2. Тогда по лемме 3 число связных компонент4)нечемGp –имеетq = 2.цикл, то согласно лемме 1 можно выбросить одно ребро так, что⇒менее5): еслинент не менее чем p – q = 2.4) ⇒ 5): еслиG имеетцикл, толеммесогласнолеммедобавить1 можнолюбоевыброситьодноребротак, чтограф останетсясвязным.Согласно2, еслиновоереброк связному4) ⇒ 5): если G имеет цикл, то согласно лемме 1 можно выбросить одно ребро так, чтографостанетсясвязным.Согласнолемме2,еслидобавитьлюбоеновоереброксвязномуграфу G на тех же вершинах, то появится цикл.граф останется связным.
Согласно лемме 2, если добавить любое новое ребро к связномуграфуG натех же Gвершинах,то появитсяцикл.5) G⇒не связныйграф и вершиныu, v лежат в разных связных компонентахграфуна1):техеслиже вершинах,то появитсяцикл.5)⇒1):еслиGнесвязныйграфивершиныu, v лежатв разныхсвязныхкомпонентахграфа5)G,⇒то1):добавлениек G ребра(u, иv),вершиныочевидно,порождаетциклов,чтокомпонентахпротиворечитесли G не связныйграфu, vнележатв разныхсвязныхграфаG, то добавлениеGсвязныйребра (u,граф.v), очевидно,не порождает циклов, что противоречит5).Отсюдачто Gкк—Теореманедоказана.графаG, тоследует,добавлениеG ребра(u, v), очевидно,порождает циклов, что противоречит5).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
