Построение решёток матроида с помощью ранговой функции

МИНИСТЕРСТВО  ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ 

ПЕНЗЕНСКИЙ  ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ФАКУЛЬТЕТ ЭКОНОМИКИ И УПРАЛЕНИЯ

КАФЕДРА «ЭКОНОМИЧЕСКАЯ КИБЕРНЕТИКА» 
 
 
 
 
 
 
 
 
 
 
 
 

ЛАБОРАТОРНАЯ  РАБОТА №3

Дисциплина: Дискретный анализ и дискретная оптимизация

Построение решёток матроида с помощью ранговой функции

Бригада №9 
 
 
 
 
 
 

                                                                         Выполнили:

студентки гр.07ЭЧ1

Зюзина А., Жукова Е.,

Проверил: д.т.н., профессор Лебедев В.Б. 
 
 
 
 

Пенза 2010 

Лабораторная работа №3

Построение  решёток матроида с помощью ранговой функции 

    Цель  работы: научиться строить различные решетки матроида с помощью ранговой функции и на основе их соответствующие диаграммы Хассе.

    Задание: Построить решетки матроида для трёх данных семейств порождающих множеств, используя средства Microsoft Office либо какого-нибудь другого программного продукта.

1. R = {R} ={a, b, c, d};
2. R = {R} ={1234, 234, 14};
3. R = {R} ={ab, ac, bc}.

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

                             Порядок выполнения работы 

1. Строим  решётку матроида для первого семейства порождающего множества

Строим все решётки с помощью теоремы Эдманса.

kr(a) = 1, kr(b) = 1, kr(c) = 1, kr(d) = 1

min kr (i) = 1

,

,

,

,

,

,

 
 

Таблица 1 Расчёт значений ранговой функции для множества R = {a, b, c, d}

 

2. Строим  решётку матроида для второго семейства порождающего множества

kr(1) = 2, kr(2) = 2, kr(3) = 2, kr(4) = 3

min kr (i) = 2

,

,

,

,

,

,

,

Таблица 2 Расчёт значений ранговой функции для множества 
R ={1234, 234, 14}

3. Строим  решётку матроида для третьего семейства порождающего множества

kr(a) = 2, kr(b) = 2, kr(c) = 2

min kr (i) = 2

,

,

,

 
 

Таблица 3 Расчёт значений ранговой функции для множества R = {ab, ac,bc}

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

                          Результаты построения диаграмм Хассе 

     На основании построенной для каждого исходного семейства порождающих множеств таблиц была построена соответствующая решётка матроида (см. рис 1 – 3) 

Рисунок 1 Решётка матроида для множества R = {a, b, c, d}

 
 
 
 

Рисунок 2 Решётка матроида для множества R ={1234, 234, 14} 
 
 

 

 

Рисунок 3 Диаграмма Хассе для  семейства  множеств 
R = {R} ={ab, ac, bc} 
 
 
 
 
 
 
 

                                                              Вывод 

Решена  задача построения решёток матроида по исходным семействам множеств с помощью ранговой функции благодаря использованию графических средств Microsoft Word. Решётки матроида были построены для таких множеств, как R = {R} ={a, b, c, d},  
R = {R} ={1234, 234, 14}, R = {R} ={ab, ac, bc}.