В.Н. Нефедов, В.А. Осипова - Курс дискретной математики (1127083), страница 45
Текст из файла (страница 45)
Согласна утверждению 4.35 граф 6,+, также ивляетсн деревом. Присваиваем >: =1+1 п переходим к шагу 2. Иример 4.23. Используя алгоритм 4.б, вылепим остовное ле. 'рево графа 6, азображенного на рис. 4.25. Йа рпс. 4.25 приведена последователь. г "з ность графов Сь 1=1, 2, 3, 4, 5, получаемых в результате выполнении алгорит ма 4.б. При атом в силу того, что п(6) =5.
Се†астовнае дерево графа 6. г Замечание 4.8у. Остовиоедерево связного графа может быть выделено, вообще го поря, не едвнственным способом (тем более рве. ядп 210 зто нерво лля связного псевлографа). Обшве число остовных де. ревьев связного графа может оказатьсп весьма бшмшнм. Напра. х»ер, лля полного графа с л вершинами оно рвано л"-'. л, В и „ж », 1 Рв». 4Ж 4.3.3.
Мнмимальвме сстовнме деревьв нагруженнмк графов Пусть теперь каждому ребру «шХ связного графа 6 = (У, Х) с непустым множеством ребер Х поставлена в соответствие величина Цх) — длина ребра х, т. е. «раф С является нагруженным. Првведеы виоритм, позаоляюшнй найти потопное аерево графа С с мнннывлвной суммой длин содсржашяхся в вем ребер (по сравненвю со всемв другнмн ссговнымн дсревьямн графа 6).
Осчовное дерево связного нагруженного графа С с мнвнмальяой суммой лаяв садержашнхся в нем ребер будем называть мнянлальимл сстозныл деревам (МОД) графа С. Алгоршм 4.7 (выделенвя МОД нагруженною связного графа 6 г аг й Выберем в графе С ребро мнннмальвой панны. Вместе с внцодешнымв ему вершннамн оно образует нодграф 6» графа С. Положим! 2. Шаз 2. Есин 1 = и, где и л(6). то задача решена, н ѻ— искомое МОД графа С.
В противном случае переходим к шагу 3. Шез 3. Стронь» граф Смь добавляя к графу 6» новое ребро мнпнмальвой длпьы, выбранное сред» всех ребер графа 6, каждое нз шпорых нншшевтно «акой-ннбуль вершине графа Сг н одновременно ннцвдентко какой-нибудь вершние графа С, не содержашсйся в Сг. Вместе с этны ребром включаеы в 6,+, н кпцндентную ему вершнну, не содержашуюся в С<. Прнсавнваем 1» = 1+ ! н персшдвм к шагу 2. Прнмер 4.33. Опрелелпм МОД нагруженного графа 6, пзображенного ка рвс. 4.27, нсполшуя алгорятм 4.7.
На рнс. 4.23 Приведена цс. г, " »г следовагельность графов 6„1 2, 3, 4, б, валучаемых в результате выполяе- у ння алгорнтыа 46. Прн этом в калу то. г го. что л(С) 3, С» — МОД графа 6. Сбоатаание од»пригов 4.7. Для лю тч 4»Г» бого дерегл Т подграф Т графа Т. в свою очередь являюшнйся деревом, будем Рас 427 т!! ритм 4.7) янляется поддеревом некоторога МОД графа б. Но тогда, снова исиолюуя лемму 4.1, последовательно находим, что каждый нэ графов 6», 6». -., 6„, полученных в результате применения к С алгоритма 4.7, явлнишя поддеревом некоторого МОД графа б, а так как б„содержит все вершины графа С, заключаеы, что 6„— искомое МОД графа 6.
Замечание 4.88. Для выделения МОД нагруженного псевдо- графа С следует предваричельно удвпить нз б петли, из кратных ребер оставить лишь ребра минимальной длины, а затем применить к полученному таким образом графу алгоритм 4.7. 4.3.4. Вектор циклы Пусть б = (У, Х) — некоторый мультнграф, Х (хь ..., х ), шм!. Ввелем произвольно ориентацию длн ребер из Х, т. с. каждое ребро х= (а, и) чыХ превратим в дугу х' такую, чта .чибо з" (а, ю), либо х' (ю, а).
В результате яз исходного мультиграфа 6 (У, Х) нолучнм ориентированный мультиграф О (У, Х'). Всюду в этом разделе будем пользоваться термином «цннл» а более широком смысле, а именноч под циклом будем понимать произвольный замкнутый маршрут. Как и ранее, замкнутый маршрут, в котором все ребра и вервчины попарно различны, будем называть простым циклом. Рассмотрим некоторый цикл и а»уш»у» ...
а»у»и» (4.27) в мультнграфе б, где у, (а»,а„.,)щХ, 1=1, ..., й, 4~2 (при этом о»+,=и,). Запись (4.27) задает направление прохода цикла 1» через каждое ребро у,= (сь щ+ч) (от щ к и»+ч), которое явля. ется для нас весьма существенным, н поэтому далее всюду будем рассматривать циклы с фиксированным направлением прохода через ребра, вхолящне в эчи циклы. Говорят, что цинл р прохопит через ребро у»= (аь и»ы) е направлении ембралнаб ориентации, если уб (аь а»»ч); в противном случае (т. е.
если у', = (о)м, ач)) говорят, что цикл в проходвт через ребро уч з иалааалеиии. нрачивоиохажном выбранной ориентации. Пусть Хи — множество ш-мерных векторов с целочисленными каордннатамн и и — некоторый пнкл в мультнграфе б с выбранным направлением прохода через ребра, входящие в этот пипл. Вектор С(м) щй называсюя вектор-циклам, ссотвечствующим циклу 1» (или просто вектор-инкпом и), если»-я координата С,(М) вектора С(я) равна разности Сь»(М) — С »(и), где с ч(м) — число проходов в цикле 1» через ребро х» в направлении выбранной ориентации, С »(м) — число проходов в цикле д через ребро х, в направлении, противоположном выбранной ориентации.
зчз Пример 4.30. Пусть 6 - (Р, Х) — иультиграф, изображен; ный на рис. 4.29, а. Введем в О ориентацию иа ребрах. В резуль! тате получим, например, ориентированный мультиграф О, изот браженный иа рнс. 4ля, б. Рассмотрим некоторые циклы в О: р, = и,х,о»хзозК»оз; р» = Вхзозсзозхзо<х»озхй!Юо!! рз = о,хзозкзизх!о,кзизхтозхзозх,о»; рз озх озх о> рз о хжзх о, Тогда С(!зз) (1, 1, — 1, О. О, О, О, 0); С(Р»)= ( — 1,— 2,1,0,0,0, 1,1); С(нз) ( — 2,— 2,1,— 1,— 1,0,0,0); с (! ) = (о, о, о, О, о, о, о, о)', ' ' С(Р») (0.0,0,0.0,— 1,— 1,0) Обозначим через О"о мноч ц жсство всех вектор-цнилов *', Ц "з а з' „б з' мультиграфа О.
Пипл р называетсн линей. '» зз ' з~) лб т ной конбинаЦией циклов Рь .-, ее ры если дли некоторых а„..., Ю с/ аьшЯ, где () — множество рациональных чисел, выаолннег ся равенство С(р) а»С(р») + ... + а»С(рь). (423) Вместо (4.23) будем использовать сокращсннузо запись р апи+ ... + азрз. (4.29) Теорема 4.3 (о незанисикости «озффицаентов е линейной конбинизии от ориентации ребер). Пусть для некоторой ориентации ребер еьиюлнлется соотношение (4.29).
Тогда оно сзцюзедлисо и для избой другой ориентации ребер. Запишем равенство (4.23) в координатной форые! С.(р) = С"з(Р) — С »(р) - Х атС»(Р») = з — » В аДС»з(рз) — с з(р!)), (4.30) где !ев(1,, лф. При изменении ориентации ребра кз из (4.30) будет следовать равенство (4 31) С з(Р) Сзз(р) = Х аз(с з(рз) С+з(рз)1 ! а!4 После умножении (4.3!) иа — ! получаем С+г(гг) — С г(р) = 2 пг(Счг(рг) — С г()м)), 1- откуда х Сг(р) = 2 пгСг(рг), т. е. равенство [4.30) имеет место и в втоы случае. Обазначнм через 0 нулевой вектор в 2" [т.
е. 0 (О, ..., 0) гж сп2 ). Система пиклов (рь ..., гм) (где йы!) называется неэлзгпылоп, если соответствующан ей система вектор-циклов линейно незавзсима [т. е. если дла любых пь ., ща6 нз агС(~ц)+... ...-)-о„С(рз) =0 следует ог=...=ах=О). Исиальзун теорему 43, заключаем, что выбор ориентации ребер не влинет на независимасть системы циклов. Отметин, что поснольку 2"ощ[), гле 6 — т-мерное линейное пространство пад полем 6, то максимальное количество элементов в нюависимой системе Пиклое не превышает т. Зшксчошге 4.39.
Нетрудно видеть, что есин (рь ..., Рг) — незавнснмап система пнклов и цикл гны не нвлнстся ее линейной комбинацией, то (рг, ..., рг, югг) — незавнсиман система циклов. 4.3.5. Циничной базис мультнграфа Пусть мы находнмси в условиях рази. 4.34. Независимая система пиклов (рь ..., рг,) называется Наклонил базисом мультнграфа 6, если любой цикл нз 6 является линейной комбинацией циклов этой системы. Рассмотрим вопрос о существовании пнклового базпса мультнграфа 6. Мультнграф 6 будем называть пциклическлл, если либо т=О, либо 2"о= (0) (т. е.
в 6 отсутствуют простые циклы). Очевидно, что в апиклическом мультиграфе нет цнклоаого базиса. С друюй стороны, справелливо утверждение 4 4!. Гсли лузьгчзрпф 6 не эелягтсяпцикаичегкин, то з лем срщеогерег Чикзовоб базис. Пусть р, — произвольный цикн в 6 такой, что С(гг~)тьб, Тогда либо (рг) — циклавой базис, либо в 6 существует цнки ра такой, что он не являетсн линейной комбинацией цикла гч. В последнем случае (см. замечание 4.39) (рь рт) — независимая система циклов. При зтоы снова либо (р„ р,) — цнкловой базис, либо в 6 существует пикл рз такой, что ои ие явлнетсн линейной комбинацией циклов рь рь В последнем случае (рь нп рэ)— иезависимаи система циклов. Вснлутого,что количество элементов в независимой системе циклов не превышает гл, указанный процесс последовательного ее расширения ие является бесконеч- 3!5 ным и па пекотором й-и шаге, где й ж ш, получаем систему цнк.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
