В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 19
Текст из файла (страница 19)
С л е д с т в и е 24.4, В непустом графе 6 имеется реберно непересекаюи1ихся остовов тогда и только тогда, когда любой его остовиый подграф удовлетворяет неравенству (10). Следствие 24.5. Для того чтобы непустой граф С был объединением не более чслс 1 своих остовов, не имеюисих обисих ребер, иеобходилсо и достаточно выполнение условия (11) для любого его остова Н. Аналогично введенному выше понятию объединения матроидов моясно ввести попятие их пересечения. Пусть ЛХ,=(Е, У,) (1=1, )с) — й матроидов на множестве элементов Е с наборами независимых множеств Уь Пару и ЛХ=(Е, У), гдеот = Д .У;, назовем пересечением матроите-т дов М; (1'= 1, 1с) и обозначим ЛХ = Й ЛХсь 1=1 Разумеется, пересечение матроидов также может оказаться матроидом. Например, пересечение тривиального матроида и любого матроида с тем ясе множеством элементов есть тривиальный матроид.
Но, как правило, пересечение матроидов ЛХ пе является матроидом с набором независимых множеств У, поскольку .У монсет пе удовлетворять аксиоме независимости 1.2. Например, пересечение двух матроидов Мс =(Е,,Ус) и Мг=(Е, Уг), где Е = — (1, 2, 3, 4), Ус = (9, (1), (2), (3), (4), (1, 3), (1, 4), (2, 3), (2, 4Н, Рг=(0, (И, (2), (3), (4), (1, 2), (1, 4), (2, 3), (3, 4)), не есть матроид, так как множество 7$ 99 , ) П, т (8, ((), (2), (3), (4), ((, 4), (2, ЗИ не удовлетворнет условию 1.2.
В $ 28 читатель столкнется со следующей задачеи: Задача о пересечении й матроидов. Даны й матрондов на одном и том же множестве элементов Е. Требуется найти в Е наибольшее по числу элементов подмножество, являющееся независимым множеством каждого из заданных матроидов, Пусть, например, заданы два графа С п И, причем 1ЕС~ = ~ЕН~ =- т.
Пусть ребра этих графов занумерованы с помощью одних п тех нге меток: ЕС =ЕН=(1, 2, ... ..., т). Очевндно, что задача нахонсдення в Е наибольшего по числу элементов подмножества, не содержащего циклов ни первого, нн второго графов, и есть задача о пересечении двух графических матроидов М(С) н М(Н). Задача о пересечении лишь двух матроидов стоит особняком: она эффективно решается методом чередующихся последовательностей (см., например, (25)).
Идея этого метода демонстрируется в з 77. При й ) 2 задача о пересечении й матроидов становится очень трудоемкой. Даже для решения ее простейшего варианта — задачи о пересечении трех матроидов разбиений — не найдено, и скорей всего не существует, эффективных алгоритмов. У П Р А )К Н К Н И Я П Пусть М вЂ” матроид порядка н. Покажите, что число его баз п не превосходит ( )), а число его циклов не превосходит (р(м) +)) 2. Пусть М = (Е, ) — матроид с набором независимых множеств , йл ье А ш Е. Пусть, далее, ' = (Хли.
: ХНА = йл). Докажите, что М' = (Е, . ') — матроид с набором независимых множеств '. Ма тренд М' называется сужением матраида М иоередетеолл А. 3. Пусть в обозначениях предыдущего упражнения " = = (Х П А: Х ш, ). Докажите, что М" = (Е, ") — матроид с набором независимых мноисеств, ". Матроид М" называется ограничением матреида М на А 4. Пусть Š— непустое конечное множество, й ~ (Е(. Докажите, что множество Я всех й-элемептных подмножеств множества Е удовлетворяет аксиомам баз и, следовательно, (Е, м)) — матроид.
Его вазьлвают однородным матреидем ранга й. 5. Пусть )) — ориентированный граф, и пусть Е и У вЂ” два непересеттающихся подмноясества его вершин. Подмножество А ш Е называется независимым, если существует )А) вершинка непе- 100 ресскагощихся простых орцепей из А в У. Докажите, что этп независимые множества задают некоторый матроид. 6. Пусть М вЂ” матроид с рангозой функцией р. Донажите, что для любого подмножества А его эломентов р*(А) = (А) + р(А) — р(М), где р* — корапговая функция матроида ЛХ. 7.
Для каких й и и существуют однородные матроиды порядка п и ранга?г, являющиеся матроидами циклов некоторого графа? 8. Исследуйте цинлическио матропды М(К2) и М(Кзл). Докажите, что они пе нвляются кографическимп. 9. Покажите, что с тошостью до изоморфизма число матронах дов порядка и не превосходит 2 10. Охарактеризуйте графы, матроиды циклов и разрезов которых изоморфны. 11. Покажите, что с точностью до изоморфизма существует ровно 4 матронда порядка 2 и 8 матроидое порядка 3. Сколько среди пих представимых над каким-либо полем? 12.
Пусть М1 и ЛХ2 — матроиды па множестве Е с ранговыми функциями р~ и р2. Докажите, что М2 и Ме имеют общее независимое множество мощности?г тогда и только тогда, когда р2(А) + + 62(А) >?г Для люоого А д Е. 13. Докажите, что кангдый однородный матроид является трапсвсрсальным. 14. Докажите, что трансверсальпые матроиды и только онп представимы в виде объединений матроидов ранга 1. 15. Докажите, что циклический матроид М(К,) не является трапсверсальным. 16. Докажите, что матроид, двойственный к трапсвсрсальпому, пс обязательно является трапсворсальным. 17. Докажите, что с точностью до изоморфизма число трапсп2 нереальных матрондов порядка и не превосходит 2 18.
Необходимо выполнить па ЭВМ множество заданий. Вес задания требугот для выполнения одинанового времени. Каждому из заданий присвоен краинпй срок выполнения. а) Покажито, что набор всех подмножеств заданий, которые можно выполнить с соблюдением сроков выполгюния, образует набор независимых подмножеств некоторого матроида. б) Допустим, что за каждое пе выполпснноо в срок аадание пообходимо ааплатить штраф, величина которого одинакова для всех заданий. В каком порядке следует выполнять задания, чтобы общий штраф был минимальным? 10. Пусть ЛХ вЂ” иатроид, элементам е которого приписаны пеотрицатсльпыо веса ю(е).
Докажите, что гп1п гпах ю(е) = игах ш1п ю(е), хыЯ и~Х уын'х хыу где Я вЂ” моо:когтзо оаз патроида ЛХ, егх —. множество коциклов ма- троида ЛХ. Глава 1'г' Независимость и покрытия Во многих прикладных задачах требуется найти в конечном множестве объектов максимальную систему объектоз, попарно не связанных друг с другом, или же выбрать минимальную систему объектов, связанных со зсеми другими.
Формулировки подобных задач на языке теории графов приводят к понятиям независимости и покрытия. $25. Независимые множества и покрытия Мяожестзо зоршин графа называется независимым (плп анутрютнс устойчивым), если никакие две вершины из этого множества не смежны. Иными словами, если Я вЂ” )тС и Я независимо в графе С, то порожденный под|раф С(Б) язляется пустым.
Очевидно, что если при этом Я' ~ Я, то Я вЂ” также пезазисимое множество. Независимое множество называется максимальным, сслп опо пе язляется собственным подхгпогкеством некоторого другого неаавпспмого мпожестза. Наибольшее по мощности нозазиспмое множество называется наибольизим. Испо, что наибольшее яезависимое множество является максимальным. Обратное, вообще говоря, неверно. Н отыскашпо паиболыпего независимого множества зершпп з графе сводится, например, известная задача о восьми ферзях, которую саязыза1от с именем Н. Гаусса.
Задача о восьми ферзях: требуется так расставить на шахматной доске наибольшее число ферзей, чтобы опп пе атаковалп друг друга. Таких ферзей, очевидно, может быть пе более восьми, так как никакие дза пз пих по должны находптьсн на одной зортпиалп илп горизонтали.
Рассмотрим граф, ворппшы которого соответствуют клеткам доски, а ребра— парам клеток, лежащих на одной вертикали, горизонтали пли диагонали. Ясно, что требуемой в задаче расстановке ферзей соответствует наибольшее независимое множество 102 в этом графе. Одно из решений задачи о восьми ферзях показано на рис. 25.1. т1исло вершин в наибольшем независимом множестве графа С нааываетсн числом независимости (числом внутренней устойчивости, неплотностью) этого графа и обозначается через ас(С). Например, длн графа С, изображенного па рпс.
25.2, ас(6)=4, множества вершин (1, 2, 3, 7), 11, 2, 3, 8), (2, 3, 5, 7) и (2, 3, 5, 8) явлкются наибольшими независимымп, а (4, 7) — максимальное псзаьпспмоо множество, не нв.ппощееся наибольшим, Содержанием большинства задач, связанных с понятием независимости, явлнются определение числа пеза- в Рпс. 25.2 Рпс. 253 впсимости и отыскание наибольшего независимого множества. Эти задачи, как правило, очень трудны, и потому для их решоппя оказываются полезными оценки числа независимости. Теорема 25.1. Для любого графа С верно неравенство а,(6)) ~~э„(1+ с(за о) — ц > Если С вЂ” полный граф, то в (1) пмсст место равенство.
Поэтому не теряя общности будем считать, что СФК„. Воспользуемся ипдукцией по числу вершин графа С. В справедливости неравенства (1) для графов порядка п ~ 2 легко убедитьсн непосредственно. Пусть теперь ~ ГС~ = п ) 2 и длп всех графов порядка, меньшего чем п, неравенство (1) верно. Выберем в графе С вершину х минимальной степени. Так как СчьК„, то х 0 Х(х)Ф РС. Пусть С = С вЂ” (х 0 Ж(х) ) . Согласно индуктивному пред- 103 положению для графа 6' верно неравенство, апалогнчноо неравенству (1) . Пусть Лу' — наибольшее независимое множество вершин графа 6 . Ясно, что мно.кество ЛХ= = Л1' Б х независимо в графе 6, и для доказательства теоремы достаточно показать, что от = ~ (1+ додав)- (Яг = ~~', (1+ додо о)-~ + 1.
ануа теуо' Обозначим через ч множество вершин графа С', каждая нз которых смшкна в С с какой-либо вершиной нз Х(х) (см. рис. 25.3). Очевидно, что слагаомые и Яь соответствующие верпшнам и из С, меньше аналогичных слагаемых в ом а слагаемые в д! п он соответствующие вершинам и из г'С ~9 совпадают. Стало быть, достаточно показать, что 1 х 1+ дед х чз + зг~ (1+ дедов)-'(1. т==щ х) (2) Согласно выбору вершины Рас. 25.3 х для любой вершины у из Л'(х) имеем деда х ~ деда у. Постону левая часть неравенства (2) является суммой (1+дедах) слагаемых, пе превосходящих (1+дед,х) и, следовательно, пе превосходит 1. <3 Пусть д= — ~ деди 1 тнго — среднее арифметическое степеней грофа 6. Следствие 25.2. Для епобого графа 6 порядка п верно неравенство пв(6) ) —, > Известно неравенство Коши — Пупяковского: для любых а„Ь,- О.
Полагая а;=1+дедов Ь;=(1+деде;) ', ц;шРС, 104 получим (1+ дед о)) ( ~ (1+ Йедо) — ~) ) и. ( —,: )(ж Последнее неравенство вместе с неравенством (1) приводит к соотношениям (1+ доя и) 1+" ю=-~ о По существу, доказательство теоремы 25.1 дает простой алгоритм построения независимого множества ЛХ такого, что ! ЛХ ~ ) ~х (1 + бед э) еыгн Это мнояссство строится следующим образом: каждый раз в графе выопрается вершина минимальной степени и заносится в множество М. Затем эта вершина и все смежные с ней удаляются из графа и процесс продолжается.
Как уже отмечалось, задача отыскания наибольшего независимого множества вершин в графе очень трудна для алгоритмического решения. Поэтому множество М, построенное описанным выше способом, иногда принимают в качестве ее приближенного решения. Что можно сказать о точности такого решения, пли, иначе говоря, как далеко величина ~ (1+перо) ' может отстоять от ъеуо иэ(6)? Ниже показано, что отношение первой из этих величин ко второй может быть сколь угодно малым числом, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
