Дискретная математика (998286), страница 13
Текст из файла (страница 13)
Множество максимальных независимых подмножеств множества Х обозначим Х. Рассмотрим следующее утверждение: М»: чХ (УЕХйЯЕХ=Ь(У(=)Я)) то есть максимальные независимые подмножества данного множества равно- мощны. ТЕОРЕМА Пусть М = (Е, Е) и выполнены аксиомы Мг и Мг. Тогда аксиома Мз и утверждение М» эквивалентны, то есть (А, В Е Е Й ~В) = Щ + 1 =Ь 3е Е В,'1 А А О (е) Е Е) тогда и только тогда, когда 'э'Х (У, Я Е Х =~ Щ = Д). Доказательство Необходимость. Пусть выполнены утверждения Мы Мг, Мз (то есть М вЂ” матроид).
Покажем от противного, что выполняется и М». Пусть У, Я Е Д;„~У( ~ Д,и для определенности Щ > ~Я1 Возьмем У' с У, так что (У'~ = )Я) + 1. Тогда по свойству Мз имеем: 3е Е У' 12 Иг: = Я О (е) Е Е. Таким образом, имеем И' Е Е, Я С И", И' С Х, что противоречит предположению Я Е Х. Достаточность. Пусть выполнены утверждения Мы Мг, М». Покажем от противного, что выполняется и Мз.
Возьмем А, В и Е, так что )В! = ~А) + 1. Допустим, что Зе Е В'1А А0(е) б Е, то есть с'е Е В'1ААО(е) ф Е. Рассмотрим С:=АОВ. Имеем А е С. Но В Е Е, поэтому Э В' В с В' й В' и Е й В' и С. По условию М» имеем (В'~ = )А~. Но ~А! = !В'! > ~В! = )А~ + 1 — противоречие. П 7З 2.7, матронам ЗАМЕЧАНИЕ Таким образом, Мм Мз, Мя — эквивалентная система аксиом матроида. 2.7.3. Базисы Максимальные независимые подмножества множества Е называются базами, или базисами, матроида М = (Е, Е). Всякий матроид имеет базисы, что видно из следующего алгоритма. Алгоритм 2.1. Алгоритм построения базиса матроида Вход: Мзтроид М = (Е, Е).
Выход: Множество В с Е элементов, образующих базис. В: = о ( вначале базис пуст ) Гог е и Е ао Ы В О (е) и я тйеп В: =ВО (е) ( расширяем базис допустимым образом ) епа К епд гог ОБОснОВАние Алгоритм вычисляет базу матроида М. Действительно, пусть Во = я~, Вы...,Вь =  — последовательность значений переменной В в процессе работы алгоритма. По построению т'1 В, Е Е. Пусть В и' Е, то есть В не является максимальным.
Тогда ЭВ' В С В'йВ' ~ 7В ВйВ' е Е. Возьмем В" с В', так что (В"! = )В(+ 1, В с В" и В" и Е. Рассмотрим е е В' ~ В. Элемент е не попал в множество В, но алгоритм просматривает все элементы, значит, элемент е был отвергнут на некотором шаге й тоесть (В; 1 О (е)) ф Е. Но е е Вн й В; 1 С Вв =» (В; 1 0 (е)) е Е. По аксиоме Мз имеем: (В;, 0 (е)) е Š— пРотивоРечие.
П СЛЕДСТВИЕ Все базы матроида равномощны. 2.7.4. Ранг Мощность максимального независимого подмножества данного множества Х называется рангом множества: т(Х): = шах (А(. АСХЙАЕЕ ЗАМЕЧАНИЕ Это определение корректно, потому что все максимальные независимые подмножества данного множества равномошпы. ЛЕММА Х ЕЕ йУ Е Х =» Х = У. Доказатппаства Х с ХйХ е ЕйУ е Х=» Х с У с Х =» Х = У, Глава 2. Алгебраические структуры теОРемА Х е Е е=ь т(Х) = (Х1 Доклзатвльство Х е Е е=ь (Х н Е АУ б Х =~ Х = У) о=э (т(з) = (Х~). ТЕОРЕМА ЧА, В С Е Чем ез Е Е В1. О<т(А) <(А( Вз. А < В =э т(А) < т(В) Вз.
т(А0В)+т(АПВ) ~< т(А)+т(В) Вч . т(А) < т(А 0 (е)) < т(А) + 1 Вз . т.(А 0 (е1)) = т(А 0(ез)) = т(А) =Ф т(А 0(еыез)) = т(А) Доказательство Вз . очевидно; Вз . 'очевидно; Вз: Пусть (еы..., е;) Е А П В. Тогда (еы..., ео д„..., и' ) Е А и затем (е„...,еоп„...,пу,с„..., сь) Е А Г1 В. Имеем э' = т(А П В), В*+у ы т(А), э' + й < э + т' + и = т(А 0 В) =ь т(А 0 В) + т(А П В) = (э' + з + к) + э = = (э'+ у) + (э' + й) < т(А) + т(В); Ва .
.очевидно; Вз . 'т(А) < т(А 0 (еы ез)) = т(А 0 (е1) 0 (ез)) < т(А 0 (ез)) + т(А 0 (ез))— -т((А 0 (е1)) Г1 (А 0 (ез))) = т(А) + т(А) — т(А) = т(А). П 2.7.5. Жадный алгоритм Пусть имеются конечное множество Е„(Е~ = и, весовая функция и: Е + К+ и семейство Е с 2н. Рассмотрим следующую задачу: найти Х е Е, такое что гл(Х) = шах ге(У), где в(Я): = ~ ы(е). езсе Другими словами, необходимо выбрать в указанном семействе иодможество наибольшего веса.
Не ограничивая общности, можно считать, что гл(е,) » гп(е„) > О. Рассмотрим следующий алгоритм. Алгоритм 2.2. Жадный алгоритм Вход: миожество Е = (еы,е„), семейство его подмножеств б и весовая функция ы. Множество Е упорядочено в порядке убывания весов элементов. Выход: подмножество Х. 75 2.7. Матроиды Х:=ш ( вначале множество Х пусто ) Гогг ггот 1 го и оо К Х 0 (ег) и б СЬеп Х: = Х о (ег) [ добавляем з Х первый подходящий элемент ) еюи$11 епа Гог Алгоритм такого типа называется жадным. Соверешенно очевидно, что по построению окончательное множество Х Е Е.
Также очевидно, что жадный алгоритм является чрезвычайно эффективным: количество шагов составляет 0(п), то есть жадный алгоритм является линейным. (Не считая затрат на сортировку множества Е и проверку независимости Х о (ег) Е Я.) Возникает вопрос: в каких случаях жадныи алгоритм действительно решает задачу, поставленную в начале раздела? Пример Пусть дана матрица 7 5 1 3 4 3 2 3 1 Рассмотрим следующие задачи. 1. Выбрать по одному элементу из каждого столбца, так чтобы нх сумма была максимальна. Нетрудно видеть, что жадный алгоритм выберет следующие элементы: »7» [5» 1 3 4 ДЗ 2 3 1 которые действительно являются решением задачи. 2. Выбрать по одному элементу из каждого саюлбца и из 'каждой строки, так чтобы их сумма была максимальна.
Нетрудно видеть, что жадный алгоритм выберет следующие элементы: Д7 5 1 3 Д4 3 2 3 [1» которые не являются решением задачи, поскольку существует лучшее решение: Д7 5 1 3 4 (3» 2 ПЗ 1 ТЕОРЕМА Если М = (Е, Я) — матроид, то для любой функции ш жадный алгоритм находит независимое множество Х с наибольшим весом; если же М = (Е, б) не является матроидом, гпо существует такая функция ш, что множество Х, найденное жадным алгоритмом, не будет максимальным.
Глава 2. Алгебраические структуры До Пусть М = (Е, Я) — матрогщ, и пусть Х = (хы..., хь) — множество, построенное жадным алгоритмом. По построению ю(хт) » ю(хэ) > О. Согласно алгоритму 2.1, Х вЂ” 'база М. Пусть теперь У = (ры...,р ) б Я вЂ” некоторое независимое множество. Имеем тп < )с, так как Х вЂ” база.
Покажем, что ю(р;) < ю(х;). От противного. Пусть ю(р;) > ю(х;). Рассмотрим независимые множества А = (хы, ..,х; т) н В = (ры...,р; ыр;). Имеем Лт' < т' (хы...,х, ыр-)— независимое множество. Тогда и(Р1) > ю(Р;) > ю(х,) =~ ЗР < 1 ю(х,) > . -3-ю(х„т) > ю(Р1) > ю(хр), что противоречит тому, что хр — элемент с наибольшим варом, добавление которого к (х„..., хр т) не нарушает независимости. Следовательно, 'т'1 ю(р;) < ю(хт) =э ю(У) < ю(Х) Обратно. Пусть М = (Е; б) не является матроидом. Если нарушено условие Мэ, то есть ЗА,В А с В б Я, но А ф Я, то определим функцию ю следующим образом: 1 , еслиебА; ю(е): = О, если е ЕЕ~А. Тогда А ф Е =э А ф Х =~ ~Х~ < )А~. Если же условие Мэ выполнено, но нарушено условие Мэ, то ЗА В ~А~ = кй)В~ = к+ 1 и т'е б В 1 А А О (е)— зависимое.
Пусть р: = ~А Г1 В1 Тогда р < к. Выберем число е так, что О < е < 1/(й — р). Определим функцию ю следующим образом: 1+ е, если е б А; ю(е) = 1, если ее В'1А; О, в остальных случаях. Заметим, что при таких весах жадный алгоритм сначала выберет все элементы из А и отбросит элементы В 1 А В результате будет выбрано множество Х, вес которого меньше веса множества В.
Действительно, ю(Х) = тп(А) = Й(1 + е) = (Й вЂ” р) (1+ е) + р(1 + е) ~~ <(й — 1Н1+ЧЯ-р))+р(1+с) =(й — р+1)+р(1+ ) = (В) ЗАМЕЧАНИЕ Тот факт, что семейство б является ыатрнодом, означает, что для решения поставленной экстремальной задачи можно применить жадный алгоритм, однако нэ этого пе следует, что не может существовать еще более эффективного алгоритма. С другой стороны, если семейство Я не является матрондом, то это еще пе значит, что жадный алгоритм пе пайдет правильного решения — эсе зависит от свойств конкретной функции ю. Комментарии ОТСТУПЛЕНИЕ Жадные алгоритмы н их свойства были исследованы сравнительно недавно, но их значение в практике программирования чрезвычайно велико. Если удается свести конкретную экстремальную задачу к такой постановке, где»пюжестао допустимых вариантов (из которых нужно выбрать наилучший) является матроидоы, то а большинстве случаев следует сразу применять жадный алгоритм, поскольку он достаточно эффективен а практическом смысле.
Если же, наоборот, оказывается, что множество допустимых вариантов не образует матроида, то это «плохой признак». Скорее всего, данная задача окажется трудпорешаемой. В этом случае целесообразно тщательно исследовать задачу для предаарнтелыюго получения теоретических оценок сложности, чтобы избежать бесплодных попыток «изобрести» эффективный алгоритм там, где это па самом деле невозможно.
2.7.6. Примеры матроидов Ниже приведены некоторые примеры матроидов, встречающихся в рассмотренных областях дискретной математики. В последних главах книги имеются дополнительные примеры матроидов, связанных с графами. 1. Свободные матроиды. Если Š— произвольное конечное множество, то М = (Е,2в) — матроид. Такой матроид называется свободным. В свободном матроиде каждое множество независимое, г(А) = (А~. 2. Матроиды разбиений. Пусть (Еы..., Еь) — некоторое разбиение множества Е на непустые множества.
Другими словами, ( )г Еь = Е, Е; й Е = Э, Еу ф И. ь Положим Я: = (А С Е ~ )А й Е,~ < Ц, то есть в независимое множество входит не более чем один элемент каждого блока разбиения. Тогда М = (Е,Я)— матроид. Действительно, условие Мг выполнено. Если А, В е Я и )В( = )А(+1, то 3» (Е Г1 А~ = Ой )Е Г1 В( = 1. Обозначим е: =Е О В. Тогда А 0 (е) Е Е. Значит, выполнено условие Мз. 3. Векторные пространства. Линейно независимые множества векторов любого векторного пространства образуют матроид. Действительно, условия Мг и Мг', очевидно, выполнены для линейно независимых множеств векторов. Условие М« выполнено по теореме подраздела 2.5.4.
4. Матроид трансверсалей. Пусть Š— некоторое множество, и Я вЂ” семейство подмножеств этого множества (не обязательно различных), Е с 2~. Подмножество А с Е называется частичнаой трансверсалью семеиства Я, если А содержит' не более чем по одному элементу для каждого подмножества Е; семейства Е. Частичные трансверсали над Е образуют матроид (см. (141) Комментарии Так же как и в предыдущей главе, сведения, изложенные здесь, настолько общеизвестны, что конкретные ссылки ниже следует рассматривать как примеры, а не как единственно рекомендуемые источники., Конкретные алгебраические Глава 2.
Алгебраические структуры структуры разделов 2.3-2.6 описаны в [1О, 12, 22). Книги'[22] и [12] могут быть использованы как введение в общую алгебру (разделы 2.1-2.2); первая иэ них вполне элементарна. Монография [3) исчерпывающим образом освещает важные для приложений вопросы, бегло затронутые в подразделе 2.6.5. Особого внимания заслуживает материал последнего раздела главы, который (с некоторыми сокрашениями) следует книге [14). Упражнения 2.1.
Является ли группа целых чисел (Е;+) конечно-порожденной? Какова ее система образующих? 2.2. Пусть А:=(А;г") и 3:=(В;д) — две алгебры типа (2). Тогда алгебра 6: = (С; й) называется прямым произведением алгебр А и 3 (и обозначается 6:=А х 3), если С = А х В и операция й: С х С + С определена следующим образом: й((ат, Ьт)(аю Ьэ)): =(з (ат, аэ), р(Ьтт Ьг))- Пусть 3:=А х А. Доказать, что существуют гомоморфизмы а: А -ь 3 и 13: 3 -+ А, такие что а о В: А ~ А — тождественная функция. 2.3.
Пусть Е: = (ах + Ь | а, Ь е )й) — множество линейных функций. Операция линейной замены переменной определяется следуюшим образом: (ах + Ь) о (сх + сЕ): =(а(сх + с() + Ь) = (ас)х + (ас(+ Ь)). Доказать, что множество линейных функций образует группу относительно линейной замены переменной. 2.4. Пусть на множестве пар вещественных чисел )йэ определены операции Е Э. Кэ х)йз >1тэ следующим образом: (а, Ь) йс (с,с(): =(а+ с,Ь+ с() и (а, Ь) ® (с,с(): =(ас, Ьд). Доказать, что Х:=(Из;®,Э) образует коммутативное кольцо. 2.5. Поле 3': =(Р;+, ) называется упорядоченным, если существует такое подмножество Р носителя Р, что для любого элемента х е Р выполняется одно и только одно из следующих трех утверждений: х Е Р ~ (О), х = 0 или — х 6 Р 1 (0).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
