Главная » Просмотр файлов » Спец часть (часть 1) (3 поток) (2015) (by Кибитова)

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

Файл №1161601 Спец часть (часть 1) (3 поток) (2015) (by Кибитова) (Ответы на спец часть) 6 страницаСпец часть (часть 1) (3 поток) (2015) (by Кибитова) (1161601) страница 62019-09-19СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 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).

Характеристики

Тип файла
PDF-файл
Размер
10,47 Mb
Высшее учебное заведение

Список файлов ответов (шпаргалок)

Свежие статьи
Популярно сейчас
Зачем заказывать выполнение своего задания, если оно уже было выполнено много много раз? Его можно просто купить или даже скачать бесплатно на СтудИзбе. Найдите нужный учебный материал у нас!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6367
Авторов
на СтудИзбе
310
Средний доход
с одного платного файла
Обучение Подробнее