Notice: Undefined offset: 0 in /var/www/referat.ru/public/skins/default/application/item/index.phtml on line 15

Notice: Undefined offset: 0 in /var/www/referat.ru/public/skins/default/application/item/index.phtml on line 16

Матроид

  • Категория
  • Раздел
  • Просмотров 3797
  • Скачиваний 396
  • Размер файла 48
    Кб

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

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

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

Определение в терминах правильного замыкания Пусть Для любого х из Р: Для любых х,у из Р: Для любого х из Р: Рассмотрим 1. Замыкание правильно (аксиома правильного замыкания), если 2. Для любого 1. 2. Пара Примеры Универсальный матроид Графический матроид. Множество X — множество ребер графа, независимые множества — ациклические подмножества этих ребер. Базами являются остовные леса графа. Матричный матроид. Семейство всех

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