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

НА .О .б.ходамротьС'») . П УСТЬ Н=Ь (6')И Hi. - блок графа Н , не ЯВЛЯГО1ИЙСЛ полным грайодч. Тогда сущеотвуют вершины sC & в Н; , нвомеглые д г у г с днугом. Из х-вореш 7.3 следует, что вершины и принадлежат некоторому простом}' циклу Z с5лока . ОсЗоэна- пим £ >1, Вд , , "*» Ьм блоки графа & , ооответстиукудие ввгшкзм простого цикла Z . Тогда граф ~^0 В> i являахоя овязшм гра­ фом йез точек оочл0НвШ1я, т.е. нераздодамым подграфом rpaija & . (Если бы граф &-( -содержал точку сочленения, то одна из вершн графа В(5^) , ооответотвуюш-'Х Е> £ ,, , оказалась бы вне простого цикла Z ). Таким образом, ос." зрится в нехсотсроЕд йлоке, что. противоречит максимальности блока. 'Дортатоздооть С ) . Пусть каждый блок графа Ц является полным графом. Построим граф Q , добавляя к каждой вершине Hi графа 6)(Н) число концввз"' ребер, павное числу тех вершин блока Hi , которые не являются точками сочленения графа Н . Яоотроан- ный граф & такой, что В (iS -J ~ Н . §7.5. rpaif)H панеоечений Пуоть S ~ множество. F =( S ; , i= •{,«][ _ оемейотво непустых подмножеств множества S . таккх, что О ~ S . ]>афом пересечений семейства F назыэаетоя графО.СР) = . =. ( v < f ' j ) , y(SlCF})) , в котором V(QCF))=F, )((Q(F)) =iiSi,Sj}: nS] 7^0 ' ' ^ L Граф & называется графом пересечений, если существуют множество S и семейство его подмнсхеств F , для которого ^ C f ) ' ^ ( P . Понятие графа перасечани'^ является весьма общим, 'тто олелует и з теореш. Теоюема 7.6. Лкбой граф является графом пересечений, Локаэательотво. Пусть ff - (V'^X ) - произвольный граф. ?ас-^ смотрим. множество 5 =У и оемейотво его псдг,1нокеотн тдв Г" 1^1> ; 5С инцидентно ЧГс } • Легко проверить, чтоQCP) л/(г. Изоморфизмом является отображение . Представим графы леков и точек оочленегля В(^) и^ОД прояз- вольного графа (? в виде графов пересечений. Пуот1^=С\/,Y j , £ >: Xi ) , i-i,n ~ блоки графа C/i J - точки сочленения графа (? . , . _ > Расомотрим множесгво V и оемейотво его подмножеств Легко проверить, что^(Я)-^ £ >(<?). Изоморфизмом является отобра­ жение В;, •О Vo . Л) Р\ Для того, -чтобы получить граф пересечений эс ( г ; , изоморфный 45