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

при нумерации вершин, показанной на рио,9.2, предшво^'по- ваЕШе опредаляется индексами. Пуохь и I t T - вэршины 1м и ( МИ )-го ypo'^-wS, причем vTe Г(и-) . Тогда Ы называется непоорэдотвзннвд П01'0!.1К £ з?.1 вер­ шины ТГ (а f - непооредотзешппл првдаом верлжш 1*?*). .хи­ на У называется предком взршшш W { ЬТ - погомог. 1)" ) , еолн oyiiiS' -'вует поолбдоватвльностъ ( , ' • • > ) , К8-.тая Н9рш;шй которой являетоя нэпооредотвентч нредаюы слсдуаде'.^, Т.0, ^ С1Г—I(/") - •^ТЬ. Бннарша.1 (двоичным) деревом называагоя ориантировалноо дероло, в котором Vi^" €V/ ^ 9 . 3 . Пвкжгеаостй и д.оцикличво^^Д raigii rps?ia Пусть <? = ( V , У ) - оБязный граф. йкЗерем некоторый чл в б? и удалим из него какоа-шгбудь ребро (С . Получим овязниЗ граф (?- х • Применим эгу процвдз'ру к одному пз циклов rpas|ia (у-зс и так до т а х пор, пока не оо^'^нетоя ни одного дислэ. Б результате получим остов Т г р ф а (? . Если гращ 6^ a s саязкий, т о , цриманяя описанную процед;'ру удаления pedep к воем ог-о ком­ понентам, получим -.ОТОЕНОЁ лос графа & . : Чиоло удаленных pedep в описанной процедуре паанваетоя п :ч- личеоким рангом графа G и обозначается VC6-J . Число ребер остовного леса Т называется коцикличеоким рангом графа (? п обозначаетоя . Из твораш 9 . 1 , учитывая, что каждая комггононта ласа является деревом, по.'зучим раванотво р-К, г д е р - чиоло вершин графа (Р ; к - чноло кошонвнт. 15а опрвдэ- лвн1ШТС(т) и слс.иубт, что Т ( ^ ) ~ . Отокша <^--р •) к . Ив данных опрйдвлений олздует, что У (в-) . :jiBKO чмолу рэбар дополнения Г леоа f в (?. Дополконие f леса Т называют таюке коле.э м. Теорема 9 . 5 . (Об оотовшх лесах). Пусть Т - оотовной лес графа G . Тогда а ) любой разраа графа <? оодержлт некоторое ребро чвоа Т б) "jodoft цикл графа (? оодерм'г некоторой реб­ ро и з Т . Доказательство этой почти очевидной теорзш спускаем. §9 . 4 . 'фундаментальные оиотвмн циклов и вазразов тт'а(!>а Пуот' i5^ - ОЕ зный граф, 'Г - его сотов, 'Г - дополнение Т в (? , Выб.ер 1 ребро GO кодерева Т и добавим его к Т , Граф Т+гс содержит ровно один цикл (ом.теоре-'лу 9,2) 2 . Такой ;Цтакл 2 явллэтоя простым и называетоя фундаментальным или базнс- 57