Матроид теориясы және сараң алгоритмдердің комбинаторлық оңтайландырудағы қолданбалары

 Мазмұны Кіріспе .................................................................................................................. 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