В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 11

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 11)

Поскольку алгебраические дополнения всех элементов матрицы В(6) равны (утверждение 6.2), то теорема доказана. < уз и — 1 — 1... — 1 и — 1... В(К„) = — 1 — 1 п — 1 занимагощего познциго (1, 1). Опо равно опродегштелю п — 1 — 1... — 1 — 1 и — 1... — 1 — 1... п — 1 порядка и — 1.

Далее имеем 1... А — 1п — 1... — 1 11 = 11...1 О и ... О О О ...и и-г — 1 — 1...п — 1 Очевидно, что число остовов в К равно числу помеченных деревьев порядка и. Поэтому предыдущее следствие можно сформулировать в виде следующей теоремы, впервые получопной А. Кали в 1897 году. Т с о р е м а К э л и. Число помеченных деревьев порядка и равно и" '. 5 15. Остов минимального веса Рассмотрим следующую задачу: во взвешенном связном графе требуется найти остов минимального веса.

Эта задача возникает прп проектировании линий электропередачи, трубопроводов, дорог и т. п., когда требуется за- бэ С л е д с т в и е 14.2. Длл числа компонент п-вершинного графа 6 верно равенство й(6) = и — гапй В(С). ь Если граф С связен, то в нем есть остовпое дерево. Согласно предыдущей теореме гап)гВ(6)) и — 1. С другой стороны, всегда де1 В(6) = О. Следовательно, гап)г В (С) = п — 1. Пусть теперь граф С имеет ровно й компонент. Тогда при подходящей нумерации вершин матрицей В(6) служит клеточно-диагональная матрица йая [Вн Вг, ..., В,[, диагональные клетки которой В; являются матрицами Кирхгофа соответствующих компонент. Учитывая уже доказанное, имеем гапй В (6) = и — )г. 0 Следствие 14.3.

11ри и) 1 число остовов в полном графе К„равно п" г. ь Рассмотрим алгебраическое дополнение Л~~ элемента матрицы дапнь<е центры соединить некоторой системой каналов связи так, чтобы л<обые два центра были связаны либо непосредственно соединяющим пх каналом, либо через другие центры и каналы, и чтобы общая длина (пли, например, стоимость) каналов связи была мннимальнои. В этой ситуации заданные центры мои<«о считать першинамн полного графа с весамп ребер, равнымп длинам (стоимости) соедипя<ощих эти центры каналов. Тогда искомая сеть будет кратчайшим остовным подграфом полного графа.

Очевидно, что этот кратчайший остовный подграф должен быть деревом. Поскольку полньш граф К содержит Р-г различных остовнь<х деревьев, то решение этой задачи «слепым» перебором вариантов потребовало бы чрезвычайно больших вычислений даже при относительно малых и. Однако для ее решения имеются эффективные алгоритмы.

Опишем два ич них — алгоритмы Дж, Краскала (1956 г.) и Р. Г!рима (1957 г.), применимые к произвольному связному графу. Задача об остове минимального веса (о кратчайшем остове): в связном взвешенном графо (С, <о) порндка и найти остов минимального веса.

Алгоритм Краскала, решающий эту задачу, закл<очается в следующем. 1. Строим граф Т, = О„+ е<, присоединяя к пустому графу па множестве вершин Г<С ребро в< ~ КС минимального веса. 2. Если граф Т< уя е построен п <( и — 1, то строим граф Ти < — — Т<+ в,»<, где е,»< — ребро графа С, нме<ощее минимальный вес среди робер, не входящих в Т< п пе составляющих циклов с ребрамп из Т,. Следующая теорема утверждаот, что алгоритм Краскала всегда приводит к остову минимального веса. Теорема 15.1, Пра <( и — 1 граф Т„< можно построить. Граф Т„< является остовом мшшмального веса в графе (С, <о).

<> граф Т< имеет ровно < ребер и потому при < ( и — 1 является несвязных<. А так как граф С связен, то в пем есть по' меньп<ей мере одно ребро, не составляющее циклов с ребрами графа Ть Итак, нужное ребро е<»< существует и граф Т,»< можно построить. Рассмотрпм граф Т„<. Поскольку Т„< является (и, и — 1)-графом без циклов, то согласно теореме 13.1 зго дерево.

Остается доказать, что вос дерева Т„, минимален. Предположим, что это пе так, я среди всех остовов графа С минимального васа выберем такой остов Т, ко- 60 тарый нмеет с деревом Т ! максимальное число общпх ребер. Пусть е; = аЬ вЂ” ребро дерева Т„п пе содернтащееся в Т и имеющее мнннмальный номер среди ребер дерева Т ь не входящих в 7' (напомним, что в процессе построения дерева Т ! его ребра получили номера 1, 2, ..., и — 1). В дереве Т есть простая (а, Ь)-цепь, Прпсоедннив к ней ребро еь получпм цпкл.

В этом цпкло ость ребро е, пе входящее в дерево Т ,. Заменив в дерево Т ребро е па еь получим новый остов Т' = Т вЂ” е + еь По Т вЂ” остов мннимального веса, слодовательпо, !а (Т') = = ш(Т) + и (е,) — и (е) ) !а(7' ), т. е. !а(е,) ~ ж(е). (1) С другой стороны, присоединяя ребро е к Т; ! (прн 1= '1 полагаем Т, ! = О ), мы не получим цпкла, поскольку робра еь ею ..., е, !, е входят в дерево 7, н потому., если бы вес ьт(е;) был болыпе, чем !а(е), мы взялн бы прн построенни дерева Т, ребро е вмосто е;.

Из (1) теперь следует, что в(е,) = !а(е), !а(Т') = ю(Т). Итак, Т' — остов минимального веса. Число ребор, общпх для деревьев Т' и Т, !, больше, чем число ребер, общнх для Т н Т „что протнворепгг выбору дерева Т. Полученное противоречие н доказывает теорему. < В качестве иллюстрации рассмотрим взвешеппьш граф, изображенный па рнс. 15.1, а. Полагаем е! =(1, 4), еа = = (4, 5). Среди оставшихся ребер минимальный вес имеет, например, ребро (1, 5). Однако оно не пригодно для построения, поскольку составляет цикл с двумя предыду- а Е Рис.

!5.1 щимп ребрамн. Можно взять ез = (2, 3), е4 = (2, 5). Итак, ребра (1, 4), (4, 5), (2, 3), (2, 5) составляют остов минимального веса (рнс. 15.1, б) ) . Ллзоритм 11рима отлпчастся от алгоритма Краскала только тем, что на каждом этапе стронтся не просто ацнклпчоский граф, но дерево.

Именно: 1. Выбпраем ребро е~ = аЬ минимального песа п строим дерево Ть полагая ('Т! = (а, Ь), КТ! =- (е!). 61 2. Если дерево Т, порядка 1+ 1 уже построено и 1( и — 1, то среди ребер, соединяющих верп1ины этого дерева с вершинамп графа 6, ие входящими в Ть выбираем ребро е,ы минимального веса. Строим дерево Тгьь прпсоедипяя к Т; ребро е;„1 вместе с его яе входящим в Т, концом. Для этого алгоритма также верпа теорема 15.1, доказательство которой аналогично приводепному выше. В некоторых ситуациях требуется построить остов не минимального, а максимального веса. К этой задаче также применимы и алгоритм Краскала, и алгоритм Прима.

Следует только всюду миппмальпьш вес замепить макспмальпым. С задачей об остове минпмальпого веса тесно связана задача Штейиера. Первоначальпо она формулировалась как следующая Евклидова задача Штей~ера: произвольиое множество У точек евклидовой плоскости требуется соединить непрерывными линиями так, чтобы любые две точки были связаны либо пепосредствепио соединяющей пх липиса, либо через другие точки и соединяющие пх липки, и чтобы сумма длил линий была минимальной. Множеству точек У можно поставить в соответствие полпый граф К(У), вершинами которого будут элементы У, а вес каждого ребра будет равен расстоянию мезкду соответствующими точками. Евклидова задача Штейпера отличается от задачи построепия остова минимального веса в графе К(б7) тем, что в этот граф разрешается вносить новые вершипы— точки Штейпера.

Их можно добавлять столько, сколько потребуется, чтобы дерево, пх соединяющее, имело минимальный вес. Если в предыдущей задаче в качестве расстояния между точками (хь у~) и (хм уз) взять величину ~х1 — хз! + + ~у1 — уз~, то получится прямоузольпая задача Штейнера.

Зта задача сводится к следующей широко известкой задаче. Задача !Птейпера па графах. В связном взвешенном графе С с выделеппым подмножеством вершил У': — 'г'6 требуется иайти связный подграф Т, удовлетворяющий следующим двум условиям: 1) мпожество ГТ содержит заданное подмножество У; 2) граф Т имеет минимальный вес среди всех подграфов, удовлетворяющих условию 1). 62 Очевидно, что искомый подграф является деревом. Он называется деревом Штейпера.

Очевидно такяге, что задача построения дерева Штейнера эквивалентна задаче нахождения остова минимального веса в порожденпых подграфах графа С, множества вершин которых содержат 1.г. Какие-либо эффективные алгоритмы, решающие задачу Штейпсра, кеизвестшл. У П Р Л Х( П Е Н И Я 1. Нарисуйте все попарно псизоморфпыо деревья седьмого порядка. 2, Найдите дерево минимального порядка и ~ 2 с тогкдественной группой автоморфизмов, 3.

Докажите, что центр дерева состоит из одной веригины в случае, когда диаметр этого дерева лвляетсн четным числом, и па двух смежных вершин, когда диаметр — число нечетное. 4, Докажите, что радиус г(6) и диаметр г/(6) любого дерева 6 связаны соотношением г(С) = ) д(6)/21. 5. Верно ли, что осли диаметр связного графа С равен й (л ) 2), то в С существует остовпое дерево, диаметр которого также равен й? б. (и, та)-граф называется вбалаавпрсванвыл, если пинакой его подграф пе имеет вершин степени большей, чем 2т/в. Покагьчгтс, что всякое дерево при а - 2 — несбалансированный граф. 7. Найдите остоваые деревья в Кв Квл и в графе Петерсена, 8. Докавситс, что подграф Н графа С являетсн в С остовом тогда и только тогда, когда верны равонства (Н) = (6(, т(Н) = = )6) — Ь(6), Ь(Н)'= й(6) 9.

Используя матричную теорему Ккрхгофа, найдете число остовных деревьев в полном двудольном графе К 10, Докажите, что число помеченных двудольных деревьев с числами всргпин в долях т и п равно лг" 'лм ', 11. Покажите, как найти остов графа с помощью поиска в ширину. 12, Постройте такое множество Н точек на плоскости, длл которого вес дерева Штейнера был бы меньше асса любого остовпого дерева графа К(С), Глава 1!1 Матроиды и трансверсали В этой главе вводится новый комбипаторный объект— матроид, появляющийся в результате оообщения хорошо известного читателю понятия ляпеш<ой зависимости. Хотя понятие «матроид» возникло относительно давно,— в 30-е годы нашего столетия (впервые это понятие ввел Х.

Характеристики

Список файлов лекций