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

тогда и только тогда, когда ооот130тотвую!Щ1е'им блоки имеют общую точку оочлененкя. Графом точек сочленения графа G пазываотоя граф C(ff-) , вер­ шины которого ооотЕвтствуш' точкам сочленения графа (? , и две вершиш Е CCS-) смежны тогда и только тогда, когда'ооотвототвуго- щио км Т0Ч1С! сочленйния принадаеашт одному блоку. Па рио. 7.1 показаны граф G (•( ^ ), его блоки ^ ^ . граф блоков B(G) (4) и грр'*1 € (,&•) (.Ь) . Рио.7.1 Иа определений олбдует, что графЁ)С&) содержит цикл дагш И , если И блоков графа G имоют одну обиз'ю точку оочленення. Граф С ( ( ? ) имает цикл длины И , если Y\ точек ооч-ченения при­ надлежат одкоод блоку Грефа G . Претам легко заметитъ, ч';'о любые две вершины графов В (б*) или цринадле)лаи(ке общему щшАу, омех1Иы, т . е . любой цикл в Ь(.&) или СОД содержит в •БСб' } и С 6? J BOG диагонали. Теорйма 7.5. Граф Н является графом блоков некоторого графа G тогда и только тогда, когда каждий блок графа Н является пол­ ным графем. 44