Матроидтарда қолданылатын алгоритм реферат
МАЗМҰНЫ - www.topreferat.com.kz
Кіріспе .................................................................................................................. 2
І тарау. Матроидтарда қолданылатын алгоритм
Матроид түралы ұғым ................................................................................. 3
Циклдер матроиды, Еркін матроид, Бинарлы матроид ........................... 3
Бағаналық матроид ...................................................................................... 4
ІІ тарау. Негіздер мен қарапайым циклдар
2.1 Матроидтың қарапайым циклі ................................................................... 6
2.2 Салдарлары .................................................................................................. 7
2.3 Матроидтар мен комбинаторлық тиімділендіру ...................................... 7
Қорытынды ..................................................................................................... 13
Пайдаланылған әдебиеттер ...................................................................... 14
Жұмыс түрі: Реферат
Пәні: Соңғы қосылған рефераттар
Жұмыс көлемі: - бет
-----------------------------------------------------------------------------------
РЕФЕРАТТЫҢ ҚЫСҚАРТЫЛҒАН МӘТІНІ
Мазмұны
Кіріспе .................................................................................................................. 2
І тарау. Матроидтарда қолданылатын алгоритм
Матроид түралы ұғым ................................................................................. 3
Циклдер матроиды, Еркін матроид, Бинарлы матроид
Бағаналық матроид ...................................................................................... 4
ІІ тарау. Негіздер мен қарапайым
2.1 Матроидтың қарапайым циклі ................................................................... 6
2.2 Салдарлары .................................................................................................. 7
2.3 Матроидтар мен комбинаторлық тиімділендіру ......................................
Қорытынды ..................................................................................................... 13
Пайдаланылған әдебиеттер ...................................................................... 14
Кіріспe
Алгоритмда сараң алгоритмдер маңызды рөл ойнайды,
Циклдер матройды
- Матроид
Еркін матроид
- Е көбейтіндісінің өзі жалғыз
Маршрут
- Кезектесуші жүйелілік
a=v0, e1, v1, e2, …, vn-1,
Бағаналардың биіктіктері мен қабырғалары осындай е=(v-1,
а = v0, v1, …, vn=b
оған енетін қабырғалар саны әрине қарама-қарсы
Аяқсыз n. тек бір ғана нүктесіне
Бинарлы мартоид
-Тұтас сандар бойынша көрсетілген матроид бағана
Келісімділік
Әңгіме үшін алдымен осы мақалада қолданылатын
Матроид туралы ұғым
Келесі матрицаны қарастырамыз.
1001000
0101110
0010110
Е көбейтіндісін анықтаймыз. Матрица бағаналырының {1,2,3,4,5,6,7}
1.Бір көбейтіндісі бос емес. Тіпті егер
і = {{□}}.
2.Бір көбейтіндісінің кез келген элементінің кез
З.Сондай-ақ бір көбейтіндісінде тағы да бір
Матроид ұғымының өзін анықтауға өтеміз. Матроид
Қарастырылым мысалда сызықтық тәуелсіз бағаналар көбейтіндісі
Дәлелдеме. Х,Ү І [Х]=[Ү]+1 болсын.
Бағаналық матроидты қарастырамыз
Бағаналар бағытталмаған және 4 биіктікпен тесік
Теорема -1
Айталық 6 сызықша бағана, ал АG
Дәлелдеме. Х□АG X циклға ие болған
Енді X сызықтық тәуелсіз деп болжамдаймыз.
Егер де D нөлдік векторға ие
Негіздер мен қарапайым циклдар
Тікелей матроидтардың көмегі арқылы әр алуан
Матроидтың қарапайым циклі - матроидтардың минимальды
Екі көбейтінді береміз - М матроидтың
Теорема - 2
X көбейтіндісі келесі екі қасиет орындалған
1. В көбейтіндісі бос емес.
2.Егер де В1, В2□В, х□В1, -
Дәлелдеме. Онда келтірілген екі қасиет орындалсын
В1□{I}□В, І=В1-В. Дегенмен бұл кезде Ү□В-(В□{I})
Айталық В - базалар көбейтіндісі, екі
Салдарлары
Кез келген базаның қуаттылығы екі қасиет
Теорема - 3
С көбейтіндісі келесі үш қасиет орындалған
1. С элементтерінің ешқайсысы бос
2. С-ның ешқандай элементі С-ның басқа
З. Егер де С1 және
Дәлелдеме.
Келтірілген екі дәлелдемеге ұқсас. Оқырманға оны
Матроидтар мен комбинаторлық тиімділендіру
Матроидтар комбинаторлық тиімділенген байланысты тапсырмаларға және
Мынадай тапсырмалар қарастырамыз: менеджерде m бір
Айталық А - қандайда бір Е
Теорема - 4
Айталық А Е көбейтіндісінің қандайда бір
Дәлелдеме
Жартылай трансверсальдың әрбір көбейтіндісі - жартылай
Салдар-1
В матроидтың кез келген негізі үшін
Келесі қадамда біз қос матроид ұғымын
Бұл қадамда біз сараң алгоритм ұғымын
Айталық Е - бос емес соңғы
және w (А) А көбейтіндісінің салмағы
Бірқатар жиынтығын ең болмағанда бір бос
Ары қарай В тәуелсіздік аксиомасын қанағаттандырады,
Келесі тапсырманы қарастырамыз: жартылай реттелген көбейтіндіде
Нысандар ұяшығына қандай жағдайларда келесі алгоритм
Сараң алгоритм.
7. е1,
8. Айталық
және
9. Мүмкін болғанға дейін екінші
Айталық В - М=М(G) матроидының бірқатар
Кез келген Т ағаш үшін М(Т)
требиальді екендігін байқаймыз.
Мысал. Келесі бағана циклдары матроидын қарастырамыз:
Сурет-1. бағана мысалы.
1. E = {е1,е2,е3,е4,е5} – матроидтың
2. В1={е2,e3,e4}, В1={е1,e3,e4}, В3={е1,e2,e4}
3. B2={е1,е5},= {е2,е5},= {е3,е5} – кобаз
4. {е1,е2}, {е1,е3}, {e2,e3},{e4} – қарастырылған
Теорема - 5.
көбейтіндісі қасиетті қанағаттандыратын Е бос емес
кез келген ко цикл үшін С*.
Дәлелдеме.
Егер X матроид циклі болып табылса,
Керісінше айталық X - көрсетілген қасиетті
Е1 матроиды еркін матроидқа қосарлы және
Айталық G
Қорытынды.
Менің бұл курстық жұмысымның тақырыбы “
Бұл жұмысты орта оқу орындарында қолдануға
Үнемі алгоритмдердің мақсаты – берілген есептерді
Мұнда тест сұрақтарын енгізетін болсақ, онда
Пайдаланылған әдебиеттер:
В.П.Сигорский. Математический аппарат инженера. – К.,
Ю.Н.Кузнецов, В.И.Кузубов, А.Б.Волощенко. Математическое программирование: учебное
Е.В.Маркова, А.Н.Лисенков. Комбинаторные планы в задачах
Е.П.Липатов. Теория графов и её применения.
В.М.Бондарев, В.И.Рублинецкий, Е.Г.Качко. Основы программирования. –Харьков,
2
