В.А. Носов - Основы теории алгоритмов и анализа их сложности (курс лекций), страница 24

если A∈J, A’⊆ A, то A’∈J). Элементы семейства J называютсянезависимыми.Комбинаторная задача оптимизации для системы подмножеств S=(Е,J)состоит в следующем. Для каждого е∈Е задан его вес w(e)≥ 0 - действительноечисло. Требуется найти независимое множество А∈J, имеющее наибольший вес133W(A)= ∑ w ( e )e∈AЯсно, что рассмотренные выше задачи α) и β) принадлежат данному классуоптимизационных задач. Здесь Е множество позиций матрицы (i , j), w ставит всоответствие каждой позиции (i , j) число a i , j .

При этом для задачи α) A∈J ⇔каждый столбец содержит не более одного элемента из A; для задачи β) A∈J ⇔каждый столбец и каждая строка содержит не более одного элемента А.Сформулируем теперь для системы подмножеств S= =(E,J) жадныйалгоритм решения оптимизационной задачи.1.Положить I:=∅.2.Найти e∈E - элемент с наибольшим весом.3.Положить Е’:=Е\{e}. Если I U{e} ∈ J , положить I’:= I U{e} .4.Перейти к шагу 2.5.Если E’=∅, стоп.Определение. Пусть М=(E,J) - система подмножеств. М называетсяматроидом, если жадный алгоритм корректно решает любую индивидуальнуюкомбинаторную задачу оптимизации для системы М.Аксиомы матроидов отражают характерные свойства независимыхмножеств векторов линейных пространств.Существует много эквивалентных определений матроида, но мыограничимся следующим.Утверждение 1.

Пусть М=(Е,J) - система подмножеств. Тогда следующиеутверждения эквивалентны:1) М - матроид.2) Если I p , I p+1 ∈ J , где I p = p , I p +1 = p , то существует такой элементе ∈ I p+1 \ I p , что I p U {e} ∈ J .3) Если А - подмножество множества Е и I,I’ - максимальные по включениюподмножества А, то I = I ′ .Доказательство. 1)⇒ 2). Пусть М - матроид, но 2) не выполняется. Этозначит, что существуют такие два независимые подножества I p , I p +1 , чтоI p = p , I p +1 = p + 1 и для всех e ∈ I p +1 \ I p подмножество I p U{e} неявляется независимым. Рассмотрим следующую функцию весов w на Е: p + 2 , e ∈Ipw( e) =  p + 1 , e ∈ I p+1 \ I p 0 , e ∉ I p U I p+1Имеем w( I p+1 ) ≥ ( p + 1) 2 > p( p + 2) = w( I p ) .

Жадный алгоритм в этомслучае начнет с выбора всех элементов множества I p , поскольку эти элементыимеют максимальный вес. После этого жадный алгоритм не сможет увеличитьобщий вес, т.к. для всех остальных элементов е либо I p U{e} ∈ J (если e ∈ I p+1 ),134либо w(e)=0. Следовательно, жадный алгоритм дает неоптимальное решение I p ,и поэтому M не является матроидом.2)⇒ 3). Пусть выполнено 2) и рассмотрим I,I’ - два максимальных повключению независимых подмножества множества А ⊆ Е. Допустим, чтоI < I ′ . Исключим из I’ I ′ − I − 1 элементов и получим множество I”I ′′ =I + 1.

Поскольку J замкнуто относительно включения, то I”∈J.По свойству 2 существует элемент e ∈ I ′′ \ I такой, что I U{e} ∈ J ., гдеСледовательно, I не является максимальным по включению независимымподмножеством множества A.3)⇒ 1). Пусть выполнено 3) и пусть для некоторого множества весов w(e),e∈Е жадный алгоритм не дает оптимального решения, т.е. приводит кнезависимому множеству I= {e1 , e2 ,..., ei } тогда как существует множество{}I1 = e11 , e21 ,..., e1j ∈ J такое, что w( I1 ) > w( I ) . Пусть элементы множеств I иI1 упорядочены так, что w( e1 ) ≥ w( e2 ) ≥ ...

≥ w( ei ) иw( e11 ) ≥ w( e21 ) ≥ ... ≥ w( e1j ) .Можно считать, что I1 - максимальное по включению независимоемножество в Е. По построению I - максимально по включению, поэтому изсвойства З) (при Е=А) следует, что i=j. Покажем, что выполненоw( e t ) ≥ w( e1t ), ∀ t ∈ 1, i , что будет противоречить допущению, чтоw( I1 ) > w( I ) . Доказываем это индукцией по t.

При t=1 это следует из жадностиалгоритма. Пусть теперь w( e m ) < w( e1m ) для некоторого m>1 и w( e s ) ≥ w( e1s ){}для s ∈1, m - 1 . Рассмотрим множество A = e ∈ E w( e) ≥ w( e1m ) . Множество{e1 ,..., em-1 } является максимальным по включению независимым множеством вА, т.к.

если {e1 ,..., e m-1 , e} ∈ J и w( e) ≥ w( e1m ) > w( e m ) , то жадный алгоритмвыбрал бы e вместо e m в качестве следующего элемента I. Это противоречит 3),{}т.к. e11 ,..., e 1m - другое независимое множество в А большей мощности.Противоречие показывает законность индукции. Утверждение доказано.Сделаем теперь несколько замечаний.1.Оптимальное множество, являющееся решением оптимизационнойзадачи, зависит только от упорядочения весов.2.В матроиде нельзя выбрать независимое множество, состоящее изменьшего числа больших по величине элементов.3.При обращении упорядочения элементов жадный алгоритм находитминимальное по весу множество.4.Жадные алгоритмы эффективны.

Они имеют слож-ность полиномиальнозависящую от размера задачи.Пусть М=(Е,J) - матроид и А ⊆ Е. Рангом r(A) множества А в М называетсямощность максимальных по включению независимых подмножеств множества А.135Согласно свойству 3 утверждения 1 все такие подмножества в А имеют одну и туже мощность и, значит, ранг определяется корректно. Ранг r(E) называетсярангом матроида. Максимальные по включению независимые подмножества дляЕ называются базисами матроида.Из утверждения 1 следует, что каждые два базиса матроида имеютодинаковую мощность.Отметим следующие свойства рангов.Утверждение 2. Для произвольных А,В ⊆ Е и e,f∈E справедливо:1) 0 ≤ r ( A) ≤ A ;2)если А ⊆ B , то r ( A) ≤ r ( B) ;3) r ( A U B) + r ( A I B) ≤ r ( A) + r ( B) ;4) r ( A) ≤ r ( A + e) ≤ r ( A) + 1 , где A + e означает A U{e} ;5)если r ( A + e) = r ( A + f ) = r ( A) , то r ( A + e + f ) = r ( A) .Доказательство. Свойства 1) и 2) очевидны.

Докажем 3).Пусть e1 ,..., e p - максимальное независимое множество в A I B .{}{}внезависимого множества {e1 ,..., e p , f 1 ,... , f q , g1 ,..., g t } вРасширим его до максимального независимого множества e1 ,..., e p , f 1 , ..., f qA и до максимальногоA U B. Имеем p = r ( A I B), p + q = r ( A), p + t ≤ p + q + t = r ( A U B),следовательно r ( A U B) + r ( A I B) = p + q + t + p ≤ r ( A) + r ( B).Свойство 4) очевидно, свойство 5) следует из свойства 3):r ( A) ≤ r ( A + e + f ) = r (( A + e) + f ) ≤≤ r ( A + e) + r ( A + f ) - r (( A + e) I ( A + f )) = r ( A) + r ( A) - r ( A) = r ( A) .Утверждение доказано.Множества семейства J называются независимыми, а подмножества Dмножества Е, не входящие в J, называются зависимыми. Минимальное повключению зависимое подмножество С в Е называется циклом.

Оболочкоймножества А называется максимальное по включению множество S, содержащееА и удовлетворяющее условию r(S)=r(A).(Обозначение:sp(A)).Приведем два полезных свойства матроидов.Утверждение 3. Пусть I∈J и e∈E. Тогда либо I+e∈J, либо I+e содержитединственный цикл.Доказательство.

Допустим, что I+e∉J. Пусть С= c I + e - c ∈ J .{}Покажем, что С - цикл. Действительно, это множество зависимо, т.к. впротивном случае его можно увеличить до базиса в I+e, поскольку С ⊆ I+e икоторый должен иметь мощность I и, следовательно, иметь вид I+e-d, чтоприводит к противоречию, поскольку это означает, что d∈C. Далее, множество С- минимально, т.к. удаляя любой его элемент, скажем с, получаем подмножествоС-с , которое содержится в независимом подмножестве I+e-c. Покажем теперьединственность. Пусть D - другой цикл в I+e и пусть с∈C\D.

Тогда D являетсяподмножеством I+e-c и, значит, независимо, что противоречит предположению.Утверждение доказано.136Утверждение 4. Любое подмножество А ⊆ Е имеет единственнуюоболочку.Доказательство. Если S - оболочка подмножества А и e∈S, то r(A+e)=r(A).В противном случае, если r(A+e)>r(A), то r(S)≥ r(A+e)>r(A) и получили быпротиворечие. Значит S ⊆ sp(A).Покажем, что r(sp(A))=r(A). Легко видеть, что общий базис двух множествявляется базисом их объединения. Поэтому базис множества А является базисомsp(А), т.к. он является базисом в А+e для каждого e∈sp(A).

Утверждение доказано.Следствие 1. sp(А) есть объединение А и всех циклов, все элементыкоторых, кроме одного, содержатся в А.Следствие 2. Если I∈J, I+e∉J и с принадлежит циклу в I+e, то sp(I)=sp(I+ec).Рассмотрим теперь примеры матроидов.1.Для конечного множества Е пара (E,B(E)), B(E)- булеан Е, удовлетворяетусловиям утверждения 1 и является матроидом. Данный матроид называетсясвободным матроидом.2.Для конечного множества Е рассмотрим разбиение E = E1 +...+ E k .Будем называть I ⊆ Е независимым, если никакие два элемента из I не лежат водном блоке разбиения, т.е. I I E j ≤ 1 , j ∈1, k .

Пусть J - семействонезависимых множеств. Если A, B∈J, причем B = A + 1 , то существуетi ∈1, k такой, что E i I A = ∅ и E i I B ≠ ∅ . Возьмем e ∈ E i I B и образуемA U{e} . Ясно, что A U{e} ∈ J . Согласно утверждения 1 пара (Е,J) образуетматроид, называемый матроидом разбиения.Функция ранга определяется так:Пусть i ( A) = { j ≤ k E j I A ≠ ∅ } . Легко проверить, что r ( A) = i ( A)есть требуемая функция ранга, т.к. для данного А можно построить максимальноепо включению независимое подмножество в А, выбирая по одному элементумножества А из каждого E j , с которым А пересекается.

Например, пустьE = {e1 , e2 , e 3 , e 4 , e5 , e6 , e7 , e8 } .П = { {e1}, {e2 , e3}, {e4 , e5}, {e 6 , e7 , e8 } } . Тогда ранг множестваA = {e1 , e2 , e3 , e6 , e 7 } равен 3. Оболочка множества А определяется формулойsp ( A) = U E j .j∈ i ( A )3. Пусть A = ( a ij ) - матрица размера m×n над некоторым полем. Пусть Е множество столбцов матрицы А,I∈J в том и только в том случае, когда множество столбцов I линейно независимо.Ясно, что пара (E,J) образует матроид, называемый матроидом матрицы А.Функция ранга есть обычный ранг системы векторов.