Реферат: Матроид

В алгоритмике играют важную роль жадные алгоритмы. Они просты для понимания и реализации, работают сравнительно быстро, известно много разнообразных задач, которые можно решить с помощью жадных алгоритмов. Однако не всегда можно доказать возможность применимости жадного алгоритма для нахождения точного решения многих задач. В данной статье будет рассмотрена теоретическая основа жадных алгоритмов — теория матроидов. При помощи нее можно довольно часто установить возможность применимости жадного алгоритма. Как потом выяснится, для этого необходимо, чтобы исследуемое множество являлось матроидом. Сначала будет дано определение матроида, а затем будут рассмотрены несколько стандартных задач, напрямую связанных с матроидами.

Матроид - классификация подмножеств некоторого множества, представляющая собой обобщение идеи независимости элементов, аналогично независимости элементов линейного пространства, на произвольное множество.

Аксиоматическое определение

Матроид — пара (X,I), где X — конечное множество, называемое носителем матроида, а I — некоторое подмножество множества всех подмножеств X, называемое семейством независимых множеств, то есть . При этом должны выполняться следующие условия:

Если и , то

Если и мощность А больше мощности В, то существует такой, что

Базами матроида называются максимальные по включению независимые множества.

Определение в терминах правильного замыкания

Пусть - частично упорядоченное множество. - замыкание в , если:

Для любого х из Р:

Для любых х,у из Р:

Для любого х из Р:

Рассмотрим случай, когда частично упорядоченное множество – булева алгебра. Пусть - замыкание .

1. Замыкание правильно (аксиома правильного замыкания), если

2. Для любого существует такое , что

1.

2.

Пара , где - правильное замыкание на , называется матроидом.

Примеры

Универсальный матроид . Множество X имеет мощность n, независимыми множествами являются подмножества мощностью не больше k. Базы — подмножества мощностью k.

Графический матроид. Множество X — множество ребер графа, независимые множества — ациклические подмножества этих ребер. Базами являются остовные леса графа.

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

Определим множество E, как множество состоящее из {1, 2, 3, .., n} — номеров столбцов некоторой матрицы, а множество I, как множество состоящее из подмножеств E, таких, что векторы, определяемые ими, являются линейно независимыми над полем вещественных чисел R. Зададимся вопросом — какими свойствами обладает построенное множество I?

1. Множество I непусто. Даже если исходное множество E было пусто — E = ∅, то I будет состоять из одного элемента — множества, содержащего пустое. I = { {∅} }.

2. Любое подмножество любого элемента множества I также будет элементом этого множества. Это свойство понятно — если некоторый набор векторов линейно независим над полем, то линейно независимым будет также любой его поднабор.

3. Если A, B ∈ I, причем |A| = |B| + 1, тогда существует элемент x ∈ B − A, такой что B ∪ {x} ∈ I.

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

Доказательство. Пусть и . Пусть W будет пространством векторов, охватываемым . Понятно, что его размерность будет не менее . Предположим, что будет линейно зависимо для всех (то есть третье свойство не будет выполняться). Тогда B образует базис в пространстве W. Из этого следует, что .Но так как по условию A и B состоят из линейно независимых векторов и , получаем противоречие. Такое множество векторов будет являться матроидом.

Дополнительные понятия

Двойственным данному матроиду называется матроид, носитель которого совпадает с носителем данного матроида, а базы — дополнения баз данного матроида до носителя. То есть X*=X, а множество баз двойственного матроида — это множество таких B*, что B*=X\B, где B — база данного матроида.

Циклом в матроиде называется такое множество A⊂X, что A∉I, и для любого B⊂A, если B≠A, то B∈I

Рангом матроида называется мощность его баз. Ранг тривиального матроида равен нулю.

--> ЧИТАТЬ ПОЛНОСТЬЮ <--