Raqamli texnologiyalarni rivojlantirish vazirligi muhammad al-xorazmiy nomidagi
Chuqurlik-birinchi qidirishni qo'llash
Download 290.05 Kb. Pdf ko'rish
|
MI 4
- Bu sahifa navigatsiya:
- DFS yordamida grafikaning kuchli boglangan komponentini toping
- 7. Topologiya
Chuqurlik-birinchi qidirishni qo'llash
DFS yordamida yo'lni topish Foydalanish orqali DFS, biz ikkita tepalik orasidagi yo'lni aniqlaymiz. DFS-ni birinchi tepada qo'llang va dfs traversal yordamida ikkinchi tepaga etib borganligimizni tekshiring. Pseudo-Code: DFS yordamida grafikaning kuchli bog'langan komponentini toping Agar biz biron bir juft tugun o'rtasida grafikaning bog'langan tarkibiy qismidagi biron bir yo'l orqali o'tishga qodir bo'lsak. Grafikning kuchli bog'langan komponentini topish uchun mantiq uchun misol va psevdo-kodni ko'rib chiqamiz. 7. Topologiya (lot. topos — joy, oʻrin va ...logiya) — mat.ning istalgan tabiatli obʼyektlar shakli bilan bogʻliq eng umumiy xossalarni oʻrganuvchi sohasi hamda shu sohaning eng muhim tushunchalaridan biri. Geometriyaning bir necha ming yillik tarixiy rivojlanishi davomida koʻplab tayin chiziklar va sirtlar xossalari oʻrganib kelingan boʻlsa, 19-asrning soʻnggi choragida, bir tomondan, B. Riman, S. Li kabi matematiklar chiziq va sirt tushunchalarini umumlashtirish natijasida ancha keng geometrik obraz — qurama (koʻpxillik ham deyiladi) tushunchasini kiritdilar; ikkinchi tomondan, funksiyalarning turli sinflarini oʻrganish natijasida fransuz matematiklari A. Lebeg (1875— 1941), E. Borel (18711956) va boshqa ishlarida analisis situs (oʻrinjoy tahlili) deb nomlangan yoʻnalish shakllana boshladi. Xuddi shu davrda italiyalik matematik E. Betti (1823—98) koʻpyokdilar haqidagi Eyler teoremasini umumlashtirib, koʻp oʻlchovli koʻpyoqsimon (hozirgi atamaga koʻra, chiziqli boʻlakli) quramalarning murakkablik darajasini belgilovchi koʻrsatkich — Betti sonlarini kiritdi. Bir oz keyin J. A. Puankare yana ham umumiyroq gomologik va fundamental gruppa tushunchalarini qoʻllash natijasida T. mat.ning keyingi taraqqiyotida muhim rol oʻynashini bashorat qildi. 20-asr boshlarida nemis matematigi F. Xausdorf (1868—1942) topologik fazo tushunchasiga taʼrif berdi. Shundan soʻng T.ning jadal surʼatlar bilan rivojlanish davri boshlandi. 20-asrning oʻrtalariga kelib T. algebra bilan bir qatorda butun mat.ning poydevorini tashkil qilishi, mat. sohalari u yoki bu darajadagi nisbatda olingan algebra bilan T. tushuncha va gʻoyalarining sintezidan iborat boʻlishi eʼtirof etildi. Agar istalgan tabiatli X toʻplam oʻz holicha qaralsa, uning elementlari orasida hech bir munosabat boʻlmaydi. Agar X toʻplam metrik fazo boʻlsa, u gʻolda nuqtalar orasida masofani oʻlchash va shu bilan bogʻliq tushunchalarni oʻrganish imkoniyati tugʻiladi. Bunga nisbatan gʻoyat keng tushuncha — nuqtaning qismtoʻplamga yaqinligi yoki nuqtaning atrofi tushunchasidir. Mas., matematik analizning asosiy goyasi — funksiyalarning lokal (yaʼni nuqtaning atrofidagi tabiati bilangina belgilanadigan) xossalari va ulardan kelib chiqadigan natijalarni oʻrganishdan iborat. Bunda a nuqtaning (a—e,yaQe) koʻrinishdagi intervallar majmuasi asosiy rol oʻynaydi. Agar X toʻplamning har bir nuqtasi uchun quyidagi aksiomalarni kanoatlantiradigan atroflari majmuasi koʻrsatilgan boʻlsa, X topologik fazo boʻladi; 1) har bir nukta oʻzining ixtiyoriy atrofiga tegishli; 2) agar U nuktaning atrofi hamda UcW boʻlsa, u holda W ham shu nuqganing atrofi. Shunday qilib, topologik fazo — biror yoʻsinda T. bilan taʼminlangan toʻplamdir. Bunda ana shu majmualar tizimi X fazoning T.si deyiladi. Mas., X toʻplam [a, ] kesmada aniklangan uzluksiz funksiyalardan tashkil topgan boʻlsa, f(x) funksiyaning atrofi qanday funksiyalardan tuzilishiga qarab xossalari bir-biridan farq qiladigan topologik fazolar hosil boʻladi. Odatda, bir toʻplam bir necha usulda topologik fazoga aylantirilishi mumkin. Bunda ularning topologiyalari nuqtalar atroflari majmualari boyligiga qarab oʻzaro taqqoslanadi — bir T. ikkinchisiga nisbatan kuchliroq (boyroq), ikkinchisi esa kuchsizroqdeb ataladi. Mas., barcha x nuqta uchun bittagina atrof X ning oʻzidan iborat boʻlsa, eng kucheiz T., aksincha x ni oʻz ichiga oladigan istalgan toʻplam uning atrofi deb eʼlon qilinsa, eng kuchli (diskret) T. hosil boʻladi. Shuningdek, T. atroflar oʻrniga ochiq toʻplamlar, yopiq toʻplamlar, chegara, yopilma, toʻplamning ochiq yadrosi, atroflar bazasi kabi xilmaxil usulda aniqlanishi mumkin — ularning bari oʻzaro tengkuchlidir. Istalgan toʻplamda turli usulda xilmaxil T. kiritish mumkinligi T. mat.ning universal sohasi ekanligidan dalolat beradi. Download 290.05 Kb. Do'stlaringiz bilan baham: |
Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling
ma'muriyatiga murojaat qiling