HAQIQIY IKKILIK QIDIRUV

Загружено в:

08.08.2023

Скачано:

0

Размер:

567 KB

Скачать

“ALGORITM VA MA’LUMOTLAR STRUKTURASI” FANIDAN
“HAQIQIY IKKILIK QIDIRUV” MAVZUSIDA TAYYORLAGAN
KURS ISHI

Mundarija
Kirish…………………………………………………………………………….3
I.Asosiy qism
1.1.Graflar va ularning tasvirlanishi…………………………………………..4
1.2.Daraxt va ularni turlari………………………………………………….…11
1.3.Haqiqiy ikkilik qidruv algoritimi……………………………………...…..15
II. Dasturlashga oid
2.1.C++ dasturlash tilida ikkilik qidiruv algoritmi……………………………28
III.Xulosa………………………………………………………………………...34
IV.Foydalanilgan adabiyotlar……………………………………..………….…35
2

Kirish
Qidiruv vazifasi dasturlashda eng keng tarqalgan vazifalardan biridir.
Shuningdek, u ko'rib chiqilayotgan narsaning qo'llanilishini namoyish qilish uchun
ajoyib imkoniyatdir. Qidiruv tizimi hamma sohada ishlatilishi sababli
ma'lumotlar tuzilmalari kompyuterda bajarish ancha oson bo’ladi. Kompyuterda
ma’lumotlarni topish maqsadida maxsus kod kiritilgan kompyuterga shu bilan bir
qatorda global qidiruv tizimida ham huddi shu maqsadda va shunga o’xshash kod
kiritilgan. Qidiruv mavzusida bir nechta asosiy o'zgarishlar mavjud va bu yerda %
bilan ko'plab algoritmlar ishlab chiqilgan. Biz qiladigan asosiy taxmin quyidagi
ma'lumotlar to'plami bo'lib, unda % qidiriladi. Berilgan qiymat belgilangan. Biz bu
N elementlar to'plami deb faraz qilamiz massiv bilan ifodalanadi, deylik element
Ob'ektlar odatda yozuvlar bo'lib, ularning maydonlaridan biri rol o'ynaydi kalit.
Keyin vazifa kalit maydoni teng bo'lgan elementni topishdir berilgan x qiymati,
shuningdek, qidiruv argumenti deb ataladi. Topilgan shartini qanoatlantiruvchi i
indeksi boshqasiga murojaat qilishimizga imkon beradi. topilgan elementning
maydonlari. Bizni faqat% ni topish muammosi qiziqtirgani uchun lekin qidiruv
qilingan ma'lumotlar emas, biz buni taxmin qilamiz Element turi faqat kalitdan
iborat, ya'ni uning o'zi kalit.
Lineer qidiruv Agar ma'lumotlar haqida qo'shimcha ma'lumot bo'lmasa, unda
aniq yechim% nie - qiymatni bosqichma-bosqich oshirib, massivdan ketma-ket
o'ting massivning kerakli qiymat aniq bo'lmagan qismi. Bu yechim ma'lum%
Stno chiziqli qidiruv sifatida. Qidiruv ikkita shartdan birida to'xtatiladi:
1. Element topildi, ya'ni ai = x.
2. Butun massiv skanerdan o‘tkazildi, lekin element topilmadi.
3

Asosiy qism
Graflar va ularning tasvirlanishi
Graflar nazariyasi haqida umumiy ma’lumotlar. 1736 yilda L. Eyler
tomonidan o‘sha davrda qiziqarli amaliy masalalardan biri hisoblangan
Kyonigsberg ko‘priklari haqidagi masalaning qo‘yilishi va yechilishi graflar
nazariyasining paydo bo‘lishiga asos bo‘ldi.
Kyonigsberg shahridagi Pregel daryosi ustida qurilgan yettita ko‘priklar
joylashuvi 1- shakldagi qadimiy xaritada tasvirlangan va qurilishi tartibida 1, 2, 3,
4, 5, 6 va 7 raqamlar bilan belgilangan. Pregel daryosi Kyonigsberg shahrini o‘sha
davrda to‘rtta , , va qismlarga bo‘lgan. Shaharning ixtiyoriy qismida joylashgan
uydan chiqib yettita ko‘priklardan faqat bir martadan o‘tib, yana o‘sha uyga qaytib
kelish mumkinmi? Kyonigsberg ko‘priklari haqidagi bu masalani hal qilish
jarayonida graflarda maxsus marshrut (hozirgi vaqtda graflar nazariyasida bu
marshrut Eyler sikli nomi bilan yuritiladi, mavjudligi shartlari ham topildi. Bu
natijalar e’lon qilingan tarixiy ilmiy ishning birinchi sahifasi 2- shaklda keltirilgan.
L. Eylerning bu maqolasi yuz yildan ko‘p vaqt mobaynida graflar nazariyasi
bo‘yichayagona ilmiy ish bo‘lib keldi. XIX asrning o‘rtalarida graflar nazariyasi
bilan bog‘liq tadqiqotlar G. Kirxgof va A. Keli ishlarida paydo bo‘ldi. “Graf”
iborasi D. Kyonig tomonidan 1936 yilda graflar nazariyasiga bag‘ishlangan
dastlabki darslikda uchraydi. Graflar nazariyasi bo‘yicha tadqiqotlar natijalari inson
faoliyatining turli sohalarida qo‘llaniladi. Ulardan ba’zilari quyidagilardir:
boshqotirmalarni hal qilish; qiziqarli o‘yinlar; yo‘llar, elektr zanjirlari, integral
sxemalari va boshqarish sistemalarini loyihalashtirish; avtomatlar, blok-sxemalar va
komp’yuter uchun programmalarni tadqiq qilish va hokazo.
Grafning abstrakt ta’rifi va u bilan bog‘liq boshlang‘ich tushunchalar.
Avvalo, grafning abstrakt matematik tushuncha sifatidagi ta’rifini va boshqa
ba’zi sodda tushunchalarni keltiramiz. qandaydir bo‘shmas to‘plam bo‘lsin.
4

Uning va elementlaridan tuzilgan ko‘rinishdagi barcha juftliklar
(kortejlar) to‘plamini (to‘plamning o‘z-o‘ziga Dekart ko‘paytmasini) bilan
belgilaymiz.
Bundan buyon grafni belgilashda yozuv o‘rniga yozuvdan
foydalanamiz. Grafning tashkil etuvchilarini ko‘rsatish muhim bo‘lmasa, u holda
uni lotin alifbosining bitta harfi, masalan, bilan belgilaymiz.
graf berilgan bo‘lsin. to‘plamning elementlariga grafning uchlari ,
to‘plamning o‘ziga esa, graf uchlari to‘plami deyiladi.
Graflar nazariyasida “uch” iborasi o‘rniga, ba’zan, tugun yoki nuqta iborasi
ham qo‘llaniladi. Umuman olganda, hanuzgacha graflar nazariyasining ba’zi
iboralari bo‘yicha umumiy kelishuv qaror topmagan. Shuning uchun , bundan
keyingi ta’riflarda, imkoniyat boricha, muqobil (alternativ) iboralarni ham
keltirishga harakat qilamiz. grafning ta’rifiga ko‘ra, bo‘sh kortej bo‘lishi ham
mumkin. Agar bo‘sh bo‘lmasa, u holda bu kortej ( , ) ko‘rinishdagi
juftliklardan 2
tashkil topadi, bunda bo‘lishi hamda ixtiyoriy juftlik kortejda
istalgancha marta qatnashishi mumkin. juftlikni tashkil etuvchi va uchlarning
joylashish tartibidan bog‘liq holda, ya’ni yo‘nalishning borligi yoki yo‘qligiga
qarab, uni turlicha atash mumkin. Agar juftlik uchun uni tashkil etuvchilarning
joylashishya’ni bo‘lsa, juftlikka yo‘naltirilmagan ( oriyentirlanmagan )
qirra (yoki, qisqacha, qirra ) deyiladi. Agar bu tartib muhim, ya’ni bo‘lsa, u
holda juftlikka yoy yoki yo‘naltirilgan ( oriyentirlangan ) qirra deyiladi.
kortejning tarkibiga qarab, uni yo grafning qirralari korteji , yo yoylari korteji ,
yoki qirralari va yoylari korteji deb ataymiz.Grafning uchlari va qirralari (yoylari)
uning elementlari deb ataladi. graf elementlarining soni ( )ga tengdir, bu
yerda grafning uchlari soni va bilan uning qirralari (yoylari) soni belgilangan.
Grafning qirrasi (yoyi), odatda, uni tashkil etuvchi uchlar yordamida ,
yoki , yoki ko‘rinishda belgilanadi. Boshqa belgilashlar ham ishlatiladi:
masalan, yoy uchun yoki , qirra uchun , yoy yoki qirra uchun (ya’ni uchlari
ko‘rsatilmasdan bitta harf vositasida) ko‘rinishda. Graf yoyi uchun uning chetki
uchlarini ko‘rsatish tartibi muhim ekanligini ta’kidlaymiz, ya’ni va yozuvlar
5

bir-biridan farq qiluvchi yoylarni ifodalaydi. Agar yoy ko‘rinishda ifodalangan
bo‘lsa, u holda uning boshlang‘ich uchi , esa oxirgi uchi deb ataladi. Bundan
tashqari, yoy ko‘rinishda yozilsa, u haqida uchdan chiquvchi ( boshlanuvchi )
va uchga kiruvchi ( uchda tugovchi ) yoy deb aytish ham odat tusiga kirgan. Qirra
uchun uning yozuvidagi harflar joylashish tartibi muhim rol o‘ynamaydi va va
elementlar qirraning uchlari yoki chetlari deb ataladi.
Agar grafda yo qirra, yo yoy, yoki yoy topillsa, u holda va uchlar
tutashtirilgan deyiladi. Agar grafning ikkita uchini tutashtiruvchi qirra yoki yoy
bor bo‘lsa, u holda ular qo‘shni uchlar deb, aks holda esa, qo‘shni bo‘lmagan
uchlar deb aytiladi.
Grafning ikkita uchi qo‘shni bo‘lsa, ular shu uchlarni
tutashtiruvchi qirraga ( yoyga ) insident , o‘z navbatida, qirra yoki yoy bu uchlarga
insident deyiladi. Grafda ikkita qirra (yoy) umumiy chetga ega bo‘lsa,
ular qo‘shni qirralar ( yoylar ) deyiladi.
Shuni ta’kidlash kerakki, qo‘shnilik tushunchasi grafning bir jinsli, insidentlik
tushunchasi esa uning turli jinsli elementlari orasidagi munosabatni ifodalaydi.
Ba’zan graf undagi elementlar soniga qarab, ya’ni uchlar
soni va qirralar ( yoylar ) soni ga qarab belgilanadi va bu holda grafni -graf deb
ataydilar.
Agar grafda kortej faqat qirralardan iborat bo‘lsa, u
holda yo‘naltirilmagan ( oriyentirlanmagan ) va faqat yo‘naltirilgan
(oriyentirlangan) qirralardan (ya’ni, yoylardan) tashkil topgan bo‘lsa, u holda
u yo‘naltirilgan ( oriyentirlangan ) graf deb ataladi. Oriyentirlangan graf,
qisqacha, orgraf deb ham ataladi.
Qator hollarda oriyentirlanmagan qirralari ham, oriyentirlangan qirralari ham
bo‘lgan graflar bilan ish ko‘rishga to‘g‘ri keladi. Bunday graflar aralash
graflar deb ataladi.
Agar grafning (orgrafning) korteji tarkibida to‘plamdan olingan
takrorlanuvchi elementlar bo‘lsa, u holda ular karrali yoki parallel
6

qirralar ( yoylar ) deb ataladi. Karrali qirralari yoki yoylari bo‘lgan
graf multigraf deyiladi.
Ikkala chetki (boshlang‘ich va oxirgi) uchlari ustma-ust tushgan qirra (yoy),
ya’ni grafning elementi sirtmoq deb ataladi. Sirtmoq, odatda,
yo‘naltirilmagan deb hisoblanadi. Qirralari (yoylari) orasida sirtmoqlari bo‘lgan
graf psevdograf deyiladi. Umumiy holda uchlar to‘plami va (yoki) qirralar (yoylar,
qirra va yoylar) korteji cheksiz ko‘p elementli bo‘lishi mumkin. Bundan keyin
to‘plam va kortej faqat chekli bo‘lgan graflarni qaraymiz. Bunday
graflar chekli graflar deb ataladi.Hech qanaqa qirra (yoy) bilan bog‘lanmagan
uch yakkalangan ( ajralgan , xolis , yalong‘och ) uch deb ataladi.
Faqat yakkalangan uchlardan tashkil topgan graf (ya’ni, grafda qirralar va
yoylar bo‘lmasa) nolgraf yoki bo‘sh graf deb ataladi. Uchlari soni ga teng bo‘lgan
bo‘sh grafni yoki kabi belgilash qabul qilingan. Istalgan ikkita uchlari qo‘shni
bo‘lgan sirtmoqsiz va karrali qirralarsiz oriyentirlanmagan graf graf deb ataladi.
Uchlari soni ga teng bo‘lgan to‘la graf bilan belgilanadi. Ravshanki , grafning
qirralar soni bo ‘ ladi .
Agar orgrafning istalgan ikkita uchini har bir yo ‘ nalishda tutashtiruvchi faqat
bittadan yoy mavjud bo ‘ lsa , u holda unga to ‘ la orgraf deb ataladi . Ravshanki, to‘la
grafdagi qirralarning har birini ikkita (yo‘nalishlari bir-biriga qarama-qarshi
bo‘lgan) yoylarga almashtirilsa, natijada to‘la orgraf hosil bo‘ladi. Shuning uchun,
to‘la orgrafdagi yoylar soni oriyentirlanmagan to‘la grafdagi qirralar sonidan ikki
baravar ko‘pdir, ya’ni uchlari ta bo‘lgan to‘la orgrafdagi yoylar soni
bo‘ladi. Agar grafning uchlariga qandaydir belgilar, masalan, sonlari mos
qo‘yilgan bo‘lsa, u belgilangan graf deb ataladi.
Agar va graflarning uchlari to‘plamlari, ya’ni va to‘plamlar
orasida uchlarning qo‘shnilik munosabatini saqlaydigan o‘zaro bir qiymatli moslik
o‘rnatish mumkin bo‘lsa, u holda va graflar izomorf graflar deb ataladi. Bu ta’rifni
quyidagicha ham ifodalash mumkin: agar va ularga mos bo‘lgan (
7

, ) uchun ( , ) bo‘lsa, u holda va graflar izomorfdir. Agar izomorf
graflardan biri oriyentirlangan bo‘lsa, u holda ikkinchisi ham, albatta,
oriyentirlangan bo‘lishi va ulardagi mos yoylarning yo‘nalishlari ham bir-birlariga
mos bo‘lishlari shart.
Graf uchiga insident qirralar soni shu uchning lokal darajasi , yoki,
qisqacha, darajasi , yoki valentligi deb ataladi. Grafdagi uchning darajasini
bilan belgilaymiz.
Sirtmoqqa insident bo‘lgan uchning darajasini aniqlashda shuni e’tiborga olish
kerakki, qaralayotgan masalaga bog‘liq holda sirtmoqni bitta qirra deb ham, ikkita
qirra deb ham hisoblash mumkin. Ravshanki, ajralgan uchning darajasi nolga teng.
Darajasi birga teng uch chetki (yoki osilgan ) uch deb ataladi. Chetki (osilgan)
uchga insident qirra ham chetki (yoki osilgan ) qirra deb ataladi.
Agar grafning barcha uchlari bir xil darajaga ega bo‘lsa, u holda bunday
graf darajali regulyar graf deb ataladi. Uch darajali regulyar graf kubik (yoki uch
valentli ) graf deb ataladi. graf nol darajali regulyar graf ekanligini, esa () darajali
regulyar graf ekanligini ta’kidlaymiz.
Ko‘rinib turibdiki , oriyentirlanmagan grafda barcha uchlar darajalarining
yig‘indisi qirralar sonining ikki baravariga teng juft son bo‘ladi, chunki qirralarni
sanaganda har bir qirra hisobda ikki marta qatnashadi. Shunday qilib, XVIII
asrdayoq L. Eyler tomonidan isbotlangan quyidagi tasdiq o‘rinlidir.
1- lemma (“ko‘rishishlar” haqida). Ixtiyoriy oriyentirlanmagan grafda barcha
uchlar darajalari yig‘indisi qirralar sonining ikki baravariga teng.
Agar grafning uchlar to‘plamini o‘zaro kesishmaydigan shunday ikkita qism
to‘plamlarga (bo‘laklarga) ajratish mumkin bo‘lsaki, grafning ixtiyoriy qirrasi bu
to‘plamlarning biridan olingan qandaydir uchni ikkinchi to‘plamdan olingan biror
uch bilan tutashtiradigan bo‘lsa, u holda bunday graf ikki bo‘lakli
graf ( bixromatik yoki Kyonig grafi ) deb ataladi. Ta’rifdan ko‘rinib turibdiki, ikki
bo‘lakli grafning har bir bo‘lagidagi ixtiyoriy ikkita uchlar qo‘shni bo‘la olmaydi.
Biror bo‘lagida faqat bitta uch bo‘lgan to‘la ikki bo‘lakli graf yulduz deb ataladi.
Agar ikki bo‘lakli grafning turli bo‘laklariga tegishli istalgan ikkita uchi qo‘shni
8

bo‘lsa, u holda bu graf to‘la ikki bo‘lakli graf deb ataladi. To‘la ikki bo‘lakli
grafni bilan belgilaymiz, bu yerda va bilan grafning bo‘laklaridagi uchlar sonlari
belgilangan. graf uchun va bo‘lishi ravshan, bu yerda –
grafning uchlari soni, – uning qirralari soni. Grafning ikki bo‘lakli graf bo‘lishi
haqidagi ba’zi qo‘shimcha ma’lumotlar (Kyonig teoremasi) ushbu bobning 4-
paragrafida keltirilgan.
Graflar ustida amallar . Graflar ustida turli amallar bajarish mumkin.
Masalan, graflarning birlashtirish, biriktirish, ko’paytirish, grafni qismlarga
ajratishva hokazo. Eng sodda amallardan biri sifatida grafdan uchni olib tashlash
amalini keltirsa bo’ladi. Bu amalni qo’llash berilgan grafning uchlari to’plamidan
biror element yo’qotishni anglatadi.Natijada uchlari soni 1 taga kam yangi graf
paydo bo’ladi. Bu amalni uchlari soni ikkitadan kam bo’lmagan graflarga qo’llash
mumkin bo’lib, uni bajarish jarayonida olib tashlanayotgan uch bilan birgalikda shu
uchga intsident bo’lgan barcha qirralar ham olib tashlanadi.Eng sodda amallar
qatoriga grafdan qirrani olib tashlash amalini kiritish mumkin. Bu amalga ko’ra,
berilgan grafning qirralari to’plamidan birorta element olib tashlanadi. Berilgan
grafda qirralarini olib tashlashda shu qirraga intsident uchlarni grafda qoldirish ham,
yo’qotish ham mumkin. Agar va grafning barcha qirralari grafning ham qirralari
bo’lsa bo’lsa, u holda graf grafning qism grafi deyiladi.
Agar graf karrali qirralarga ega bo’lmasa u holda uchlari grafning barcha
uchlaridan iborat bo’lgan shunday yagona graf mavjudki , grafdagi barcha juft
uchlar faqat va faqat grafda qo’shni bo’lmagandagina qo’shnidir. Bunday graf
berilgan grafning to’ldiruvchi grafi deyiladi. Berilgan graf uchun to’ldiruvchi
grafni qurish jarayonini ham graflar ustida bajariladigan amallar qatoriga qo’shish
mumkin. graf uchun to’ldiruvchi grafni qurish amalini qo’llash natijasida graf hosil
bo’ladi.munosabatni isbotlash mumkin. Graflar ustida shunday amallarni bajarish
mumkin, ular elementlari soni berilgan grafdagidan ko’proq bo’lgan boshqa
graflarning hosil bo’lishiga olib keladi. Bunday amallar qatoriga uchni qo’shish
amali yoki qirrani qo’shish amalini kiritish mumkin.
9

Grafga yangi uchni qo’shishni turli usul bilan amalga oshirish mumkin.
Masalan, yangi uchni berilgan grafda qo’shish shu grafning va uchlariga intsident
bo’lgan qandaydir qirrasiga qo’shish orqali quyidagicha 2 bosqichda bajarilishi
mumkin qirra berilgan grafdan olib tashlanadi.
1.Hosil bo’lgan grafga ikkita yangi qirralar va uchlarida intsident qirra
hamda va uchlarga intsident qirra qo’shiladi. Bu jarayon grafda qirraga darajasi
ikki bo’lgan yangi uchni qo’shish yoki qirrani 2 ga bo’lish amali deb ataladi.
2.Agar graf grafdan qirrani ikkiga bo’lish amali chekli marta ketma- ket
qo’llash vositasida hosil qilingan bo’lsa, u holda graf grafning bo’linish grafi
deyiladi. Bo’linish graflari izomorf bo’lgan graflar gomeomorf graflar deyiladi.
Ushbu shaklda tasvirlangan graflar izomorf emas, lekin ular gomeomorf, chunki bu
graflarning har biri ushbu Shaklda tasvirlangan bo’linish grafga ega.
Bizga va graflar berilgan bo’lsin. Uchlari to’plami va qirralari korteji kabi
aniqlangan grafga va graflarning birlashmasi (uyushmasi) deyiladi va kabi
belgilanadi.
Misol: uchlari to’plamlari kesishadigan graflarning birlashmasi quyidagi
chhizmada tasvirlangan Agar birlashtirilayotgan graflarning uchlari to’plamlari
kesishmasa, u holda bu graflarning birlashmasi dizyunkt birlashma deyiladi.
Graflarni biriktirish amalini qaraymiz. Bizga va graflar berilgan bo’lsin va graflar
10

birlashtirilishi hamda grafning har bir uchi grafning har bir uchi bilan qirra
vositasida tutashtirilishi natijasida hosil bo’lgan graf va graflarning birikmasi
(tutashmasi) deyiladi va kabi belgilanadi. Agar uchlari to’plamlari kesishmasi
bo’sh bo’lmagan graflarni birlashtirish zarur bo’lsa , u holda hal qilinayotgam
masala xossalarini e’tiborga olish kerak. Graflarni ko’paytirish amali.
Bizga va graflar berilgan bo’lsin. Uchlari to’plami bo’lgan grafning qirralari
kortejini quyidagicha aniqlaymiz: agar va yoki va bo’lsa , u holda bo’ladi, bu
yerda va bunday usul bilan hosil bo’lgan graf graflarning ko’paytmasi deyiladi
va kabi belgilanadi. Graflarning ko’paytmasi ta’rifigaasosan, berilgan va graflarning
ko’paytmasihisoblangan grafdagi uchlari yoki ko’rinishdagi juftliklardan iborat,
bu yerda uchlar faqat va faqat shu holda qo’shni bo’ladiki, qachonki bu uchlarni
(juftliklarni) tashkil qiluvchi elementlarning biri unga mos element bilan ustma-ust
tushgan holda boshqa elementlarda o’z grafiga qo’shni bo’lishsa, bu yerda
munosabatlardanva bo’lishi kelib chiqadi. Dekart ko’paytmalar bilan bog’liq
tuzilmalar ustida bajariladigan amallar boshqalardan o’ziga xosligi bilan ajralib
turadi. Bu o’ziga xoslik graflarni ko’paytirish amalida namoyon bo’ladi. Graflar
ko’paytmasida qatnashgan bironta grafning qirralari katreji bo’sh bo’lsada,
ko’paytirish amalini qo’llash natijasida hosil bo’lgan grafning qirralari kotreji bo’sh
bo’lmasligi ham mumkin. Xaqiqatan ham, yuqorida keltirilgan
graflarningko’paytmasi ta’rifidan kelib chiqadiki, agar graf va graflarning
ko’paytmasi, ya’ni bo’lsa, u holda bo’ladi va kortej elementlari bilan birlashma
elementlari orasida bir qiymatli moslik mavjud. Graflarni ko’paytirish amalini qayta
takror qo’llash usuli bilan graflar nazariyasining muhim sinfini tashkil
etuvchi o’lchovli kublarni aniqlash mumkin. o’lchovli kubuchlari soni ikkiga teng
bo’lgan to’la graf yordamida quyidagi rekkurent formula bilan aniqlanadi.
1.2 Daraxt va ularni turlari
Ikkilik qidiruv daraxti ( BST ), shuningdek, buyurdi yoki saralangan ikkilik
daraxt , a ildiz otgan ikkilik daraxt uning ichki tugunlari har birida tugmachaning
11

chap pastki daraxtidagi barcha tugmachalardan kattaroq va uning o'ng pastki
daraxtidagi tugmachalardan kichikroq kalit saqlanadi. Ikkilik daraxt - bu bir
turi ma'lumotlar tuzilishi raqamlar kabi ma'lumotlarni uyushgan ravishda saqlash
uchun. Ikkilik qidiruv daraxtlari imkon beradi ikkilik qidirish tezkor qidirish,
ma'lumotlar elementlarini qo'shish va olib tashlash uchun va amalga oshirish uchun
ishlatilishi mumkin dinamik to'plamlar va qidiruv jadvallari . BST-dagi tugunlarning
tartibi shuni anglatadiki, har bir taqqoslash qolgan daraxtning yarmini o'tkazib
yuboradi, shuning uchun butun izlanish talab etiladi vaqt bilan
mutanosib The ikkilik logarifma daraxtda saqlanadigan narsalar sonidan. Bu juda
yaxshi chiziqli vaqt (saralanmagan) qatorda kalitlarga ko'ra elementlarni topish
uchun talab qilinadi, ammo tegishli operatsiyalardan sekinroq xash jadvallar .
Ikkilik qidiruv daraxti - bu ildiz otgan ikkilik daraxt ichki tugunlari har birida
kalitni (va ixtiyoriy ravishda bog'liq qiymatni) saqlaydi va har birida odatda
belgilangan ikkita taniqli pastki daraxtlar mavjud chap va to'g'ri . Daraxt qo'shimcha
ravishda qoniqtiradi ikkilik qidirish xususiyati: har bir tugundagi kalit chap pastki
daraxtda saqlangan har qanday tugmachadan kattaroq yoki teng, o'ng pastki
daraxtda saqlangan har qanday tugmachadan kichik yoki teng. [1] :287
Daraxtning
barglarida (yakuniy tugunlarida) hech qanday kalit yo'q va ularni bir-biridan ajratib
turadigan tuzilishga ega emas. Ildizida 8 dona bo ' lgan 9 va chuqurlik 3 o ' lchamdagi
ikkilik qidiruv daraxti Barglari chizilmaydi .
Ko'pincha, har bir tugun tomonidan ko'rsatilgan ma'lumot bitta ma'lumot
elementi emas, balki yozuvdir. Biroq, ketma-ketlik maqsadida tugunlar o'zlarining
tegishli yozuvlarining biron bir qismiga emas, balki ularning kalitlariga qarab
taqqoslanadi. Ikkilik qidiruv daraxtlarining boshqa ma'lumotlar tuzilmalaridan
ustunligi shu bilan bog'liqdir algoritmlarni saralash va qidirish
algoritmlari kabi tartibda o'tish juda samarali bo'lishi mumkin. Ikkilik daraxtda
odatdagi ikkilik qidiruv daraxtini qanday kiritish mumkinligi C ++ :
bekor kiritmoq ( Tugun *& ildiz , int kalit , int qiymat ) { agar ( ! ildiz ) ildiz =
yangi Tugun ( kalit , qiymat ); boshqa agar ( kalit == ildiz -> kalit ) ildiz -> qiymat =
12

$qiymat ; boshqa agar ( kalit < ildiz -> kalit ) kiritmoq ( ildiz -> chap , kalit , qiymat ); boshqa // key> root-> key kiritmoq ( ildiz -> to'g'ri , kalit , qiymat );} Shu bilan bir qatorda, rekursiv bo'lmagan versiya shu kabi qo'llanilishi mumkin. Qaerdan kelganligimizni kuzatish uchun ko'rsatgichdan-ko'rsatkichga foydalanish kodni daraxtning ildiziga tugunni kiritishi kerak bo'lgan holatni aniq tekshirish va ko'rib chiqishdan qochishga imkon beradi: [3] bekor kiritmoq ( Tugun ** ildiz , int kalit , int qiymat ) { Tugun ** yurish = ildiz ; esa ( * yurish ) { int kurka = ( * yurish ) -> kalit ; agar ( kurka == kalit ) { ( * yurish ) -> qiymat = qiymat ; qaytish ; } agar ( kalit > kurka ) yurish = & ( * yurish ) -> to'g'ri ; boshqa yurish = & ( * yurish ) -> chap ; } * yurish = yangi Tugun ( kalit , qiymat );} Yuqorisida, yuqoridagi halokatli protsessual variant daraxtni joyida o'zgartiradi. U faqat doimiy yig'ma bo'shliqdan foydalanadi (va takrorlanadigan versiya ham doimiy stack maydonidan foydalanadi), lekin daraxtning oldingi versiyasi yo'qoladi. Shu bilan bir qatorda, quyidagi kabi Python Masalan, biz kiritilgan tugunning barcha ajdodlarini qayta tiklashimiz mumkin; asl daraxt ildiziga har qanday havola haqiqiy bo'lib qoladi va bu daraxtni a qiladi doimiy ma'lumotlar tuzilishi : def binary_tree_insert ( tugun , kalit , qiymat ): agar tugun == Yo'q : qaytish NodeTree ( Yo'q , kalit , qiymat , Yo'q ) agar kalit == tugun . kalit : qaytish NodeTree ( tugun . chap , kalit , qiymat , tugun . to'g'ri ) agar kalit < tugun . kalit : qaytish NodeTree ( binary_tree_insert ( tugun . chap , kalit , qiymat ), tugun . kalit , tugun . qiymat , tugun . to'g'ri ) qaytish NodeTree ( tugun . chap , tugun . kalit , tugun . qiymat , binary_tree_insert ( tugun . to'g'ri , kalit , qiymat )) Qayta qurilgan qismdan foydalaniladi O (log n ) o'rtacha holatda bo'sh joy va O ( n ) eng yomon holatda. Ikkala versiyada ham ushbu operatsiya eng yomon holatda daraxt balandligi bilan mutanosib vaqt talab qiladi, ya'ni O (log n ) barcha daraxtlar bo'yicha o'rtacha holatda vaqt, lekin O ( n ) eng yomon holatda vaqt. Ikkilik qidirish daraxtlari asosiy hisoblanadi ma'lumotlar tuzilishi kabi mavhum ma'lumotlar tuzilmalarini qurish uchun foydalaniladi to'plamlar , multisets va assotsiativ massivlar . 13$

Ikkilik qidirish buyurtma munosabatini talab qiladi, unga ko'ra har bir element
(element) a ma'nosida boshqa elementlar bilan taqqoslanishi mumkin jami oldindan
buyurtma . Elementning taqqoslashda samarali bo'lgan qismi uning kalit deb ataladi .
Ikki nusxada bo'ladimi, ya'ni. e. daraxtda bir xil kalitga ega bo'lgan turli xil
elementlarga ruxsat beriladi yoki yo'q, buyurtma munosabatlariga bog'liq emas,
balki faqat dasturga bog'liq.
B daraxtining ta'rifi B- da r a xt - bu m uv oz an at l i M - y o' l d ar a xt i va u
m u vo za na t l i na vl i da r a xt s i f at i d a ha m t an i l g an . B u t u gu nl ar i nor der
t r a ve r s al as os i d a t as hk i l e t i l g an i kk i l i k q i d i r u v dar ax t i ga o' xs ha yd i . B
da r a xt i ni ng k os m i k m ur a kk ab l i gi O ( n) di r . Ki r i t i sh va o' ch i r i sh va qt i n i n g
m ur ak ka bl i g i O ( l o g n) .
B d ar a xt i uc hu n t o' g' r i b o' l i sh i k er a k bo 'l ga n b a' zi sh ar t l ar m av j u d:
 Daraxtning balandligi iloji boricha minimal bo'lishi kerak.
 Daraxt barglari ustida hech qanday bo'sh daraxt bo'lmasligi kerak.
 Daraxtning barglari bir xil darajada bo'lishi kerak.
 Barcha tugunlarda ta'til tugunlaridan tashqari eng kam bola bo'lishi kerak.
M tartibidagi B daraxtining xususiyatlari
 Har bir tugunda maksimal M bolalar soni va minimal M / 2 bolalar soni yoki
2 dan maksimalgacha bo'lgan har qanday son bo'lishi mumkin.
 Har bir tugunda maksimal M-1 tugmachalari bo'lgan bolalarga qaraganda
bitta tugmacha kam.
 Klavishlarning joylashishi tugunlar ichida ma'lum bir tartibda. Kalitning chap
tomonida joylashgan subtree-dagi barcha tugmachalar kalitning oldingilari va
kalitning o'ng tomonida joylashganlari vorislar deb ataladi.
 To'liq tugunni kiritish paytida daraxt ikki qismga bo'linadi va ota-ona
tuguniga o'rtacha qiymati bo'lgan kalit qo'yiladi.
 Birlashtirish jarayoni tugunlar o'chirilganda amalga oshiriladi.
B d ar a xt i i k ki l i k va i kk i l i k qi di r uv d ar ax t l ar i u st i d a i sh l a t i l a di ,
bu ni ng as os i y sa ba bi CP U pr ot se s so r y uq or i o' t k az uv ch an l i k ka na l l ar i
14

bi l a n k es hg a u l a ng an xo t i r a i ye r ar xi ya si di r , pr o t s es s or di sk ka p as t
o' t k az uv ch an l i k k an al i or qa l i u l a na di .
Ikkilik daraxtning ta'rifi . I kk i l i k d ar a xt - b u dar ax t t u gu nl ar i u ch un en g
ko 'p i k ki t a ko 'r sa t g i c hg a e ga bo 'l ga n da r a xt t u zi l i s hi . Bu s hu ni
an gl at ad i k i , t ug un ni ng e ng y uq or i d ar aj as i 2 g a t en g va u e r d a no l yo ki bi r
da r a j a l i t ug un h am b o' l i sh i m um k i n .
Ikkilik qidiruv ishlaydi logaritmik vaqt ichida eng yomon holat ,
qilish taqqoslashlar, qaerda - bu massivdagi elementlar soni. Ikkilik qidiruv
tezroq chiziqli qidiruv kichik massivlardan tashqari. Biroq, ikkilik qidiruvni amalga
oshirish uchun birinchi navbatda qatorni saralash kerak. Ixtisoslashgan ma'lumotlar
tuzilmalari kabi tezkor qidiruv uchun mo'ljallangan xash jadvallar , ikkilik
qidiruvdan ko'ra samaraliroq qidirish mumkin. Shu bilan birga, ikkilik qidiruv
yanada kengroq muammolarni hal qilish uchun ishlatilishi mumkin, masalan,
qatorda yo'q bo'lsa ham, maqsadga nisbatan massivda keyingi eng kichik yoki eng
katta elementni topish.
Ikkilik qidiruv algoritmi
Ikki tomonlama qidiruv algoritimining vizualizatsiyasi, bu yerda 7 maqsad
qiymatidir
Sinf Qidiruvalgoritmi
 Ma’lumotlar tarkibi Array
 Eng yomon ishlash O(log n)
 Eng yaxshi holati ishlash O(1)
 O’rtacha ishlash O(log n)
 Eng yomoni kosmik murakkablik O(1)
15

1.3.Haqiqiy ikkilik qidruv algoritmi
Haqiqiy ikkilik qidiruv (inglizcha Bisection usuli ) - monotonik haqiqiy
funktsiyaning berilgan qiymati uchun argumentni topish algoritmi.
Keling, ikkilik qidiruv g'oyasini qo'llaymiz . Funktsiyaning qiymati berilgan
qiymatdan aynan katta va to'liq kichik bo'lgan shunday chegaralarni
tanlaylik. Keling, ushbu segmentning o'rtasida qiymat tanlaylik. Agar u
belgilanganidan kamroq bo'lsa, biz chap chegarani segmentning o'rtasiga
o'tkazamiz. Aks holda, biz o'ng chegarani o'zgartiramiz. Keyinchalik, chegaralarni
toraytirish jarayonini takrorlaymiz. Qachon to'xtash kerak degan savol
tug'iladi. Buning bir necha usullari mavjud.
Qidiruv uchun segment chegarasini tanlash. Birinchidan, chap chegarani
topamiz, ixtiyoriy salbiy nuqtani tanlang (masalan 1-bitta ). Undagi qiymat
belgilangan qiymatdan kattaroq ekan, biz uni ikki barobarga oshiramiz. To'g'ri
chegarani topish uchun o'zboshimchalik bilan ijobiy nuqtani tanlang (masalan bitta
bitta ). Funktsiyaning bu nuqtadagi qiymati berilgan qiymatdan kichik bo'lsa, biz uni
ikki barobarga oshiramiz.
double findLeftBoard (C: double ):
x = -1
esa f (x)> C
x = x * 2
x
qaytaring
double findRightBoard (C: double ):
x = 1
esa f (x) <C
16

x = x * 2
x
qaytaring
double binSearch (C: double ):
chap = chap taxtani topish (C)
o'ng = findRightBoard (C)
while o'ng - chap <eps // Bu erda boshqa chiqish shartidan foydalanish
mumkin
o'rta = (chap + o'ng) / 2
agar f (o'rtada) <C
chap = o'rta
boshqa
o'ng = o'rta
qaytish (chap + o'ng) / 2
Keling, bizga monotonlik beraylik ff va ma'nosi CC ... Biz ikkita boshlang'ich
nuqtani tanlaymiz va f(xbitta) < Cf(xbitta)<C , a f(x2) > Cf(x2)>C ... Ular orqali
to‘g‘ri chiziqni kesib o‘tuvchi to‘g‘ri chiziq o‘tkazamiz y= Cy=C nuqtada (x3, C)
(x3,C) ... Endi nuqta o'rniga xbittaxbitta va x2x2 ochkolarni olaylik x3x3 va x2x2 , va
xuddi shu amalni bajaring va hokazo, ballarni oling xn + 1xn+bitta va xnxn , xayr |
xn - 1-xn| >e|xn-bitta-xn|>e ... Biz har bir keyingi qiymatni
hisoblaymiz xn + 1xn+bitta formuladan foydalanib:
xn + 1=xn - 1+( C- f(xn) ) ⋅ (xn-xn - 1)f(xn) - f(xn - 1)xn+bitta=xn-bitta+(C-
f(xn)) ⋅ (xn-xn-bitta)f(xn)-f(xn-bitta)
Funksiyaning nollarini topish ( C= 0 )(C=0) :
xn + 1=xn - 1-f(xn) ⋅ (xn-xn - 1)f(xn) - f(xn - 1)xn+bitta=xn-bitta-f(xn) ⋅ (xn-xn-
bitta)f(xn)-f(xn-bitta)
17

qo'sh qidiruv (a: double , b: double , eps: double ): // Bu erda a chap
chegara, b o'ng
esa | a - b | > eps
a = b - (b - a) * f (b) / (f (b) - f (a))
b = a - (a - b) * f (a) / (f (a) - f (b))
qaytish b
Ma lumotlar tuzilmasi va algoritmlarda ikkilik qidirish haqidaʼ
Ikkilik qidirish — Ο (log n) vaqti murakkabligi bilan tezkor qidiruv algoritmi.
Ushbu qidirish algoritmi bo linish (divide) va yengish (conque) prinsipi asosida
ʻ
ishlaydi. Ushbu algoritm to g ri ishlashi uchun ma lumotlar to planishi tartiblangan
ʻ ʻ ʼ ʻ
shaklda bo lishi kerak.
ʻ Ikkilik qidirish to plamning ko p qismini o rtasini ʻ ʻ ʻ
taqqoslash orqali ma lum bir narsani qidiradi. Agar mos kelsa, unda element indeksi
ʼ
qaytariladi. Agar o rta qism elementdan kattaroq bo lsa, u holda ushbu element
ʻ ʻ
o rta qismning chap tomonidagi pastki qatorda qidiriladi.
ʻ Aks holda, element o rta ʻ
elementning pastki qismidagi pastki qatorda qidiriladi. Ushbu jarayon pastki
massivda, shuningdek sub-massivning kattaligi nolga tushguncha davom etadi.
Ikkilik qidirsh qanday ishlaydi? Ikkilik qidirish ishlashi uchun maqsad
qatorini tartiblash kerak. Ikkilik qidirish jarayonini tasvirli misol yordamida bilib
olamiz. Quyidagi tartiblangan massivimiz bo lib, ikkilik qidirishdan foydalanib, 31
ʻ
qiymatni qidirish kerakligini taxmin qilaylik.

Birinchidan, ushbu formuladan foydalanib, massivning yarmini aniqlaymiz:
mid = low + (high - low) / 2
18

Bu yerda, 0 + (9 - 0 ) / 2 = 4 (4.5 ning butun qiymati). Shunday qilib, 4
qatorning o rtasida.ʻ
Endi biz 4-chi joyda saqlangan qiymatni, ya ni qidirilayotgan qiymat bilan
ʼ
taqqoslaymiz, ya ni 31-chi joyda 27-ning qiymati mos kelmasligini aniqladik.
ʼ
Qiymat 27 dan katta bo lsa va bizda tartiblangan qator mavjud bo lsa, biz shuni
ʻ ʻ
ham bilamizki, maqsad qiymati massivning yuqori qismida bo lishi kerak.
ʻ

Biz pastligimizni + 1 o rtasiga o zgartiramiz va yana yangi o rtacha qiymatni
ʻ ʻ ʻ
topamiz.
low = mid + 1
mid = low + (high - low) / 2
Bizning yangi o rtamiz endi 7 ga chiqdi. Biz 7-joyda saqlangan qiymatni
ʻ
maqsadli qiymatimiz 31 bilan taqqoslaymiz.
7-joyda saqlangan qiymat mos kelmaydi, aksincha biz qidirayotgan narsadan
ko proqdir. Shunday qilib, qiymat ushbu joyning pastki qismida bo lishi kerak.
ʻ ʻ
19

Shunday qilib, biz yana o rtani hisoblaymiz. Bu safar 5 ga.ʻ
Biz 5-chi joyda saqlangan qiymatni maqsadli qiymatimiz bilan taqqoslaymiz.
Bu match ekanligini aniqladik.
31 maqsadli qiymat 5 manzilda saqlanadi degan xulosaga keldik.
Ikkilik qidirish qidiriladigan qismlarni ikki baravar qisqartiradi va shu bilan
juda kam sonlar uchun taqqoslash sonini kamaytiradi.
Ikkilik qidirish algoritmlarining kodi quyidagicha ko rinishi kerak:
ʻ
Procedure binary_search
A ← sorted array
n ← size of array
x ← value to be searched
Set lowerBound = 1
Set upperBound = n
while x not found
if upperBound < lowerBound
EXIT: x does not exists.
set midPoint = lowerBound + ( upperBound - lowerBound ) / 2
if A[midPoint] < x
set lowerBound = midPoint + 1
if A[midPoint] > x
set upperBound = midPoint - 1
20

if A[midPoint] = x
EXIT: x found at location midPoint
end while
end procedure
"Bo'lib tashla va hukmronlik qil" nimani anglatadi
Dasturlashda, bo'lib tashla va hukmronlik qil — bu algoritmik
paradigma bo'lib, bu paradigmaning asosiy g'oyasi algoritmik masalalarni bosh
masalaga o'xshash kichik qismlarga bo'lib tashlab, ularni rekursiv hal qilishdan
iborat.
Bu paradigmada masala qismlarga bo'linganligi sababli, qism masalalar bosh
masalaga qaraganda kichikroq bo'lishi va bu bo'linish to'xtashi uchun asos
holat bo'lishi kerak (Rekursiya esingizga tushib ketmadimi?). Barcha turdagi bo'lib
tashla va hukmronlik qil algoritmlari 3 ta bosqich dan iborat bo'ladi:
1. Bo'lib tashlash bosqichi. Bunda bosh masala huddi shu masalaga o'xshash
kichikroq masalalarga bo'lib chiqiladi.
2.Hukmronlik bosqichi. Asos holatimizga mos kelib qolgan qism masalalar
huddi u kabi yechiladi.
3.Birlashtirish bosqichi. Bu bosqichda yechilgan kichik qism masalalar qaytib
birlashtirib chiqiladi va bu bosh masala yechimi bo'ladi.
Shu sababli, bo'lib tashla hukmronlik qil paradigmasini 3 ta jumla bilan eslab
qolish mumkin: bo'lib tashla, hukmronlik qil, birlashtir. Boshida tushunish ozroq
qiyin bo'lishi tabiiy, shuning uchun bu paradigma g'oyasini tasvirlab berishga
harakat qilamiz.
Oddiy, bittagina qadamdan iborat bo'lib tashla va hukmronlik qil algoritmi
qanday ishlashini ko'raylik:
21

Agar biz qadamlar sonini oshiradigan bo'lsak, paradigma tasviri quyidagicha
ko'rinish oladi:
Bo'lib tashla va hukmronlik qil paradigmasi asosiy masalalari
Bu paradigma dasturlashning juda mashhur algoritmlari asosini tashkil qiladi:
1. Ikkilik qidirish ( Binary Search )
2. Merge Sort
22

3. Quick Sort
4. Eng yaqin ikki nuqta ( Closest two points )
5. Strassen ko'paytirishi ( Strassen multiplication )
6. Karatsuba algoritmi ( Karatsuba algorithm )
7. Cooley-Tukey algoritmi ( Cooley-Tukey Algorithm )
Bo'lib tashla va hukmronlik qil paradigmasi afzalliklari
 qiyin masalalarni osonlik bilan yechishga imkon beradi
 bu paradigmaga asoslangan algoritmlar oddiy yechimlardan ko'ra tezroq
ishlaydi. Masalan: oddiy saralash bo'lgan Bubble Sortning tezligi O(n²) bo'lsa,
MergeSortniki O(n*logn)
 bunday algoritmlarni parallel hisoblovchi sistemalarda hech qanday
o'zgarishsiz ishlatish mumkin
 bunday algoritmlarni qo'llashda xotira keshidan unumli foydalanish mumkin.
Chunki masalalar bo'linish jarayonida shunday kichik qismlarga ajraladiki, ularni
keshni o'zida turib yechish mumkin bo'ladi.
 haqiqiy sonlar uchun bunday algoritmlar aniqroq ishlaydi, chunki qism
yechimlardagi haqiqiy sonlar ustidagi amallar aniqroq bajariladi (masalan,
ko'paytirish algoritmlarida)
Algoritm qadamlari.Algoritm qanday ishlashini tushundingiz degan
umiddaman. Endi uning qadamlariga o'tadigan bo'lsak.
Eslatma: Ikkilik qidirish algoritmi to'g'ri ishlashi uchun array saralangan
bo'lishi shart!
Bizda n ta elementli saralangan massiv bor va biz undan x elementni
qidirmoqdamiz. Biz qidirish chegarasini belgilash uchun l (left) va r
(right) ko'rsatkichlardan foydalanamiz. Ular array indekslarini ko'rsatib
23

turadi. mid o'zgaruvchi bizda qidirilayotgan sohaning o'rtadagi elementi indeksini
ko'rsatadi
1. Avvaliga l = 0 va r=n-1 bo'ladi (butun boshli array)
2. O'rtadagi element indeksi hisoblanadi: mid = (l + r)/2;
3. O'rtadagi element indeksi bilan qidirilayotgan son x solishtirib ko'riladi
4. Agar son mos kelsa, algoritm shu joyida to'xtaydi.
5. Agar x o'rtadagi sondan katta bo'lsa, left ko'rsatkichni o'rtadan bitta
keyingi elementga suramiz: l=mid + 1;
6. Agar x o'rtadagi sondan kichik bo'lsa, right ko'rsatkichni o'rtadan bitta
oldingi elementga suramiz: r=mid — 1;
7. 2-qadamga qaytiladi.
Ikkilik qidirish algoritmi har bir qadamda n ni ikki baravarga kamaytirgani
uchun algoritm ishlash tezligi O(logn) hisoblanadi.
Ketma-ket qidiruv algoritmi. Mazkur ko’rinishdagi qidiruv agar ma’lumotlar
tartibsiz yoki ular tuzilishi noaniq bo’lganda qo’llaniladi. Bunda ma’lumotlar butun
jadval bo’yicha operativ xotirada kichik adresdan boshlab, to katta adresgacha
ketma-ket qarab chiqiladi. Massivda ketma-ket qidiruv (search o’zgaruvchi topilgan
element tartib raqamini saqlaydi).
Ketma-ket qidiruv algoritmi C++ tilida quyidagicha bo’ladi:
int qidiruv(int key)
{ for (int i=0;i<n;i++)< p=""></n;i++)<>
if (k[i]==key) { search = i;return search;}
search = -1;
24

return search;
}}
Massivda ketma-ket qidiruv algoritmi samaradorligini bajarilgan taqqoslashlar
soni M bilan aniqlash mumkin. M
min = 1, M
max = n. Agar ma’lumotlar massiv
yacheykasida bir xil ehtimollik bilan taqsimlangan bo’lsa, u holda M
o’rt  (n + 1)/2
bo’ladi.
Agar kerakli element jadvalda yo’q bo’lib, uni jadvalga qo’shish lozim bo’lsa, u
holda yuqorida keltirilgan algoritmdagi oxirgi ikkita operator quyidagicha
almashtiriladi .
n=n+1;
k[n-1]:=key;
r[n-1]:=rec; search:=n-1;
return search;
Agar ma’lumotlar jadvali bir bog’lamli ro’yhat ko’rinishida berilgan bo’lsa , u
holda ketma-ket qidiruv ro’yhatda amalga oshiriladi.
Chiziqli bir bog’lamli ro’yhatdan key kalitga mos elementni ketma-ket qidiruv
usuli yordamida izlab topish dasturi.
Node *q=NULL;
Node *p=lst;
25

while (p !=NULL){
if (p->k == key){ search = p;
return search;
}
q = p;
p = p->nxt; }
Node *s=new Node;;
s->k=key;
s->r=rec;
s->nxt= NULL;
if (q == NULL){ s->nxt=lst; lst = s;
} else q->nxt = s;
search= s;
return search;
Ro’yhatli tuzilmaning afzalligi shundan iboratki , ro’yhatga elementni qo’shish
yoki o’chirish tez amalga oshadi, bunda qo’shish yoki o’chirish element soniga
bog’liq bo’lmaydi, massivda esa elementni qo’shish yoki o’chirish o’rta hisobda
barcha elementlarning yarmini siljitishni talab qiladi. Ro’yhatda qidiruvning
samaradorligi taxminan massivniki bilan bir xil bo’ladi.
Teng bo’lish orqali qidiruv (ikkilik qidiruv) algoritmi . Faraz qilaylik,
o’sish tartibida tartiblangan sonlar massivi berilgan bo’lsin. Ushbu usulning asosiy
g’oyasi shundan iboratki , tasodifiy qandaydir A
M element olinadi va u X qidiruv
argumenti bilan taqqoslanadi. Agar A
M =X bo’lsa, u holda qidiruv yakunlanadi; agar
A
M >X bo’lsa, u holda indekslari M dan katta bo’lgan barcha elementlar kelgusi
qidiruvdan chiqarib yuboriladi.
26

$M ixtiyoriy tanlanganda ham taklif qilinayotgan algoritm korrekt ishlaydi. Shu sababali M ni shunday tanlash lozimki, tadqiq qilinayotgan algoritm samaraliroq natija bersin , ya’ni uni shunday tanlaylikki, iloji boricha kelgusi jarayonlarda ishtirok etuvchi elementlar soni kam bo’lsin. Agar biz o’rtacha elementni, ya’ni massiv o’rtasini tanlasak yechim mukammal bo’ladi. Misol uchun butun sonlardan iborat, o’sish bo’yicha tartiblangan massivdan ikkilik qidiruv usuli yordamida key kalitga mos elementni izlash dasturini ko’rib chiqamiz. Dastur kodi: #include <iostream> using namespace std ; int main(){ int n;cout<<"n=";cin>>n; int k[n]; for(int i=0;i>k[i]; int key, search; cout<<"qidirilayotgan elementni kiriting=";cin>>key; int low = 0; while (low <= hi){ int mid = (low + hi) / 2;j++; if (key == k[mid]){ search = mid; cout<<"qidirilayotgan element "<<search+1<<" o’rinda="" turibdi="" va="" u="" "<<j<<"="" ta="" solishtirishda="" toplidi\n";<="" p=""></search+1<<"> system("pause"); 27$ $exit(0); } if (key < k[mid]) hi = mid - 1; else low = mid + 1; } search=-1; cout<<j<<" ta="" solishtirish="" amalga="" oshirildi="" va="" qidirilayotgan="" element="" topilmadi\n";<="" p=""></j<<"> system("pause"); } Dastur natijasi n=6 1 2 3 4 5 6 qidirilayotgan elementni kiriting=6 qidirilayotgan element 6 o'rinda turibdi va u 3 ta solishtirishda toplidi Qidiruv jadvalini qayta tartibga keltirish Umuman olganda, jadvalda har bir elementni qidirish ehtimolligini qandaydir bir qiymat bilan izohlash mumkin. Faraz qilaylik jadvalda qidirilayotgan element mavjud. U holda qidiruv amalga oshirilayotgan jadvalni diskret holatga ega tizim sifatida qarash mumkin hamda unda qidirilayotgan elementni topish ehtimolligi – bu tizim i-chi holati ehtimolligi p(i) deb olish mumkin. Dasturlashga oid 2.1. С ++ dasturlash tilida ikkilik qidruv Dasturlash tillari asosan maxsus so'z va gaplarning mantiqiy konstruktsiyasidan foydalanib dasturlar yaratish imkoniyatini beradi. Ob'ektga yo'naltirilgan yondashuvlar bir kunda o'ylab topilgan emas. Uning paydo bo'lishi dasturiy ta'minotning tabiiy rivojidagi navbatdagi pog’ona, xolos. Vaqt o'tishi bilan qanday uslublar ishlash uchun qulay, qaysinisi noqulay ekanini aniqlash oson bo'lib bordi. Eng muvaffaqiyatli, vaqt sinovidan o'tgan uslublarni o'zida mujassam etadi. 28$

Dastlab dasturlash anchayin boshqotirma ixtiro bo'lib, u dasturchilarga
dasturlarni kommutatsiya bloki orqali kompyuterning asosiy xotirasiga to'g’ridan-
to'g’ri kiritish imkonini berdi. Dasturlar mashina tillarida ikkilik tasavvurda yozilar
edi. Dasturlarni mashina tilid a yozishda tez-tez xatolarga yo'l qo'yilar, kodni kuzatib
borish amalda deyarli mumkin emas edi. Bundan tashqari, mashina kodlaridagi
dastur tushunish uchun g’oyat murakkab edi.
Vaqt o'tishi bilan kompyuterlar tobora kengroq qo'llana boshlandi hamda yuqoriroq
darajadagi protsedura tillari paydo bo'ldi. Bularning dastlabkisi FORTRAN tili edi.
Biroq ob'ektga mo'ljallangan yondashuv rivojiga asosiy ta'sir keyinroq paydo
bo'lgan. Protsedura tillari dasturchiga axborotga ishlov berish dasturini pastroq
darajadagi bir nechta protseduraga bo'lib tashlash imkonini beradi. Keyinchalik
ob'ektga yo'naltirilgan dasturlash yo'nalishiga asos solindi.
Ushbu kurs ishi mavzusi “Sinflar orasidagi munosabatlar” bo'lib, unda nazariy
ma'lumotlar va Jawa muhitida dasturiy vosita yaratiladi. Yaratilgan dastur
“Kutubxona” va “Kitob” asosida sinflar ishlab chiqish va ular orasidagi
munosabatlarni o'rnatishdan iborat. “Kitob” sinfi yordamida har bir Kitob ob'ektlari
tashkil etiladi va ularning qiymatlari kiritilib natijalari olinadi.
Bu yerda oqimdan qiymat qabul qiluvchi o‘zgaruvchining nomi. int n; cout <<
” n = ”; cin >> n; Butun turdagi n o‘zgaruvchisi kiritilgan qiymatni o‘zlashtiradi [3,
Bir paytning o‘zida probel vositasida bir nechta va har xil turdagi qiymatlarni
oqimdan kiritish mumkin. Qiymat kiritish “Enter” tugmasini bosish bilan tugaydi.
Agar kiritilgan qiymatlar soni o‘zgaruvchilar sonidan ko‘p bo‘lsa, «ortiqcha»
qiymatlar bufer xotirada saqlanib qoladi. int x, y; float z; cin >> x >> y >> z; Shuni
qayd etish kerakki, oqimga qiymat kiritishda probel ajratuvchi hisoblanadi. Haqiqiy
sonning butun va kasr qismlari ‘.’ belgisi bilan ajratiladi.
“Prefiks” yoki “postfiks” amal tushunchasi faqat qiymat berish bilan bog‘liq
ifodalarda o‘rinli. x = 5; y = ++x; Ushbu misolda x ning qiymati besh. y ga x ning
qiymatini yuklashdan oldin pre-inkrement amali qo‘llaniladi, x ning qiymati oltiga
29

o‘zgaradi, so‘ngra y o‘zgaruvchisiga olti yuklanadi. Natijada, x ning qiymati ham, y
ning qiymati ham oltiga teng bo‘ladi. x = 5; y = x++; Ushbu misolda x ning qiymati
besh. y ga x ning qiymatini yuklash jarayonida post-inkrement amali qo‘llaniladi, x
ning qiymati y o‘zgaruvchisiga yuklanadi, so‘ngra x ning qiymati bittaga oshiriladi.
Natijada, x ning qiymati - olti, y ning qiymati - beshga teng bo‘ladi. Inkrement va
dekrement amallarini murakkab ifodaning ichida ham ishlatish mumkin. Faqat
bunda tushunarli bo‘lishi uchun inkrement va dekrement amallarini qavs ichiga
olish maqsadga muvofiq. a = 5; b = 2 + (++a); Birinchi ifodada a o‘zgaruvchisiga
besh soni yuklanadi. Keyin esa, 2 + (++a) ifodani bajarish jarayonida avval a
o‘zgaruvchisining qiymati bittaga oshiriladi, so‘ngra uning qiymatiga ikki sonini
qo‘shib, natija b o‘zgaruvchisiga yuklanadi. Natijada, a ning qiymati - olti, b ning
qiymati - sakkizga teng bo‘ladi. a = 5; b = 2 + (a--); Birinchi ifodada a
o‘zgaruvchisiga besh soni yuklanadi. Keyin esa, 2 + (a--) ifodani bajarish
jarayonida, avval, a o‘zgaruvchisining qiymati ifodaga qo‘yib hisoblanib, natija b
o‘zgaruvchisiga yuklanadi, so‘ngra uning qiymati bittaga kamaytiriladi. Natijada, a
ning qiymati to‘rt, b ning qiymati esa yettiga teng bo‘ladi.
Jadvalga n ta talaba FIO va adreslarini kiritamiz. 2. Binar qidiruvni jadvalning
birorta maydonida amalga oshirish uchun jadvalni shu maydoni bo’yicha tartiblab
olish kerak. Shuning uchun masalaning qo’yilishida adresi TTJ bo’lgan talabalarni
topish kerakligi sababli jadval ma’lumotlarini adres maydoni bo’yicha saralab
olamiz. Masalani yechishda to’g’ridan-to’g’ri tanlash orqali saralashdan
foydalanilgan. 3. key kalitga mos elementni izlash chegaralarini aniqlab olamiz.
Dastlab u [0,n] oralig’ida, ya’ni low=0,hi=n. 4. Agar low<=hi bo’lsa, oraliq
o’rtasini hisoblaymiz. mid=(low+hi)/2 5. Agar mid o’rnida turgan talaba adresi TTJ
bo’lsa, element topildi, search=mid va 7-qadamga o’tiladi, aks holda keyingi
qadamga o’tiladi. 6. Agar “TTJ” so’zi alifbo bo’yicha mid o’rnida turgan talaba
adresi qiymatidan kichik bo’lsa, izlash quyi chegarasi o’zgaradi, ya’ni mid o’rnida
turgan elementdan bitta oldingi elementgacha olinadi, ya’ni hi=mid-1. Aks holda,
yuqori chegara o’zgaradi – mid dan keyingi elementdan to oxirgi elementlar oralig’i
olinadi, ya’ni low=mid+1. 4-qadamga o’tiladi. 7. Agar topilgan elementdan oldin
30

turgan elementning (mid-1) ham adres maydoni TTJ bo’lsa, search--, ya’ni bitta
oldingi elementga o’tamiz va shu qadamni boshidan bajaramiz. Aks holda keyingi
qadamga o’tiladi. 8. Joriy (search ko’rsatayotgan) elementdan boshlab adresi “TTJ”
ga teng bo’lgan talaba ma’lumotlarini ekranga chiqaramiz. Agar adresi “TTJ” dan
farq qiladigan talaba chiqib qolsa, algoritm tugallanadi.
Misol:Faqat lotin xarflaridan tuzilganlar ichida ekranga “r” xarfi chiquvchi chiziqli
qidiruv algoritmi tuzilsin va natijalar taxlil qilinsin.
// C++ tilida rekursiyali Binar Qidiruv
# include <stdio.h>
// Rekursiyali qidiruv funksiyasi. U massivdan
// x qaysi o'rinda turganini qaytaradi,
// yoki -1
int binarqidiruv ( int arr[], int l, int r, int x)
{
if (r >= l)
{
int mid = l + (r - l)/2;
// Agar element x ga teng bo'lsa
// o'zi qaytadi
if (arr[mid] == x)
return mid;
// Agar element x dan katta bo'lsa,
// u faqat chap qismni oladi
if (arr[mid] > x)
return binarqidiruv(arr, l, mid-1, x);
31

// Yoki u faqat o'ng qismni oladi
return binarqidiruv(arr, mid+1, r, x);
}
// Bu yerga yetib keladi, qachonki
// x soni massiv ichidan topilmasa
return -1;
}
int main ( void )
{
int arr[] = {2, 3, 4, 10, 40};
//massiv ni elementlar sonini topib olayabmiz
int n = sizeof (arr)/ sizeof (arr[0]);
int x = 10;
int natija = binarqidiruv(arr, 0, n-1, x);
(natija == -1)? printf ("X soni massivni ichidan topilmadi.")
: printf ("X soni massivning %d - elementi.", natija);
return 0;
}
Dastur ishlaganda " X soni massivning 3 - elementi." degan yozuvni qaytaradi.
Sababi massiv elementlari 0 dan boshlanadi.
Binar qidiruvning yana bir ko'rinishi Interative (ingliz tilida ) orqali
ko'rsatamiz.
// C++ tilida interative binar qidiruv
# include <stdio.h>
// Interative binar qidiruv funksiyasi. U massivdan
32

// x qaysi o'rinda turganini qaytaradi,
// yoki -1
int binarqidiruv ( int arr[], int l, int r, int x)
{
while (l <= r)
{
int m = l + (r-l)/2;
// X o'rtadagi elementga tengmi yo'qmi tekshiramiz
if (arr[m] == x)
return m;
// Agar x katta bo'lsa, chapni hisobga olmaymiz
if (arr[m] < x)
l = m + 1;
// Aks holda o'ng tarafni hisobga olmaymiz
else
r = m - 1;
}
// Dastur bu yerga qachonki x element topilmaganda yetib keladi.
return -1;
}
int main ( void )
{
int arr[] = {2, 3, 4, 10, 40};
// Elementlar sonini n ga o'zlashtirayabmiz
int n = sizeof (arr)/ sizeof (arr[0]);
int x = 10;
int natija = binarqidiruv(arr, 0, n-1, x);
(natija == -1)? printf ("X soni massiv ichida topilmadi.")
: printf ("X soni massivning %d o'rnida.", natija);
return 0;
33

}
III.XULOSA
Xulosa qilib aytganda malumotlarni qidirish orqali ko’p masalalarni hal qilsa
bo’ladi. Katta-katta hajmdagi ma’lumotlar orasidan xohlagan ma’lumotlarni izlab
topish mumkin bo’lar ekan. Bu kurs ishi orqali qidiruv tizimining qanchlik qiziqarli
va samarali mavzu ekanligini bildim. Bundan tashqari juda ko’p yangi usillar orqali
malumotlarni qidirish bilan turli xil chiroyli va qiziqarli ma’lumotlarni qidirib
topish, va shu kabi malumotlarni tez qidirish qobilyatini xosil qildim. Bu kurs ishi
orqali men mustaqil oddiy ma’lumotlarni qidira oladigan dasturlar tuza olish
qobilyatiga ega bo’ldim. O’ylaymanki bu kurs ishi dasturlash olamiga kirib
borishimga katta fundament vazifasini o’tab beradi . Ikkilik qidirish to plamningʻ
ko p qismini o rtasini taqqoslash orqali ma lum bir narsani qidiradi. Agar mos
ʻ ʻ ʼ
kelsa, unda element indeksi qaytariladi. Agar o rta qism elementdan kattaroq bo lsa,
ʻ ʻ
u holda ushbu element o rta qismning chap tomonidagi pastki qatorda qidiriladi.
ʻ
Aks holda, element o rta elementning pastki qismidagi pastki qatorda
ʻ
qidiriladi. Xulasa qilib har bir dasturning dastlab algaritmni yaratib olgan maqul.
Agar biz dasturimizning ketma ketligini bilmasak, u dastur biz oylagandan koprak
hajmni egallash mumkin ekan.Ikkilik qidiruv va dasturlash tillari bo’yicha yazilgan
bir necha kitoblar bilan taniship chiqdim va ulardan o’zimga kerakli malumotlarni
oldim . Kurs ishimda malumotlar qidiruv tizilmasi, programmalash texnalogiyalari
masalalari,qidiruv tizimi, ularning xossalari, tasvirlash usullari va tipik
algoritmlarga blok sxemalar tuzish masalalari qaralgandir.

34

$Foydalaningan adabiyotlar 1. Cormen, Tomas H. va boshqalar. Algoritmlarga kirish. Kembrij, Massachusets shtati: MIT Press, 2009. Chop etish 2. Xayneman, Jorj T. va boshq. Algoritmlar yamoqqa. Sebastopol, Kaliforniya: ko'rishReilly Media, 2016. Chop etish 3. Mahmud, Xosam M. Saralash: taqsimot nazariyasi. Xoboken, Nyu- Jersi: Jon Vili va Sons, 2011 yil. Chop etish 4. Tasvirkrediti:https://upload.wikimedia.org/wikipedia/commons/ thumb/e/e6/Merge_sort_algorithm_diagram.svg/500px- M erge_sort_algorithm_diagram.svg.png 5. Tasvirkrediti:https://en.wikipedia.org/wiki/Quicksort#/media/ File:Quicksort-diagram.svg 6. http:\\ziyonet.uz 7. http:\\dastur.uz 8. http:\\Algoritmlash asoslari 9. https :// www . tutorialspoint . com / data _ structures _ algorithms / binary _ search _ algorithm . htm 35$

“ALGORITM VA MA’LUMOTLAR STRUKTURASI” FANIDAN “HAQIQIY IKKILIK QIDIRUV” MAVZUSIDA TAYYORLAGAN KURS ISHI

Mundarija Kirish…………………………………………………………………………….3 I.Asosiy qism 1.1.Graflar va ularning tasvirlanishi…………………………………………..4 1.2.Daraxt va ularni turlari………………………………………………….…11 1.3.Haqiqiy ikkilik qidruv algoritimi……………………………………...…..15 II. Dasturlashga oid 2.1.C++ dasturlash tilida ikkilik qidiruv algoritmi……………………………28 III.Xulosa………………………………………………………………………...34 IV.Foydalanilgan adabiyotlar……………………………………..………….…35 2

Kirish Qidiruv vazifasi dasturlashda eng keng tarqalgan vazifalardan biridir. Shuningdek, u ko'rib chiqilayotgan narsaning qo'llanilishini namoyish qilish uchun ajoyib imkoniyatdir. Qidiruv tizimi hamma sohada ishlatilishi sababli ma'lumotlar tuzilmalari kompyuterda bajarish ancha oson bo’ladi. Kompyuterda ma’lumotlarni topish maqsadida maxsus kod kiritilgan kompyuterga shu bilan bir qatorda global qidiruv tizimida ham huddi shu maqsadda va shunga o’xshash kod kiritilgan. Qidiruv mavzusida bir nechta asosiy o'zgarishlar mavjud va bu yerda % bilan ko'plab algoritmlar ishlab chiqilgan. Biz qiladigan asosiy taxmin quyidagi ma'lumotlar to'plami bo'lib, unda % qidiriladi. Berilgan qiymat belgilangan. Biz bu N elementlar to'plami deb faraz qilamiz massiv bilan ifodalanadi, deylik element Ob'ektlar odatda yozuvlar bo'lib, ularning maydonlaridan biri rol o'ynaydi kalit. Keyin vazifa kalit maydoni teng bo'lgan elementni topishdir berilgan x qiymati, shuningdek, qidiruv argumenti deb ataladi. Topilgan shartini qanoatlantiruvchi i indeksi boshqasiga murojaat qilishimizga imkon beradi. topilgan elementning maydonlari. Bizni faqat% ni topish muammosi qiziqtirgani uchun lekin qidiruv qilingan ma'lumotlar emas, biz buni taxmin qilamiz Element turi faqat kalitdan iborat, ya'ni uning o'zi kalit. Lineer qidiruv Agar ma'lumotlar haqida qo'shimcha ma'lumot bo'lmasa, unda aniq yechim% nie - qiymatni bosqichma-bosqich oshirib, massivdan ketma-ket o'ting massivning kerakli qiymat aniq bo'lmagan qismi. Bu yechim ma'lum% Stno chiziqli qidiruv sifatida. Qidiruv ikkita shartdan birida to'xtatiladi: 1. Element topildi, ya'ni ai = x. 2. Butun massiv skanerdan o‘tkazildi, lekin element topilmadi. 3

Asosiy qism Graflar va ularning tasvirlanishi Graflar nazariyasi haqida umumiy ma’lumotlar. 1736 yilda L. Eyler tomonidan o‘sha davrda qiziqarli amaliy masalalardan biri hisoblangan Kyonigsberg ko‘priklari haqidagi masalaning qo‘yilishi va yechilishi graflar nazariyasining paydo bo‘lishiga asos bo‘ldi. Kyonigsberg shahridagi Pregel daryosi ustida qurilgan yettita ko‘priklar joylashuvi 1- shakldagi qadimiy xaritada tasvirlangan va qurilishi tartibida 1, 2, 3, 4, 5, 6 va 7 raqamlar bilan belgilangan. Pregel daryosi Kyonigsberg shahrini o‘sha davrda to‘rtta , , va qismlarga bo‘lgan. Shaharning ixtiyoriy qismida joylashgan uydan chiqib yettita ko‘priklardan faqat bir martadan o‘tib, yana o‘sha uyga qaytib kelish mumkinmi? Kyonigsberg ko‘priklari haqidagi bu masalani hal qilish jarayonida graflarda maxsus marshrut (hozirgi vaqtda graflar nazariyasida bu marshrut Eyler sikli nomi bilan yuritiladi, mavjudligi shartlari ham topildi. Bu natijalar e’lon qilingan tarixiy ilmiy ishning birinchi sahifasi 2- shaklda keltirilgan. L. Eylerning bu maqolasi yuz yildan ko‘p vaqt mobaynida graflar nazariyasi bo‘yichayagona ilmiy ish bo‘lib keldi. XIX asrning o‘rtalarida graflar nazariyasi bilan bog‘liq tadqiqotlar G. Kirxgof va A. Keli ishlarida paydo bo‘ldi. “Graf” iborasi D. Kyonig tomonidan 1936 yilda graflar nazariyasiga bag‘ishlangan dastlabki darslikda uchraydi. Graflar nazariyasi bo‘yicha tadqiqotlar natijalari inson faoliyatining turli sohalarida qo‘llaniladi. Ulardan ba’zilari quyidagilardir: boshqotirmalarni hal qilish; qiziqarli o‘yinlar; yo‘llar, elektr zanjirlari, integral sxemalari va boshqarish sistemalarini loyihalashtirish; avtomatlar, blok-sxemalar va komp’yuter uchun programmalarni tadqiq qilish va hokazo. Grafning abstrakt ta’rifi va u bilan bog‘liq boshlang‘ich tushunchalar. Avvalo, grafning abstrakt matematik tushuncha sifatidagi ta’rifini va boshqa ba’zi sodda tushunchalarni keltiramiz. qandaydir bo‘shmas to‘plam bo‘lsin. 4

Uning va elementlaridan tuzilgan ko‘rinishdagi barcha juftliklar (kortejlar) to‘plamini (to‘plamning o‘z-o‘ziga Dekart ko‘paytmasini) bilan belgilaymiz. Bundan buyon grafni belgilashda yozuv o‘rniga yozuvdan foydalanamiz. Grafning tashkil etuvchilarini ko‘rsatish muhim bo‘lmasa, u holda uni lotin alifbosining bitta harfi, masalan, bilan belgilaymiz. graf berilgan bo‘lsin. to‘plamning elementlariga grafning uchlari , to‘plamning o‘ziga esa, graf uchlari to‘plami deyiladi. Graflar nazariyasida “uch” iborasi o‘rniga, ba’zan, tugun yoki nuqta iborasi ham qo‘llaniladi. Umuman olganda, hanuzgacha graflar nazariyasining ba’zi iboralari bo‘yicha umumiy kelishuv qaror topmagan. Shuning uchun , bundan keyingi ta’riflarda, imkoniyat boricha, muqobil (alternativ) iboralarni ham keltirishga harakat qilamiz. grafning ta’rifiga ko‘ra, bo‘sh kortej bo‘lishi ham mumkin. Agar bo‘sh bo‘lmasa, u holda bu kortej ( , ) ko‘rinishdagi juftliklardan 2 tashkil topadi, bunda bo‘lishi hamda ixtiyoriy juftlik kortejda istalgancha marta qatnashishi mumkin. juftlikni tashkil etuvchi va uchlarning joylashish tartibidan bog‘liq holda, ya’ni yo‘nalishning borligi yoki yo‘qligiga qarab, uni turlicha atash mumkin. Agar juftlik uchun uni tashkil etuvchilarning joylashishya’ni bo‘lsa, juftlikka yo‘naltirilmagan ( oriyentirlanmagan ) qirra (yoki, qisqacha, qirra ) deyiladi. Agar bu tartib muhim, ya’ni bo‘lsa, u holda juftlikka yoy yoki yo‘naltirilgan ( oriyentirlangan ) qirra deyiladi. kortejning tarkibiga qarab, uni yo grafning qirralari korteji , yo yoylari korteji , yoki qirralari va yoylari korteji deb ataymiz.Grafning uchlari va qirralari (yoylari) uning elementlari deb ataladi. graf elementlarining soni ( )ga tengdir, bu yerda grafning uchlari soni va bilan uning qirralari (yoylari) soni belgilangan. Grafning qirrasi (yoyi), odatda, uni tashkil etuvchi uchlar yordamida , yoki , yoki ko‘rinishda belgilanadi. Boshqa belgilashlar ham ishlatiladi: masalan, yoy uchun yoki , qirra uchun , yoy yoki qirra uchun (ya’ni uchlari ko‘rsatilmasdan bitta harf vositasida) ko‘rinishda. Graf yoyi uchun uning chetki uchlarini ko‘rsatish tartibi muhim ekanligini ta’kidlaymiz, ya’ni va yozuvlar 5

HAQIQIY IKKILIK QIDIRUV

08.08.2023

0

567 KB

Похожие