Предыдущая страница реферата | 1  2  3  4 | Следующая страница реферата

Доказательство. При lr(E)=ur(E) лемма, очевидно, следует из определения матроида.

Рассмотрим случай lr(E)<ur(E). Пусть . Перенумеруем элементы и так, что если среди них есть одинаковые, то они имеют первые m номеров (), иначе m=0. Определим где r=ur(E).

Шаг 0: Am=A - база. Шаг i: . Am+i-1 - база, следовательно, множество независимо и не база. Если - не база, то мы нашли требуемые базы Am+i-1, B и элемент u=am+i. Иначе пусть - база. Переход на шаг i+1.

Учитывая, что A|B| зависимо (т.к. B - база и ), алгоритм завершится не позднее, чем на шаге |B|+1 доказательством леммы.

2. Характеристика и ее свойства

Фронтом данного независимого множества F назовем .

Fr(F) - это множество элементов, каждый из которых может быть добавлен к F без нарушения его независимости. Именно из этих элементов градиентный алгоритм выберет на очередном шаге самый "тяжелый" для добавления к F.

Введем новую характеристику системы независимости:

Она характеризует "узкое место" в работе градиентного алгоритма.

Будем называть предбазами максимальные по включению независимые множества, не являющиеся базами. Тогда определение (4) можно записать как

поскольку каждое независимое подмножество, которое не является базой, содержится в некоторой предбазе и .

Теорема 2. 1) Для систем независимости , базы которых представляют собой все r-элементные подмножества (r-однородные матроиды),

где n=|E|, r=ur(E).

2) Для систем независимости, отличных от r-однородных матроидов,

Доказательство. 1) Очевидно, т.к. |Fr(F)|=n-|F|=n+1-ur(E) для любой предбазы F.

2) Если матроид (не r-однородный), то . Пусть F - база A. Т.к. |F|<|A|, то F не является базой матроида и .

Если не матроид, то по лемме 1 . Заметим, что .

Замечание. На различных системах независимости может принимать значения от 1 до n=|E| включительно, причем только в случае 1-однородного матроида.

Теорема 3 (оценка кривизны). Для любой системы независимости, отличной от 1-однородного матроида, имеет место оценка

Рекомендуем скачать другие рефераты по теме: банки рефератов, где диплом.





Предыдущая страница реферата | 1  2  3  4 | Следующая страница реферата