Абстрактное отношение зависимости — страница 10

  • Просмотров 5677
  • Скачиваний 76
  • Размер файла 765
    Кб

Определение 18. Элементы множества называются независимыми, а остальные подмножества - зависимыми множествами. В соответствии с введенными ранее аксиомами пространства зависимости видим, что матроиды - это в точности конечные транзитивное пространства зависимости. Рассмотрим следующие примеры матроидов: Пример 1. Семейство всех линейно независимых подмножеств любого конечного множества векторов произвольного непустого

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

есть по крайней мере один вектор , который не входит в множество и не выражается в виде линейной комбинации векторов из множества . Добавление вектора к множеству образует линейно независимое множество. Пример 2. Свободные матроиды. Если - произвольное конечное множество, то - матроид. Такой матроид называется свободным. В свободном матроиде каждое множество независимо, А является базисом и . Пример 3. Матроид трансверсалей. Пусть

- некоторое конечное множество, и - некоторое семейство подмножеств этого множества. Подмножество называется частичной трансверсалью семейства , если содержит не более чем по одному элементу каждого подмножества из семейства . Частичные трансверсали над образуют матроид на А. Перейдем к рассмотрению жадного алгоритма. Для начала нужно сформулировать задачу, которую будем решать с его использованием. Пусть имеются конечное

множество , , весовая функция и семейство . Рассмотрим следующую задачу: найти , где . Другими словами, необходимо выбрать в указанном семействе подмножество наибольшего веса. Не ограничивая общности, можно считать, что Рассмотрим такой алгоритм, который исходными данными имеет множество , семейство его подмножеств и весовую функцию , причем множество упорядочено в порядке убывания весов элементов. После выполнения этого

алгоритма мы получим подмножество . Изначально искомое множество пусто, далее просматриваем по очереди все элементы из множества и проверяем зависимость множества, если - независимо, то элемент добавляем в множество , если же - зависимо, то переходим к элементу , пока все элементы из множества не будут проверены. Алгоритм такого типа называется «жадным». Совершенно очевидно, что по построению окончательное множество , то есть