В.Н. Нефедов, В.А. Осипова - Курс дискретной математики (1127083), страница 47
Текст из файла (страница 47)
Но тогда (рь ..., р*) — цнклавой базис в 0', откупа н слелует справедливость равенства (428). В случае «б» в мультиграфе 0 будет сушествовать простой пипл, вроходящнй через добавляемое ребро х (оь сг). Действительно, в силу того, что вершияы сг, о~ првнадлежат одной компоненте связности мультнграфа 6', нх можно соединвть маршрутом в 0; нз котсрога в свою очередь можно выделить простую цепь 8 = о,хз ...
х»о«ог (см. утверждение 4.4). Поскольку 8 — простая цепь в 6', получаем хг чья, г=2, ..., Д. Но тогда р о,хо»х, ... о«хьог — простой цикл в 6. Рассмотрим случай, когда мультиграф 6' не является ацвклвческим (если 6'— зцпклическнй мультиграф, то рассуждаем аналогично). Пусть (рь . р.), тле т' т(0'),— пиклоасй базис в ОС Так как в цикл р входит (и притом один раз) ребро х.
которое ие ведер. жнгся нн и одном нз циклов !и, ..., р., то цикл р ие яачяегся их линейной комбинацией, а слеловательна (см. замечание 4.сэ), 1::.:::) рь -., р". р] — независимая система цвклов. Покажем, что )н, ..., !и, р) — циклспой базис в О. Лля этого докажем, что произвольный цикл р в 0 является линейной комбинацией циклов рь ..., р..(р. Согласно утверждению 4АБ досгаточяо рассмотреть случай, когда р является простым циклам.
Если ребро х ве входит в р, то !» — цика в 6', а следовательно, он является линейной комбннвцвей циклов рь ..., р, . Пусть тсиерь ребро х входит в р. В силу того, что р — простой цика, ребра х входит в р один раэ. Беэ ограничения обшвсств можно считать, что цика р проходит через ребро х в том же направлении, что и цикл р.
т. е. имеет ввд р о,хогр,ы, ... р~юь где 1ъ2, р;Фк, 1 !. ..., 1, юг=о» Рассмотрим цнии Ч = озр~ю, ., у,ю~х»оь -. хгоз (см. рве. 4.88). Очевидно. что г! — цикл в 0', так как он не проходит через ребро х, а слеаовательво, т! является линейной комбинацией наклон рь -., р,. Заметим. далее, что т! = и†р, а значит, цикл р=г!+!« является линейной комбинацией цаклов рг,..., р.ь р. Таким образом, (рь ..., р..
р) — цикловой базис в О, а следовательно, т(6) - ъ'+! = «(0') + !. Восполюовавшись тем, что по вндуктивному врсдположению выполняется ра. венство т(0') = т(6') = гл(6) — л(0') + р(6'), а также теи, что апашем случае справедливо л(6) =л(0), ш(0 ) =-т(6) — ! мю Р(6') Р(0], имеем ч(6) ч(0')+1. Но тогда ч(б] ч(0') + ! = ч(6') + 1 ч(0].
Теорема доказана. Рассмотрим теперь задачу о практическом нахождении пиклоаого базиса мультнграфа. Преляарительно сведем ее н зада. чам нахождения цикловых базисов для связных мультиграфов Теарыеа 4.а. Пусть 0 (У,л) — мультигрвф, не являющийся ацлклическим, бн ..., 0„(где р р(б)) — мультырефш, яоялющиеся компонентами связности мультнарофо О. Пусть тпюсв Тг)ш(1, ., Р) М,= (Рп, ..., Ргч) (где чг=ч(б~)) — Цикловоб бааис мультигрпфо б~ (нри ятом, если бг — оциялнческнс мулыиграф, та мг е)).
тогда м (рш ! 1. -.. чн г 1, р) — цикловос базис мультирафа 6. пге ь я — взоювольена витя из о. Понашю, что и «зллегс» ливеан в «онйшацвеа цнельь аа м. поашльхг шьане лвс рзюич ые вевшиеы, вш:дание И, швкео ьсвявввгь маршрутом, ть я авзаена цззю» в «нн тщша шлшоянпе вюноста Оь По иняз и авмм са шшеаиоа нснэлвзнвеа чнкаьв вз Мь а так зак МгшМ, то и швшоз ю М. Поа ч1пзен шлет ш ллзесгю иннин М.
Пглшилуа гессену 4З, а танис упнрндеее 4.10, инеем )м) - х (м,) - и ч(од - д ! (о,) — (о,) + П - ш(о) — (о) + + р(п) ч(о), откуль соглзсао пвюнлюзш 4лз получаем, чть м — шзшшша сььас нтм тзгсара О. Из доказанной теоремы следует, что задача нахождения ннклового базиса шроиввольного мультиграфа сводится и конечной соао- 1 - ), ( т) ! к)нности задач нахождения ции-, ' г' лового базиса связного мульти- „ .„, л, вл графа Опишем алгоритм решения этой задачи. Алгоритм 4.8 нахождения Рзс.
4З) ииклового базиса связншо мульти- графа О. Если ч(6) = О, то 0 — ациклический иультиграф, а следовательно, цинлового базиса не существует. Пусть теперь «(0)) О. Вьшелим в 0 остовное дернш Т. Пустил л(б), гл гн(0),хн ..., к -г — ребра в Т, а х,..., х — остальные ребра мультиграфа 6 (заметим, что поскольку ч(б))0, ош.'видно. выполняюшя неравеястза лай, юля). Чиано последних ребер равно ш — л + 1, т.
е совпадает * ч(6). добавляя любое яз ре. бер кь 1= л, ..., гн, к лереву Т, получаем некоторый подграф мультйграфа б, нз которого вылеляем простой цикл и,, г) (см. анже эамечаыие 4АО), проходящий через добавляемое ребро хь Действуя таким образом, находим совокупность простых циклов (рь .-, р и). Поскольну в каждом из циклов втой систсыы ямеется ребро, пе содержащееся в других циклах, то полученная ыь система циклов является независимой. Итак, мы нашли независимую систему цяююв с «(6) элняенгвмн, которая явлветсн цякловим базнсом мультнгрвфа С.
Действительно, предпопожнв, чю некоторый цикл и мультнграфа 6 ве явлются линейной комбинацией цнклов гц, ..., м.,ег, с учетом замечания 4 39 заключаем, что система циклов (р», ..., р.»е». р) является лннейно независимой, а это противоречат тому, что «(6) — нанснмальное число элементов е незавяснмык системах цякэов мультнграфа 6. Зювщание 4.43. Согласна утвержденна 4АО после добавления к Т ребра хь где 1ж(л, ..., ю), получаем мультнграф 6», в ко»ором существует единственный (с точностью до направлення обхода я начальной вершнны обхода) простой цикл, проходящей через добавляемое ребро хь Пример 4.3!. Используя алгорятм 4.3, апрелелнм цякловой бюнс ыультяграфа О, изображенного на ряс.
4.31,а. Имеем г(6) =щ(6) — я(6)+р(6) =8 — 4+! 3)б, т. е цнкловой базис мультяграфа 6 существует. Выделим произ- 1 ч вольно остовное дерево Т б ' „" хг~ «, сь МУЛЬтпГРафа 6 (СМ. Па РНС. 4»»г 7 т пУнктнРнымн лпннамп Указах т 1 "бх» ны РсбРа, Удаленные вз 0 для выделения дерева Т). Прн б) вмнелеяни остовнио дерева Т нз свяаного мультнграфа С Р .»Зг была уда.гено всего «(6)=б Ребер» хз, хь х», хь хз. Добавлян поочередно к Т каждое яз перечисленных ребер я выделяя яз получаемого таким образом мультвграфа простой цикл, г»ыщм цпклы р» = в»хтозх»в»хзв»1 в»х»о»х»озт»о»1 1»» = СЩ»П»Х»ЩГ п» о»хю»х с х»ос П» = п,х,о,хзв,х,с,, составляющие цнхловой базис мультяграфа 6. Зпнсчение 4.41. Как следует вз оппсаняя алгоритма 4.3, цнк« лозой базис, получаемый в результате прнменення этого алгоритма к произвольному связному мультяграфу О, состоят вз простых цяклов 4.3.4.
Цнкиаывтячеслая матрнца мультнграфа Пусть 6 — мультнграф, не являющнй»ш апнклическвм '(т. е. «(0))0). Матрица С(0) размерносгн «(6) Х ю(0), сгрокаын которой являются вектор-циклы цяклового базнса мультпграфэ 6, назмваися цнххологическеп яагрицсй мультнграфа 6. лтт Прнмер 4.32. Опредвгжн цикла. магическую матрицу для мульти- графа 6 (см.
пример 4.31). Введем орвенташпо ва ребрах мультнграфа 6. В результате пояучнм, например, орнентнрованнмй псевдо- граф, непораженный на ркс. 4.32. Выпишем вектор-цнкяы, сгютвегствуюшне циклам нз цнюювого базиса мультягрэфа 6, найденного в прнмсре 4.3!г С<дг) = <О, 1.<,О,— <ОО О); с(м) = < — <,о,о, 1, <.о,о,о); с(! *) - <о. о, о. о, 1, — 1, о, о)! С(пч) ( — 1, !.
О, О. О, О, 1, 0); С(дг) = ( — 1,1,0,0,0,0,0,— 1) Тогда р о 1!) О) — 1!"'о о б [1 Г-!о::,О!< 1;О О 0~1 С<6) О ОО О~ 11 1 О О). — 1~0 О~ О,' О 1 О[~ — ! 1!О О! О! 0 0 — 1 Закееаяие 4.42. Иэ определенна цнкламатпческой матрвам мультнграфа 6 следует, что ранг матрицы С(6) равен т(6), т. с оп совпадает с количеством строк п С(6). Замечание 4.43. Вел» (!н, ..., р,) — цнкложгй базис связною мультпгрзфа 6, найденный по алгоритму 4.3, н С(6) — цвкломатнческая матрица мультнграфа 6, строками которой являются вентер-цнклм С(!ч), 1=1, 2, ..., т, то нэ столбцов матряци С(6), согмвегствуюших ребрам, не вошедшнм,в остсаное дерева у, мажяо составнть диагональную квалратную матрнцу порядяа т(6), элсменгм главной дпаюналп которой прпваллежат множеству ( — 1, 1) (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
