If вершина y новая

8 then y шыңын қарастыру

9 y ⇐ Q

Тереңдігіне қарай іздеу методы.

Тереңдігіне іздеу-графты көшіру стратегиясындағы көптік орнатылғандардан ең маңыздысы юолып табылады. Бұл қадам жаңа ойларды орындай алатындай және де жанындағылар зерттелгенде, бір қадам артқа тастайды. Тереңдәкке іздеу методы кхптеген аттармен анықталған, мысалы «бэктрекинг», «қайтаруымен іздеу».

Жаңа ұғымдар, ашық және белсенді шыңдардың ізденісі үшін осындай тереңждік мағынасына ие. Және де сол сияқты ізденісте енеді. Бұл бір белсенді шыңының ылғи астамын ар екенін белгілейміз.

Айналып кетуінің орындалуы бастапқы шыңының қатысуымен дегеннен басталады, белсенді қайсыбір және бірден-бір ашық шыңмен болады. Кейін қақтығыс шыңға А қабырға және у шыңы қатысуымен таңдалады. Ол ашық және белсенді болады. Ізденісте енді А шыңы белсенді қалғаны осы кездерден бйқаймыз. Оған барлық қақтығыстың қабырғаларын әлі де зерттеуге болмайды. Ендігі осы сияқты және алдыңғы ізденісте ірбңр кезекті адым ашық шыңның көпшілігінен таңдау бір ғана емес зерттеу қабырғалардан, (х,у) әйтпесе сол қабырға зерттеледі. У жаңа шыңы, ол ашыққа дегенінің қатысуымен айгалады.(уа.

Басты өзгелік ендігі ізденістен, алдыңғы ізденіске тереңдігінің аралық сапасы белсенді, сол ашық шыңдардан ғана құрылады. Нешінші рет шыңның қатысуы соңғы болады. Ол үшін талғамның мынадай ережесінің жүзеге асуы ашық шыңының көпшілігіне сақтап, құрылымымен жіңішесі болфп табылады. Аш-шыңдар ғана осы тәртіпте жіңішке болып бүктеледі, олар арадағы қандай да бір ашылыстың, ал аралық сапа белсенді соңғы шың шық. Сол жүйілік 2.2 суретте көрсетілген.

Жіңішке үшін ашық шыңдарды Sарқылы белгілейміз, қалған белгілер баяғы мағынаны сақтайды, және де алғашқы тараудағы top(s) арқылы мағынасы аз ғана болады. Соңғы қосылған элемент сыртының элементі. Байлныстың бір компоненті айналып кетуінің рәсімі ізденістер әдісінің тереңдікке А шыңымен бағаланады. Мүмкін сонда келесі бейнемен жазуға болады.

Procedure DFS(a)

1 А шыңына тоқталу

2 a ⇒ S

3 while S ≠ ∅ do

4 x = top(S)

5 if емес зерттеу қабырғасы (x, y) бар

6 then зерттеу қабырғасы (x, y)

7 if у жаңа шың

8 then у шыңына тоқталу

9 Sy ⇒

10 else х-ті s –тен алыстату

Тағы бір рет көңіл аударсақ осы рәсімінің негізгі өзгелігіне ізденістер тәрізді рәсімін енді көзге іле аламыз. Алдыңғы ізденісте шың белсенді қойылып, сонымен қалады, әлі-де толық зерттелмегендіктен оның маңайы болмайды., одан кейін ол берік болады.

Алдыңғы ізденісте тереңдігінің, х белсенді шыңының маңайында у жаңа шыңы кездессе, сол стекке салады. Және алдыңғы while топтамасының келесі қайталаушылығында белсенді болады. Бұл ретте х стекте қалады және әлдеқайдағы уақыт аралығында тағы белсенді бола түседі. Әтпесе айтарлық, өақтығыстар х шыңының қабырғалары үздік-үздік зерттеуі қатар болады.

Алгоритмнің барлық бағандарының айналып кетуі, сол жағдайдағы кеңейуінің арасындағы ізденіс. (1-алгоритм). Тек қана стекті ауыстыруы керек. Ал рәсімі BFS-рәсімі DFS.

1-ші және 2-ші сипаттау ізденісі алғашқы тарауды белгіленуі сақталдаы. Және де ізденісі үшін тереңдетіледі. O(m+n) дұрыс арапшылығы қалады, бірақ онығң айғағы бірнеше өзге пайымдарын сұрайды. себебі, енді сол сияқты бірнеше шың реттің белсенді болуы мүмкін. Алайда бас-басы қабырғаға ғана екі рет қарастырылады, сол себептен IF операторы 5 ші жолда then (6-9 жолдар) реттің тармағы. O(m) қайталанылады. Осы оператордың else (10 жол) реттің тармағы O(n) қайталанылады, сол сияқты әрбір бастапқы шыңы стектен бір рет алыстатылуы мүмкін. Арадағы бүтіндікте O(m+n) алынады. Алғашқы тарауда ескертпелер туралы сол жерді сарапшалаған әділдік жасағандар қалады, алдындағы жер нешінші рет сол бағаны қамтиды.

Шыңның өрнегі

Шыңның өрнегінің бағаны деп-түстің мақсатындағы оның шыңдарын айтады. Кәдімгі түстер –ол 1,2...,к сандары. Онда өрнек функция болып табылады, белгілі бір көпшілікте шыңның ббағаны және қабылдаушы тағайынды көпшілікті шың сияқты{1,2,...,3}. Шыңды тағы бөлу көпшілік шыңы ретінде қарастыруға болды. V = V ₁ ∪ V ₂ ∪ … ∪ V_k, V_i – і түсінің көпшілігі үшін. V_i –көпшілкгі түсті сыныптармен атайды. Өрнек дұрыс деп аталады-егерде әрбір түс көпшілікті сыныптармен тәуелсіз болса, айтпесе дұрыс шыңның әрбір екі шектес шыңы әртүрлі түстерді қажет етеді. Тапсырыс туралы өрнекте түстің аздаған санына айталмыш бағаны G дұрыс өрнегін табу құрылады. Сол сан хроматикалық сан бағаны деп аталады және көрсетіледі x(G)

Дұрыс шыңның толық бағаны knбарлық өрнегі бөлек –бөлек түстерді керек етеді. Сол себептен χ(Kn) = n. Егерде қайсы-бірі бағанда толық подграф шыңдарымен, сол осы шыңның мына подграфы к түстерін қажет етеді. Осыған тиіс кез келген бағаны үшін емесабатшылық орындалады. χ(G) ≥ ω(G). (3.1)

Алайда хроматиклық сан үлкен қатал сан болуы мүмкін. Айталық: ұзындықтың топтамасы үшін 5 ω(C5) = 2, ал χ(C5) = 3. Басқа мысалдар 3.3 сіретте көрсетілген.

Онда бағаны нешінші болған шыңдары 4-түсте (шыңның түстері жақшада көрсетілген) бейнеленген. Оны тексеру қиын емес, үш түс осы дұрыс боялған оның бағаны жеткіліксіз. 4-мысалда осы бағанның емесабытшылығы орындалады.

Қабырғаның өрнегі

Түзумен берілген тапсырма туралы шыңның өрнегінің тапсырмасы туралы бағананың қабырғасының өрнегінде бар түстер қабырғаларына қашан тағайындалады. Қабырғаның өрнегі –көрінген ортақ шың, берілген екі қабырғада аламаштаса дұрыс болады. Боялған әртүрлі түстермен. Түстің бағаны G қабырғасының дұрыс өрнегі үшін қжетті, ең төмен саны бағанның хроматикалық әріпсанымен аталады және

X’(G) арқылы көрсетіледі. Δ(G) арқылы шыңның χ′(G). Ең көп дәрежесін белгілейміз.

Сәйкестік және қабырғаның жабындылары. Үмітсіз ортақ шыңдар сәйкестік болғанда қабырғаның көпшілігі қос-қостан аталады. Сәйкестік бағандар көпшілікті өрнегі деп-қабырғаның ортақ шыңы болмау н айтамыз. Тапсырма сәйкестік жайлы ол берілген бағанда сәйкестік үлкен санның өрнегімен құрылады. Ол сан баған үшін G деп алып оны π(G). айтамыз. Өрнекті жабық бағанмен мынадай көпшілікте аталады, егерде оның әрбір өрнегінің ұштарының бағасы қақтығыс болуы бірде бір өрнекпен болуы мүмкін. Қабырғасының аздаған саны қабырғада жабық бағанды G арқылы ρ(G) белгілейміз. Қабырғаның жабындысының шыңдармен оңаша өмір сүруі ғана қалғанын байқаймыз.

Сәйкестік ұйғарымы сияқты шыңның тәуелсіз көпшілігінің ұйғарымын, сәйкестік анда санда қабырғанңы тәуелсіз көпшілігін айтамыз. Сол аналогия тағы тығыз байланыстың өрнегінің жабындыларының арасында қатайады. Сол сияқты шыңның өздерінің арасындағы жабынды тәуелсіз және тоқулы көпшіліктер келісімі. Тіпті бірдей сан білдірсе осы байланысты, ашып-жарып мынадай көріністі ескертеміз, G тәуелсіздігінің а (сандары).

В-ағаштар

Сыртқы жадыдағы деректерді іздеу үшін негізгі «ағаш тәріздес» аппараты В-ағаштар болады. Осы механизмдер негізінде келесі ойлар бар. Біріншіден, жалпы қолжетімдік уақыты дәйекті түрде орналасқан мәліметтер көлемімен емес, магниттік шаласының келу уақытымен анықталатын сыртқы жадыдағы деректер құрылымы жайлы сөз қозғағаннан кейін, бір рет сыртқы жадыға сұрау салған соң бірнеше мәлімет алған тиімді, сонымен қатар бұл жерде негізгі жадының үнемді қолданылуын ескеру қажет. Негізгі жадыны ұйымдастыруды бірдей көлемді парақтар жинағы түрінде қарастыратын болсақ, онда осы парақты сыртқы жадымен мәлімет алмасу бірлігі деп қарастырған жөн. Екіншіден, сыртқы жадыдағы іздеу құрылымын құрастырудың тиімді түрін қолану барысында кез келген кілт бойынша ақпаратты іздеу саны алдын ала мәлім сыртқы жадымен ақпарат алмасуды қажет етуі тиіс.

Классикалық B-ағаштар

Классикалық B-ағаштар механизмі 1970 жылы Бэйер және Маккрейтпен ұсынылған. N ретінің B-ағашы сыртқы жадының сатылы байланысқан беттері (ағаштың әрбір басы – бет) түрінде бейнеленіледі, олар келесі қасиеттерге ие:

Әрбір бет 2*n элементтерінен көп емес (кілтпен бірге жазбалар).

Әрбір бет түбірліктен өзге, n-нен кем емес элементтен құралады.

Егер В-ағаштың ішкі (беттік емес) басы m кілттерінен құралса, онда m+1 бет-тұқымдары бар.

Барлық парақтық беттер бір деңгейде орналасқан.

B+-ағаштар

Классикалық В-ағаштар ұйымдастырылу сызбасы қарапайым, дегенмен практикалық қолданыс үшін тиімді емес. Оның ең басты себебі практикалық қолданыста көбіне сыртқы жадыда тек қана кілттерді емес, сонымен қатар жазбаларды сақтау қажет. В-ағашында элементтер ішкі де, сыртқы да парақтық беттерінде орналасады, ал жазба көлемі үлкен болуы мүмкін. Ішкі беттері көп элементтерден құрала алмайды, оның себебі ағаш терең болуы мүмкіндігінде. Осыған орай, ағаштың төменгі деңгейлерінде кілттер мен жазбаларға қолжету үшін сыртқы жадымен көп мәлімет алмасу қажет.

Деректер қорындағы индекстерді ұйымдастыру үшін B+-ағаштар түрлері

B+-ағаштар деректер қорларындағы индекстерді ұйымдастыру үшін қарқынды түрде қолданылады. Ең алдымен, аталмыш ағаштар екі қасиеттерімен айқындалады: кез келген кілт пен тақырыпты іздеу үшін сыртқы жадымен мәлімет алмасу санының алдын ала болжанылуы мен ағаш бұтақтарының көп болуына байланысты осы мәлімет алмасу санының ең үлкен кестелерді индекстеу кезінде де көп болмауы.

R-ағаштар және олардың кеңістік деректер қорындағы индекстерді ұйымдастыру үшін қолдану

Кеңістік деректер қоры индексін ұйымдастыру үшін қолданылатын В-ағаштары механизмінің тағы бір ұлғайған түрі – R-ағаштары. В-ағаштары сияқты олар бұтақ тәріздес болып келеді, алайда R-ағаштарындағы мәлімет В-ағаштарындағы мәліметтерден айырмашылығы бар. Парақтық беттерде орналасқан кеңістік объектілердің идентификаторларынан өзге R-ағаштарында индекстелетін объектінің шекаралары туралы ақпарат сақталады.

Сыртқы жадыдағы іздеу үшін хештеу әдістері. Хэштеу негізіндегі (қажет мәліметтерді бір рет сұраудан соң алу мүмкіндігі) сыртқы жадыдағы мәліметтерге қол жеткізу идеясы тиімділігі сонша, одан бас тарту қиын. Сыртқы жадыдағы мәліметтерді хеширлеудің авторы Витольд Литвин болып табылады. Бастапқы идея айқын көрінеді: егер хэштеу негізінде мәліметтерді басқару кезінде негізгі жадыда хэш-функция қажетті элементтің адресін өндірсе, онда сыртқы жадыға сұрау салғанда дисктік кеңістіктің блогының нөмірін генерациялау қажет. Басты кедергілер коллизияларға қатысты.

Кеңейетін хэштеу. Кеңейетін хэштеу (Extendible Hashing) негізінде негізгі жадыдағы сандық іздеу ағаштарын қолдануда жатыр. Негізгі жадыда сандық іздеудің бинарлық ағаштары негізінде жасалған анықтама бар, олардың кілттері хэш-функциялар мәні. Осы жағдайда, сандық іздеу ағашындағы іздеу «сәтті» жүргізіледі, басқаша айтқанда сыртқы жадының кейбір блогына алып келеді.

Сызықтық хэштеу. Сызықтық хэштеу идеясы (Витольд Литвин) негізгі жадыда анықтаманы орналастырмауда болып отыр. Әдістің бастысы сыртқы жады блогына жіберу үшін әрқашан хэш-функцияның кіші мәні биттерін қолдану. Егер бөлшектеу қажеттілігі туындаса, онда жіберу дұрыс қалатындай етіліп, блок бойынша қайта үлестіріледі.

Деректер қорындағы индекстерді ұйымдастыру үшін хэштеуді қолдану

Деректер қорында хэштеу әдісі бүгінгі күні сирек қолданылады. Хэштеу әдісін бастапқы кезден қолданып келе жатқан жүйелердің ерекше түрі ретінде Ingres-ті айта аламыз. Оның себебі анық. Хэштеу пайда болған күннен ерекше кілт бойынша іздеуге бағдарланған еді. Ең кең таралған әдістер толыққанды қамтамасыз ете алмайды. Дегенмен, бірте-бірте хэштеу технологиясы және В-ағаштар технологиясымен бірігіп, әлемдегі ең негізгі деректер қорына айналуы мүмкін.

Деректер қорындағы іздеудің жанама әдістері:Байланыс индекстері және биттік шкаланы қолдану негізіндегі индекстер.

Қолданылған әдебиеттердің тізімі: [1]-[23]

Дата добавления: 2014-01-15