Raqamli texnologiyalarni rivojlantirish vazirligi muhammad al-xorazmiy nomidagi


Chuqurlik-birinchi qidirishni qo'llash


Download 290.05 Kb.
Pdf ko'rish
bet16/23
Sana18.06.2023
Hajmi290.05 Kb.
#1579618
1   ...   12   13   14   15   16   17   18   19   ...   23
Bog'liq
MI 4

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:
1   ...   12   13   14   15   16   17   18   19   ...   23




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling