Теория графов и комбинаторика

вершин rpa'Isa. Прадаагаатоя ооотавить такой алгоритм в качестве упражнения. ^ ' Твомма 3 . 3 . Еоли граф G неовязнМ, то 5 - овязный граф,. Лока^^атальотво.Рэоомотрим произвольннй несвязный граф ( ? - . = (V,xj. Пусть ei=-CVi,Xi) . - 9Г0 Korraoiiejrra. _ ' Выберем две лккЗив ввршиш V" ,uf дополнения б" V j V ) s Возможны два случая: I. '' верганы прпнад- лажат одной компонент в графа (? . Тогда, если и, е \/к ^ ( ИФСо ) , то в 6^ (tt ow OK посладоватбльноотъ( iT, LL, ИГ) является {b'-lJJ-) -маршрутом в . г.""к , < г У, п \ V 6 V k ^Ш'б'Чг - веришны С жЬТ принадлежат разным кг. тоненгамjrpa'Ja б' - Тогда wTне OM IT B (? . Слвдсватапьпо, tfT ом IT в (5-, Таким образом, любые две вериины графа & можно соедикп гь маршрутов-у i . o . ff - овязннй граф. Заметам, что утвержденае, обратное теореме 3„3, ио оправод- ливо, в чем можно убедить®" на примерах, TTOMija 3 . 4 . В овязаом 1>рафв любые две д-таннейшиэ простив цепи HMWx' общую верииу. Твопема 3 . 5 . Удалеше рабра, прщшддекащаго циклу r p a t ^ a ^ , • не нарушает овязнооти графа. Доказательство теорем 3 . 4 , 3 . 5 предлагается дровеоти чита­ телю в качаотзе упражнения. ТбОРвма 3.6.Любой озязный граф о зершинами содержит не менее { р - 1 ) ребер. Докозатальстяо. Примашм индукцию по числу верщн f . Д"Я утвбрзденяе очевидно, Допустшл, что ^ [>Ш -i для всех случаев, когда ^(6-}4 К . Пусть 6- ~ овязный граф с К+5 вертной, Удал1м одну из 1ершин ИГ jrpa ®a S- . При этом '^*дет удалено sf_<ir)jpe6op. Обозначим G i , £ =-1>И -компоненты графа ^ - 1 Г ;УС=|,и ( ^ к ) I& i - овязный граф. JIo индуктив­ ному^ првдяо.-:ожению •;t =» <,и ^ ((Рг) ? ^i&i) -/ . Тогда ^ ) :$. ^ ^ ~ VI , т . е . ( S ' v ) ^p(S-'-r}-У) ','Чак как овданый, в 6-гГ имеет и компонент, тс ^ И • Суммируя два аосладких неравенотва, получим (^(.5-)^ р(е-гг)=.f(0 ~i. Индуктивный Biar вьшолнен, и теорема доказана. • В случае ориенгирсванных графов (? " (^V,Г ) в^^одатоя три до~ нятая связности. ' . Орграф (г называется связным (или олабо связным, ЙЛЙ слабым) еоли связно его ссноваяив , и сильн озязным (иди бисвязным, пли сильнш.'), воли V r , u r ^ V 3 CV-W-)-nyTb8rJCt/r"Г ) -путь. 24