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

Ид, =• ( ^< - - цепь длины IX(/ti,}f=S , не являющая- оя простой ценыо, т . к . в пей цовторяетоя вершгаа I'l ; / з ~ (Щ~ Vr ) - простая цепь длины iy(/j,)l - S ; ~ маршруты, причем - цикл даганы Q ; / ' I , - простые цшиП)! дтаны 3 ; - простой цикл дл.и(ш 4 . , Заметим, что,как это следает из определения, не вое пооле'- довательности вершин являют-^я маршрутами. Например, послодова- тельнооть не является зррутом в графе на рис.3.1., т . к . соединение вершины этой последовательности 1*^ Z Vs чв смежны. При псдсчете количества простых циклов последние,обнчнс рассматриваются о точностью до Е, .DO^NA начальной теши и направ- ! Ленин обхода. • Например, простые це1Ш1 ( Щ , 1/1 ) , ( 'Щ , 1й , "Щ ) , можно считать совпа^-жщми. При таком соглашении кавдый простой цшсл представляет целый клаос проотнх шгклов, отличающихся от него лишь выбором начальной вершины или направлением осЗхода^ Поэтому можно считать, что граф, лзсйракеи- пый на рнс.3.1, содертат воего 6 простых циююв ( т . е . 6 luiaccoB прооткл циклон). Если и у/д,--маршдуты, причем, пооледователыюотъу/^ является подпоследовательноотью, т о н а з и в а о т о я псдаир- шрутом м а ршр у т а . В этом случае I'-oBopm, что из маршрута можно выделить маршрут Сфоредлируем ряд простых, но важш1х предаоженпй. Леима 3 . 1 . Из дабого ( i ' * - •г*/' ) - марпфута графа мокно вцделить простую ( 1 Г - гй" )-цапь. Доказатйлъотао. Пусть дан- хгроизвольннй ( "У- )-марВ1р5'Т = Коли В нем все вершинц разные, то он oai/i явлг'тся простой,целью. В противном случае допустим, что 1Гс^ - первая (слева) вержна маршрута, псвторш»- щаяоя в нем. Пусть ~ последнее ее повторение ( 1Л:^^ ), . Удалим из маршрутауЧ все вершкнн, начиная о и до *01^ - По­ лучим подпоследовательнсоть У Которая таклш является С V-lO') - маргпрутом. Действительно, в а р г а н ы и омежш (см), т.к.- , а OM .I/Cfc ; остальные'пары соседних вершин в У оможнн, т . к . они смешщз м . 19