Алгебраические структуры

Дистрибутивная ограниченная решетка, в которой для каждого элемента существует дополнение, называется булевой алгеброй.

Свойства булевой алгебры:

1. а а = а,                                                 a a = a

по определению решетки;

2. a b = b a,                                ab = ba

по определению решетки;

3. а (bс) = (а  b) с,                         a(b c) = (a b) c

по определению решетки;

4. (а b) а = а,                              (ab) a = a

по определению решетки;

5. а (b с) = (а Ь)  (а с),               a (b  с) = (а b)  (а с)

по свойству дистрибутивности;

6. а 1= 1,                                                  а 0 = 0

по свойству ограниченности;

7. а 0 = а,                                                 а 1 = 0

по следствию из теоремы ограниченности;

8. а" = а

по теореме о свойствах дополнения;

9. (а b)' = а' b'                                      (a b)' = а' b'

по теореме о свойствах дополнения;

10. а а' = 1,                                              a  а' = 0

так как дополнение существует.

Пример

1. <2^M; , ,- > - булева алгебра, 1 = U, 0 = Ǿ, = .

2. <Е₂; &, V, ¬> — булева алгебра, 1 = 1,0=1, =.

3. Пусть π(р) : = {q | q N— простое & qр} — множество простых чисел, не превосходящих р.

множество произведений различных чисел из π (р).

Тогда <Р; Н.О.Д., Н.О.К., ДОП> — булева алгебра, где Н.О.Д. - наибольший общий делитель, Н.О.К. — наименьшее общее кратное,

ДОП(n): = .

1:= , 0: = 1, m  n: = n делится на m.

2.7. Матроиды

Матроиды, рассматриваемые в этом разделе, вообще говоря, не являются алгебраическими структурами в том смысле, который был придан этому понятию в первом разделе данной главы. Однако, во-первых, матроиды имеют много общего с рассмотренными алгебраическими структурами (в частности, с линейно независимыми множествами в векторных пространствах) и изучаются сходными методами, а во-вторых, они являются теоретической основой для изучения и анализа «жадных» алгоритмов. Ясное понимание природы и области применимости жадных алгоритмов совершенно необходимо всякому программисту.

2.7.1. Определения

Матроидом М = <Е, e> называется конечное множество Е, |Е| = n и семейство его подмножеств e2^Е, такое что выполняются следующие три аксиомы:

М1:    Ǿ  e;

М2:    Аe&ВAВe;

М3:    А, Вe & |В| = |А| + 1  eВ\ А А{е}e.

Элементы множества e называются независимыми, а остальные подмножества Е (2^Е \ e) — зависимыми множествами.

ЗАМЕЧАНИЕ———————————————––––––––––––––––––––————–––––––––––––––––––––––

Аксиома М₁ исключает из рассмотрения вырожденный случай e = Ǿ.

————————————————————————––––––––––––––––––––————–––––––––––––––––––––––

Пример

Семейство линейно независимых множеств векторов любого векторного пространства является матроидом. Действительно, по определению можно считать,

что пустое множество линейно независимо. Всякое подмножество линейно независимого множества векторов линейно независимо. Пусть A:={а₁...,а_m} и В: ={b₁,..., b_m+1} — линейно независимые множества. Если бы все векторы из множества В выражались в виде линейной комбинации векторов из множества А, то множество В было бы линейно зависимым. Стало быть, среди векторов множества В есть по крайней мере один вектор b, который не входит в множество A и не выражается в виде линейной комбинации векторов из множества А. Добавление вектора b к множеству А образует линейно независимое множество.

ЗАМЕЧАНИЕ———————————————––––––––––––––––––––————–––––––––––––––––––––––

Само понятие матроида возникло в результате исследований линейной независимости в векторных пространствах.

————————————————————————––––––––––––––––––––————–––––––––––––––––––––––

2.7.2. Максимальные независимые подмножества

Пусть XЕ — произвольное множество. Максимальным независимым подмножеством множества X называется множество У, такое что

УХ & У  Е &Z  Е  Z X =Z У.

Множество максимальных независимых подмножеств множества X обозначим . Рассмотрим следующее утверждение:

М₄:   Х (У& Z |У|=|Z|), то есть максимальные независимые подмножества данного множества равномощны.

ТЕОРЕМА   Пусть М = <Е, e> и выполнены аксиомы M₁ и М₂. Тогда аксиома M₃ и утверждение М₄ эквивалентны, то есть

(A,BE &|B|=|A|+1eB\A A{e}E)

тогда и только тогда, когда

X (У, Z |У|=|Z|)

Доказательство

Необходимость. Пусть выполнены утверждения М₁, М₂, М₃ (то есть М — матроид). Покажем от противного, что выполняется и М₄. Пусть У,Z, |У| |Z| и для определенности |У| > |Z|. Возьмем У' У, так что |У'| = |Z| + 1. Тогда по свойству М₃ имеем: еУ'\ Z W:=Z{е}e. Таким образом, имеем We, ZW, W X, что противоречит предположению Z.

Достаточность. Пусть выполнены утверждения М₁, М₂, М₄. Покажем от противного, что выполняется и М₃. Возьмем A,Вe, так что |В|=|А|+1. Допустим, что ¬еВ\А А{е}e, то есть еВ\А А{е}e. Рассмотрим С:=АВ. Имеем А. Но Вe, поэтому В' ВВ'&В' e&В'  . По условию М₄ имеем |В'| = |А|.  Но |А|=|В'| |В|=|А|+1 - противоречие.

ЗАМЕЧАНИЕ———————————————––––––––––––––––––––————–––––––––––––––––––––––

Таким образом, M₁, М₂, М₄ — эквивалентная система аксиом матроида.

————————————————————————––––––––––––––––––––————–––––––––––––––––––––––

2.7.3. Базисы

Максимальные независимые подмножества множества Е называются базами, или базисами, матроида М = <Е, e>. Всякий матроид имеет базисы, что видно из следующего алгоритма.

Алгоритм 2.1. Алгоритм построения базиса матроида

Вход: Матроид М = <Е, e>.

Выход: Множество ВЕ элементов, образующих базис.    

В : = 0 { вначале базис пуст }

    for  еЕ do

        if В{е}E  then

В : = В {е} { расширяем базис допустимым образом }

end if

    end for

Обоснование

Алгоритм вычисляет базу матроида М.

Действительно, пусть В₀ = Ǿ, В₁,…,В_k = В — последовательность значений переменной В в процессе работы алгоритма. По построению i В_i  Е. Пусть В , то есть В не является максимальным. Тогда  В' В В' & В'  В & В' Е. Возьмем В"В', так что |В"| = |В| + 1, В  В" и В"   Е. Рассмотрим е   В' \ В. Элемент е не попал в множество В, но алгоритм про сматривает все элементы, значит, элемент е был отвергнут на некотором шаге i, то есть (В_i-1 {е})  E. Но е В" & В_i-1В"  (В_i-1 {е}) е Е. По аксиоме М₂ имеем: (В_i-1 {е})  Е — противоречие.

СЛЕДСТВИЕ   Все базы матроида равномощны.

2.7.4. Ранг

Мощность максимального независимого подмножества данного множества X называется рангом множества:

ЗАМЕЧАНИЕ———————————————––––––––––––––––––––————–––––––––––––––––––––––

Это определение корректно, потому что все максимальные независимые подмножества данного множества равномощны.

————————————————————————––––––––––––––––––––————–––––––––––––––––––––––

ЛЕММА  XE & YX = Y

Доказательство

XX & X E & YXYXX = Y

ТЕОРЕМА:XEr (X) = |X|

Доказательство

X E (XE & YX = Y) (r (x) = |X|)

ТЕОРЕМА: A, B  Ee1, e2 E

R₁ : 0 r(A)  |A|

R₂ : АВr(A)r(B)

R₃ : r(AB) + r(AB)  r(A)+ r(B)

R₄ : r(A) r(A{e})r(A)+1

R₅ : r(A{e₁}) = r(A{e₂})= r(A) r(A{e₁,e₂}) = r(A)

Доказательство

R₁ : очевидно;

R₂ : очевидно;

R₃ : Пусть {е₁,…,е_i}. Тогда {е₁,…,е_i, d₁,…,d_i } и затем {е₁,…,е_i, d₁,…,d_j, c₁,…,c_k,}. Имеем i = r (A B), B^i+j = r(A), i + k i + j + k = r(A В)  r(A B) + r(A B) = (i + j +k) + i =  (i + j) + (i + k) r(А) + r(В);

R₄: очевидно;

R₅ : r(A) r(А{е₁, е₂}) = r(А {e₁}{е₂})  r(А{е₁})+ r(A{е₂}) - r((A{e₁}) (A {е₂})) = r(A) + r(A) - r(A) = r(А).

2.7.5. Жадный алгоритм

Пусть имеются конечное множество Е, |Е| = n, весовая функция w: ЕR₊ и семейство e2^Е.

Рассмотрим следующую задачу: найти Xe, такое что

,  где

Другими словами, необходимо выбрать в указанном семействе подможество наибольшего веса.

Не ограничивая общности, можно считать, что w(e₁) …w(e_n) > 0

Рассмотрим следующий алгоритм.

Алгоритм 2.2. Жадный алгоритм

Вход: множество Е = {е₁ , . . . , е_n}, семейство его подмножеств e и весовая функция w

Множество Е упорядочено в порядке убывания весов элементов