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


Мазмұны

Кіріспе ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. 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 с.

Пән: Информатика
Жұмыс түрі: Реферат
Көлемі: 12 бет
Бұл жұмыстың бағасы: 400 теңге




Мазмұны

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

1. Матроид түралы ұғым
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
... ... .. 3
2. Циклдер матроиды, Еркін матроид, Бинарлы матроид
... ... ... ... ... ... ... 3
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

Айталық 6 сызықша бағана, ал АG - оның инциденция матрицасы. Егер де АG
-ді аймақ ішіндегі матрица ретінде қарастыратын болсақ, {0, 1}, мұнда
барлық операциялар екінші модуль бойынша орындалады, осы кезде АG -
құрастырылады. Векторлық матроид өзінде циклі жоқ тәуелсіз көбейтінді
ретінде көптеген қабырғаларға ие болады және М(G)=М[АG].

Дәлелдеме. Х□АG X циклға ие болған жағдайда ғана сызықтық тәуелді
болатындығын дәлелдеу қажет. X өзіне С циклін иемденетіндігін болжаймыз.
Егер С - тесік болса, онда X нөлдік векторға ие болады және ол сызықты
тәуелсіз болады. Егерде С тесік емес болса, онда осы циклдағы әрбір биіктік
С-ның екі қабырғасына сәйкес болады және екінші модуль бойынша векторлар
жиынтығы нөлдік вектор болады. Осының себебінен X сызықтық тәуелді болады.

Енді X сызықтық тәуелсіз деп болжамдаймыз. D және X сызықтық тәуелді
көбейтінділер аламыз. Егер де D нөлдік вектордан тұратын болса, онда X
тесікке және циклға ие болады.

Егер де D нөлдік векторға ие болмаса: өйткені {0, 1} аймағында жалғыз
ғана нөлдік емес элемент - 1 бар болады, онда D-дағы векторлар жиынтығы
нөлдік вектор болып табылады. Бұл D -минимальды сызықтық тәуелді
көбейтінді себебінен болады. Осы айтылғандардан D цикл қабырғаларына ие
екендігі көрінеді және егер қандай да бір биіктікте D инцидентті қабырғасы
болса, онда минимум ретінде тағы да бір оған инцидентті қабырға бар болады.
Аяғында d1 қабырғасын аламыз және v0 v1 биіктіктері осы қабырғаларға
сәйкес болсын. Айталық v1 биіктігіне d2 қандайда бір қабырғасы инцидентті
болсын. Айталық v2 биіктігі d2 қабырғасының екінші ұшы болсын. Осы үрдісті
жалғастырайық. Нәтижесінде екі жүйелілік алынады – v0, v1, ... d1, d2, ...
биіктіктер саны мен D аяқты болатындықтан, мұнда v биіктіктерінің қандайда
бірі қайталануы тиіс. Бұл болған кезде D-дағы цикл табылады. Сәйкес циклмен
X табылады.

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

Тікелей матроидтардың көмегі арқылы әр алуан міндеттерді шешуге өту үшін
осы теориядан тағы да бір маңызды ұғымды қарастыру қажет. Матроидтар базасы
- матроидтардың максималды тәуелсіз көбейтінділері.

Матроидтың қарапайым циклі - матроидтардың минимальды тәуелді
көбейтіндісі.

Екі көбейтінді береміз - М матроидтың барлық мүмкін базаларынан тұратын
көбейтінді, оны ВМ деп белгілейміз және М матроидтың барлық мүмкін
қарапайым циклдарынан тұратын көбейтінді, оны СМ деп белгілейміз.
Матроидтар мұрагерлік қасиеттерге ие болғандықтан, бұл екі көбейтіндінің
кез келгені матроидты толығымен анықтай алады.

Теорема - 2

X көбейтіндісі келесі екі қасиет орындалған жағдайда ғана М матроид
базасының көбейтіндісі болып табылады:

1. В көбейтіндісі бос емес.

2.Егер де В1, В2□В, х□В1, - В2 болса, онда □В2-В1 бар болады. Бұл кезде (В1-
х)□{у}□В.
Дәлелдеме. Онда келтірілген екі қасиет орындалсын делік. В барлық базаға
ие екендігін дәлелдеу қажет. Қайтадан қарама-қайшылықтан дәлелдеме
жүргіземіз. Айталық В1□В бірақ I элементі бар. Ол мұндай
В1□{I}□В, І=В1-В. Дегенмен бұл кезде Ү□В-(В□{I}) элементі жоқ болады.
Айталық В - базалар көбейтіндісі, екі қасиет те орын алатындығын
дәлелдейміз. Алғашқы қасиет көрініп тұр. Екінші қасиетті қарастырамыз, х В1-
В2 бірақ В2-В1 жоқ болады, мұнда В1-х {y} В дегенмен бұл матроидтардың
үшінші қасиетіне қарама-қайшы, өйткені [В1{х}]+1=[В2] және мұндай бар болу
тиіс.
Салдарлары
Кез келген базаның қуаттылығы екі қасиет бойынша бірдей болып табылады.
Матроид рангасы деп оның базасының қуаттылығын атайды.
Теорема - 3
С көбейтіндісі келесі үш қасиет орындалған жағдайда ғана матроидтың
қарапайым цикльдарының көбейтіндісі болып табылады:
1. С элементтерінің ешқайсысы бос көбейтінді болып табылмайды.
2. С-ның ешқандай элементі С-ның басқа элементінің көбейтіндісі болып
табылмайды.
З. Егер де С1 және С2 көбейтіндісі □ С және е □ С1 □ С2 болса, онда
(С1□С2) - е қандайда бір С1 элементіне ие болады.
Дәлелдеме.
Келтірілген екі ... жалғасы
Ұқсас жұмыстар
Алгоритм. Алгоритм қасиеттері
Алгоритм түсінігі
Алгоритм ұғымы
Алгоритм жайлы
Алгоритм тілін оқыту әдістемесі
Алгоритм және алгоритмнің қасиеттері
Құпия кілтті алгоритм
Алгоритм туралы мағлұмат
Алгоритм түрлері және программалау
Алгоритм және алгоритмдеу ұғымдары
Пәндер

Қазақ тілінде жазылған рефераттар, курстық жұмыстар, дипломдық жұмыстар бойынша біздің қор №1 болып табылады.

Байланыс

Qazaqstan
Phone: 777 614 50 20
WhatsApp: 777 614 50 20
Email: info@stud.kz
Көмек / Помощь
Арайлым
Біз міндетті түрде жауап береміз!
Мы обязательно ответим!
Жіберу / Отправить

Рахмет!
Хабарлама жіберілді. / Сообщение отправлено.

Email: info@stud.kz

Phone: 777 614 50 20
Жабу / Закрыть

Көмек / Помощь