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

ГЛАВА 7 . СТРЖТ7РА ГРАФОВ ^7.1. Точки оочлекйнля. ь'осты ч блоки. Их TniiiSHtncy Вершина 'д' графа <? =( V , X ) называвтоя точке!! сочленения, оо- •ли при удэлатш этой вершинн получаемся грай G-V й числом ком- понен!' большим, чам у графэ ^ . Если Q- ~ связшй: граф к 1Г~ -соч­ ка сочленения, то графб ^~1Г - НЙ СЕЯЗНШ! и осдоришт на менаа двух компснэих.' Кз определения олеадет, что кзо.шрованнвя ларшп- на ко может быть точкой соч ленения. Моохом графа называется pedpo X , удаление которого увели- чизает число компонент. Граф^ назнЕаётся неразделишм, еол!{ он связный, Honyo?oS п бе з точек оочлекенЕЯ. Вое другие графа назыЕзютоя разделт!гжг-.гл. Блоком графа (? назазьитоя его иаксимальньг!; (в огшсле ^ ) неразд0„таша подграф. Ес;ш граф разделимнй, то он шлеет более одного блока. Иеразлел:с,1ий гра^) имеет еданогт-енжй блок, совпача- iMiKli с самюл 1'рафоы. Приведем пекоторче признаки точки сочлененяя, моста н блока. Теочема 7 . 1 . Вершнга связного графа G-(}f,X) яиляетоя точ­ кой сочленения тогда и только тогда, когда выполняется одно из следуг чх условий; а ) существует разбиение множеотЕа {тг] такое,что V i T ^ GV i , иершйна IT ирикаддежит любой простой (ТГ^ - 1?^ ^ - , цепи; б) существуют вершина U.,V!re\/ , ОГ . ЕШШ - отV , такие, что Bepiiimi. l/' принадлежит любой простой ( ti-~ 1^)-цепи. Доказатыльотзо. Докажем вначале ЕСТИННОСТЬ пшжкацик:^, IT - точна сочленения" =|> „ d " . Ti;n какV - точтса сочленения, то граф (т-тг не связный и , следовательно, имеет не менэе двух ксмпонент. Обозначим \/\ - множество верами одной из компонент графа 9 ~ V , а ~ мнсжеотво вершин воех остальных кошоиент ( \/j,= Имеем разбиение {Vi,Vx/l многества V v [ t r j на два 11од!,1ножест- в а . Покажем, что ото разбиегше удовлетворяет условию " а " . Пус?ь 1/^6 V-t ,Vi,eVx, • Вершины Wf и принадлетат разиши компонен­ там графа ( ? - г г . Следовательно, в ^ - т Г неъ ггроотых С - ' й ) - ц э - , пей, но в графе G простые -цепи существуют, так как граф & ~ связный. Следовательно, V прииадлежпт любой простой (t/i - ТЯ/) - цахга. 2 . Покажем, что " а " " б " . Это очевидно, так как уоловяе " б " является частным случр"м услов!ш " а " . 4 1