Матроидтарда қолданылатын алгоритм

Мазмұны

Кіріспе ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. 2
І тарау. Матроидтарда қолданылатын алгоритм

1.1 Матроид түралы ұғым ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 3
1.2 Циклдер матроиды, Еркін матроид, Бинарлы матроид ... ... ... ... ... ... ... 3
1.3 Бағаналық матроид ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. 4

ІІ тарау. Негіздер мен қарапайым циклдар

2.1 Матроидтың қарапайым циклі ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 6
2.2 Салдарлары ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. 7
2.3 Матроидтар мен комбинаторлық тиімділендіру ... ... ... ... ... ... ... ... ... .. 7

Қорытынды ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 13

Пайдаланылған әдебиеттер ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. 14

Кіріспe
Алгоритмда сараң алгоритмдер маңызды рөл ойнайды, олар түсіну мен жүзеге асыру үшін қарапайым салыстырмалы жылдам жұмыс жасайды, сараң алгоритмнің көмегімен шешуге болатын көптеген әр алуан тапсырмалар белгілі. Дегенмен, көптеген тапсырмалардың нақты шешемін табу үшін сараң алгоритмді қолдану мүмкіндігін барлық уақытта дәлелдеу мүмкін емес. Бұл мақалада сараң алгоритмдердің теоретикалық негізі - матроидтер теориясы қарастыратын болады. Оның көмегі арқылы барынша жиі сараң алгоритм қолдануы мүмкіндігін орнатуға болады. Кейін анықгалғандай ол үшін көпшілік зерттеулер матроид болып табылатындығы қажет. Алдымен матроидқа анықтама беріледі, сосын матроидтармен тікелей байланысты бірқатар стандарттық тапсырмалар қарастырылатын болады.
Циклдер матройды
- Матроид бірқатар бағаналар қабырғаларының мәнінің элементтері, ал негіздер бұл бағана каркастары; матроидтар циклі ретінде бағаналардың іргетастық циклдары қызмет етеді.
Еркін матроид
- Е көбейтіндісінің өзі жалғыз ғана негіз ретінде қызмет ететін матроид.
Маршрут
- Кезектесуші жүйелілік
a=v0, e1, v1, e2, …, vn-1, en, vn=b
Бағаналардың биіктіктері мен қабырғалары осындай е=(v-1, v), маршруттар биіктіктерді біріктіреді дейді. а және b маршрут соңы. Бұл жерде маршрутты тек олардың биіктіктерін есептеумен беруге болады.
а = v0, v1, …, vn=b немесе оның қабырғалары е1, е2, ..., еп соңғы егер
оған енетін қабырғалар саны әрине қарама-қарсы жағдайда аяқсыз.
Аяқсыз n. тек бір ғана нүктесіне ие және бір жақты аяқсыз маршрут деп аталады. Аяқсыз биіктіксіз n. екі жақты аяқсыз нүкте деп аталады.
Бинарлы мартоид
-Тұтас сандар бойынша көрсетілген матроид бағана кесіндісі матроиды мен циклді матроид және графикалық матроид бинарлы деп аталады.
Келісімділік
Әңгіме үшін алдымен осы мақалада қолданылатын терминдер себебі бойынша бағытталуы қажет. Графада цикл деп ондағы әрбір жабық жолдарды атаймыз. Онда бағана қабырғаларының әрбірі бір реттен көп кездеседі. Барлық қарастырылған бағаналар бағытталмаған. Бағаналардың бағаналық матроидтарын М деп белгілейміз. Матрицаның векторлы матроидын М (А) деп белгілейміз.
Матроид туралы ұғым
Келесі матрицаны қарастырамыз.
1001000
0101110
0010110
Е көбейтіндісін анықтаймыз. Матрица бағаналырының {1,2,3,4,5,6,7} нөмірлерден тұратын көбейтінді сияқты, ал 1 көбейтіндісін, Е көбейтіндісінен тұратын көбейтінді сияқты. Олармен анықталатын векторлар R заттық сандарының аймағы үстінде тәуелсіз сызықтық болып табылады. Тұрғызылған 1 көбейтіндісі қандай қасиеттерге ие деген сұрақты қоямыз.
1.Бір көбейтіндісі бос емес. Тіпті егер не бастапқы көбейтіндісі бос болса да - Е=□, егер 1 бос орынға ие көбейтіндінің бір элементінен тұрады.
і = {{□}}.
2.Бір көбейтіндісінің кез келген элементінің кез келген көбейтіндісі осы көбейтінді элементі болады. Бұл қасиет түсінікті - егер векторлардың бірқатар жиынтығы аймақ үстінде сызықтық тәуелсіз болса, онда оның кез келген жиынтығы сызықтық тәуелсіз болады.
З.Сондай-ақ бір көбейтіндісінде тағы да бір маңызды және превиальды емес қасиет бар. Егер X, Ү I, әрі [Х]=[Ү]+1, бұл кезде х Х-Ү, элементі бар. Тағы мұндай Ү□{х}□I бұл кезеңде ол біршама қызғылықты және таңғаларлық болып көрінеді. Кейіннен бұл түсінікті болады.
Матроид ұғымының өзін анықтауға өтеміз. Матроид деп – матроидтың тәуелсіз көбейтінділерінің көбейтіндісі деп аталатын 1 көбейтіндісінің және матроидтың негіздік көбейтіндісі деп аталатын Е соңғы көбейтіндісінен тұратын Е I көбейту сыңарларын айтады. Әрі 1 жоғарыда айтылған 3 қасиетті қанағаттандырады. №2 қасиет мұрагерлік қасиет деп те аталатындығын айту қажет.
Қарастырылым мысалда сызықтық тәуелсіз бағаналар көбейтіндісі шындығында да матроид болып табылатындығын дәлелдейміз. Бұл үшін матроид анықтаудын үшінші қасиетті дәлелдеу жеткілікті. Қарсы әдіс дәлелдемесін жүргіземіз.
Дәлелдеме. Х,Ү І [Х]=[Ү]+1 болсын. w Х□Ү қамтитын вектор кеңістігі болсын. Оның өлшем бірлігі [X] кем емес болуы керек. Ү□{х} барлық х Х-Ү үшін сызықтық тәуелсіз болады деп болжамдайық. Онда Ү w кеңістігінде негіз түзеді. Бұл жерде [X] dim W [Ү]. Дегенмен, X және Ү шарттары бойынша сызықтық тәуелсіз векторлардан тұрады және [Х]>[Ү], қарама-қайшылық аламыз. Векторлардың мұндай көбейтіндісі матроид болып табылады. Оны кейде векторлық матроид деп те атайды.
Бағаналық матроидты қарастырамыз
Бағаналар бағытталмаған және 4 биіктікпен тесік болып табылатын 7 қабырғадан тұрады. Айталық Е осы бағана қабырғаларынан тұратын көбейтінді болсын, Е={1,2,3,4,5,6,7}, ал I бағана циклі өзіне әрбір элементті иеленбейтін Е көбейтіндісінің көбейтіндісі болады. Бұл сыңар матроид болып табылады. Оны бағаналы матроид дейді және М(G) белгілейді.

Пайдаланылған әдебиеттер:
1. В.П.Сигорский. Математический аппарат инженера. – К., «Техника», 1975, 768 с.
2. Ю.Н.Кузнецов, В.И.Кузубов, А.Б.Волощенко. Математическое программирование: учебное пособие. 2-е изд. Перераб. И доп. – М., Высшая школа, 1980, 300 с.
3. Е.В.Маркова, А.Н.Лисенков. Комбинаторные планы в задачах многофакторного эксперимента. – М., Наука, 1979, 345 с.
4. Е.П.Липатов. Теория графов и её применения. –М., Знание, 1986, 32 с.
5. В.М.Бондарев, В.И.Рублинецкий, Е.Г.Качко. Основы программирования. –Харьков, Фолио; Ростов на Дону, Феникс, 1998, 368 с.