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

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

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

КАФЕДРА «ЭКОНОМИЧЕСКАЯ КИБЕРНЕТИКА»
ЛАБОРАТОРНАЯ РАБОТА №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}

Ø	0	0	ab	0	0	abc	0	0
a	0	0	ac	0	0	abd	0	0
b	0	0	ad	0	0	acd	0	0
c	0	0	bc	0	0	bcd	0	0
d	0	0	bd	0	0	abcd	0	0
			cd

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

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

min kr (i) = 2





,

,

,

,

,

,

,



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

Ø	0	0	12	0	0	123	0	0
1	0	0	13	0	0	124	1	1
2	0	0	14	1	1	134	1	1
3	0	0	23	0	0	234	1	1
4	1	1	24	1	1	1234	1	1
			34	1	1

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

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

min kr (i) = 2





,

,

,



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

Ø	0	0	ab	0	0
a	0	0	ac	0	0
b	0	0	bc	0	0
c	0	0	abc	0	0

Результаты построения диаграмм Хассе
На основании построенной для каждого исходного семейства порождающих множеств таблиц была построена соответствующая решётка матроида (см. рис 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}.