Математическая логика и теория алгоритмов. Стенюшкина В.А. - 90 стр.

       Матроидом называется пара М=(S,I), удовлетворяющая условиям:
       1)   S-конечное непустое множество;
       2)   I-непустое семейство подмножеств S, которые называются незави-
симыми, таких, что из B∈I и A∈B следует A∈I. Семейство I называется наследст-
венным;
       3)   Если A∈I, B∈I и A< B, то существует элемент x∈B\A такой, что
A∪{х}∈I. Это свойство семейства I называется свойством замены.
       Примеры
       1    Матричный матроид – Пусть Т – вещественная матрица, S-
множество её столбцов, и подмножество A⊂S называется независимым, если
оно линейно независимо. Тогда получается матроид.
       2    Графовый матроид – Пусть G – неориентированный граф; SG –
множество ребер графа, IG состоит из всех ацикличных множеств ребер (то есть
являющихся лесами). Тогда (SG, IG) – матроид.
       Графовые матроиды являются частным случаем матричных, если ребро
графа рассматривать как формальную сумму его вершины с коэффициентами в
поле вычетов по модулю 2.
       Если M=(S, I) – матроид, то элемент x∉A∈I называется независимым от х,
если множество AU{x} независимо. Например, в графовом матроиде ребро е
независимо от А тогда и только тогда, когда его добавление к А не создает цик-
ла.
       Независимое подмножество в матроиде называется максимальным, если
оно не содержится ни в каком большем независимом подмножестве. Имеет ме-
сто теорема:
       Теорема 4.2 Все максимальные независимые подмножества данного мат-
роида состоят из одинакового числа элементов.
       Доказательство Пусть А, В – независимые подмножества, и  А < В . то-
гда из свойства замены следует, что существует х∈А, для которого A∪{x} неза-
висимо, что противоречит максимальности.
       Пример – Пусть G – связный граф, MG – соответствующий матроид. Тог-
да всякое максимальное независимое подмножество MG должно быть деревом с
 V -1 ребром (V – множество вершин), соединяющим все вершины G. Такое
дерево называется основным деревом графа G.
       Матроид M=(S, I) называется взвешенным, если на множестве S задана
весовая функция W со значениями в множестве положительных чисел – W:
S→R+. Функция W распространяется по аддитивности на все подмножества
множества S. Вес подмножества определяется как сумма весов его элементов:
W(A)=∑x∈A W(x). Например, если MG – графовый матроид, W(e) – длина ребра e,
то W(A) – сумма длин ребер подграфа A.
       Независимое подмножество максимального веса называется оптималь-
ным подмножеством взвешенного матроида.

      5 Алгоритмы Евклида в кольце полиномов