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

„ " Ж - MOO'f" «•fit* »lo»l "(3 » ^ Теорема 7 . 3 . Пусть G= { ^ , t ) - связньй! граф и ( V j ^ 3. Тсгдга ^5" яалявтоя блоком тогда и только тогда, кох'да выполняется одно и з оледаювдх условий: а ) любые две з?"рганн графа (? принадлежат некоторсь<у общему npoo'i'ojiy циклу; б ) любая вершина и любое ребро графа G прчнадахежат некоторо~ му общо11«у кроотому циклу; в ) любыа два ребра графа ^ пркнадлс .ат нг"»торому общему хфоотощ циклу; г ) рдя лвбых двух Евршик 1Г и любого ребра ЗС, суп>оотпу «'1' п1юотая 1Г~ и)") ~ цепь, содаркащая рабро i c д ) дл^^'любых трех раз1щх нершин графа Й сущеотвуат прост,-зя ц е п ь , ородинящая дне из. них и проходащая 'ч-ераз третью; в ) ^У1я любых трех paaifflx варшкй графа •(? оущеотвуат простая ц е п ь , ооедшшщад две и з нкх к не -проходладя через третью. До1сазатвльотво этой теоремы опуокаем. Таопама 7 . 4 , Любой нетривиальный .связный rpa^i имеет хотя бы д в е взрвгаш, н е являюидаеоя точками сочленения. Локазатедьот':',). Пусть 1Гза !U?" - наиболее удалеиша вершины Траста. Раоотояниэ меаду ними равно '=> (6-). Допустим, 4'so l)" - точка сочленения. Тогда граф ~ не овяашй. Обоанш-' чим Н компоненту графа'(9-V" , т оодержащую вершины ti?" . Пуоть U- - некоторая вершййа графаf | . В графа S-'V^ пат U-)~ мар- .„рутоБ. Следовательно, М а я простоя ) -•цепь графа б ' . про­ ходи'? чйрез взригаиу 1Г . Т - а д что новозморно. Аналогично доказызаатоя,'что и- в^арш® 1*^ на япляетоя точкой ооч - лонанид. "очкк оочлвне'"1Я, моста и блоки йеовдзного графа оиределли/-- о я яоаледователышм раоомотрениемв » компонент. § у . 2 . ГоаДи бдокоя а точек оочланения 11рвр(>тавлвнии о о т р у в д р е грйфа ^ даот графа блоков и точек оочлейвния, Графом блоков графа <5^ йаваяавтоя граф 6 ^ 6 ) , вершины кото­ ро г о ооотпетствуют блокам Грефа (Р , ч две вегтины в ВС^) омвЖ1« 43