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

цаклог>1. ы;ундак*эктально11 оиотег''? циклов гр??фа & (аоооции— •i.oiSHKO-i с дероком Т ) называется окстама простых циклов, по- .•л"К;ю::рлся путем пооледоватального, раздельного добавлашш р в - г'ор J ' с '7 I" оотову 'Г . neitovopoe ребро ^ из 'Г'. Дерево Т разобьется на два Еоддорева Ti =CVf , X i ) и • Множество ребер Г ],^мй (X , соедкяжощях вершчнк из Vi о вершинами из , явля­ ется 1)5зреао;л графа 2 * (ксцнклом графа), казнваошм фуядаман- тельшм 1Ш! базноным. СледуангЕй ц^ундаментальпый разрез можно псс.^чить, удаляв другое ребро из Г . 'Хундаментальной системой разрезов графа ff- (ассоциирован­ ной о деревом Т ) называется^сио'гема разрезов, подученная в результате пооладовательногй к раздельного удаления ребеи осто- ha I . , • . Легко заметит^ что чяоло фундаментальных цшслов графа равно числу ребер Т , т . е . равно цккличоокол]у рангу Т(&}, а число фундаментальных разрезов равно числу ребер в Т , т . е . разяо коцикличеокому рангу графа Y * ( i y ) . Еолл доходный рай 9- иаовязный, Т - оотовной лео, Т - дополнение Т в б , то дош получастя фундаментальных СНОТЙМ • циклов и разрезов надо проделать описанный процеоо для воех компонентов (?. ffoHMej). Граф G , сдйй из его оотовов Т дополнение Т изобрзпет ка р,дс.Э.З. Для этого графа Ч'(^) =8 ^k-i •фундаментальная оистемр разрезов вавна i 2 L , i = Ui}> ^'Дз й'унлемаятальаая система разрезов равна{ z f = } , w e -1^-1 > I' • ^ 3 T I » •4 58