1. To’plam va ular ustida amallar



Yüklə 1,06 Mb.
Pdf görüntüsü
səhifə7/8
tarix10.06.2023
ölçüsü1,06 Mb.
#128116
1   2   3   4   5   6   7   8
kombinatorika shippi.

 Marshrutlar va zanjirlar:
16.
 .Eyler va Gamelton graflari va sikllar:
17.
Graflarning metrik xarakteristikasi. Planar graflar. Daraxtlar 
13.
Insidentlik va qo’shnichilik matrissasi.
Graflarni taxlil qilish uchun bir nechta usullar mavjud. Ular 
quyidagilardan iborat: 

Koordinat jadvali: Grafning nuqtalarini va chegaralarini jadval 
shaklida berish. 

Insidentlik matrisa: Grafning nuqtalarini va chegaralarini nuqtalar 
va chegaralar orasidagi bog'lanishlar bilan ifodalangan matrisa 
shaklida berish. 

Qo'shnichilik matrisa: Grafning nuqtalarini va chegaralarini 
nuqtalar orasidagi bog'lanishlar bilan ifodalangan matrisa shaklida 
berish. 
14
. Graflar ustida amallar. 
Graflar ustida amallar: 
1. Grafni birlashtirish: Ikki grafni birlashtirish, ularning barcha 
nuqtalarini va chegaralarini o'z ichiga olgan yangi graf hosil 
qiladi. 
2. 
Grafni kesish: Graf kesishi, ikki grafning umumiy nuqtalarini va 
chegaralarini o'z ichiga olgan yangi graf hosil qiladi

15.
Marshrutlar va zanjirlar: 

Marshrut: Grafda boshlang'ich nuqtadan oxirgi nuqtasigacha 
bo'lgan yo'l. 

Zanjir: Grafda nuqtalardan o'tib, chegaralarni bir marta ishlatib 
boshlang'ich nuqtasidan oxirgi nuqtasigacha bo'lgan yo'l. 
Yo'naltirilgan graf: 

Yo'naltirilgan graf (digraf): Har bir chegaraning yo'nalishi 
aniqlangan graf. 
11.Rekurent munosabatlar metodi. 
Rekurent munosabatlar metodi. 
Agar algoritm o‘zini-o’zi yordamchi algoritm sifatida foydala-
nadigan bo‘lsa, bunday algoritmlar rekursiv deyiladi. 
Rekursiv algoritmlar ikki turga bo‘linadi: 
a) to‘g‘ri rekursiya. Bunda algoritm o‘ziga-o‘zi murojaat qiladi. 
b) yondosh rekursiya. Bunda A algoritm B ga, B algoritm A ga 
murojaat qiladi. 
Rekursiv algoritm yozish uchun avvalo quyidagi shartlat o’rinli 
bo’lishi zarur: 
1) rekkurent munosabat aniqlangan bo’lishi; 
2) shu munosabat uchun boshlang‘ich holatning mavjud bo‘lishi. 
Rekkurent munosabat deganda qaralayotgan jarayonga doir muayyan 
bosqichlarni avvalgi bosqichlar bilan bog‘lovchi munosabatlar 
tushuniladi. Masalan, N!=N·(N−1)! 
formulani 
N! uchun rekkurent 
munosabat deb qarash mumkin. Boshlang‘ich holat esa 1!=1 bo’ladi. 
Rekkurent munоsabatlar metоdining g’оyasi yetaricha sоdda bo’lib, 
qo’yilgan masala uchun qandaydir mulоhazalar yordamida qo’yilgan 
masala o’lchamlari kichikrоq bo’lgan nusxalari оrqali ifоdalash talab 
qilinadi. Bu hоlda har bir nusha-masala o’zining nushasi uchun 
asоsiy masalaga aylanadi. Mazkur jarayon davоm ettirilib
masalaning yechimi ma`lum bo’lgan eng kichik o’lchamli nushasi 
qurilmaguncha davоm ettiriladi. Bunday hоlatni rekkurent 
munоsabatlar usulida “algоritmni o’z ichiga cho’kishi” deb ataladi. 
Eng kichik o’lchamli masala nushasi “cho’kish” jarayonini 
to’htatish 
uchun xizmat qiladi
, chunki оdatda bunday nushaning 
yechimi ma`lum bo’ladi. Shundan keyin eng kichik nusha-
masalaning yechimi ma`lum bo’lgandan fоydalanib, unga asоsiy 
bo’lgan masalaning yechimi tоpiladi. Bu yechim navbatdagi bоsqich 
asоsiy masalasini hal qilish uchun pоydevоr bo’lib hizmat 
qiladi. 
Umuman aytganda
, i-chi bоsqichdagi asоsiy masala i-1-chi 
bоsqich yechimidan fоydalangan hоlda tоpiladi. Bu jarayonni 
“algоritmni suzib chiqishi” tarzida tavsiflanadi. 
Yuqoridagi ma’lumotlarni 
hisobga olsak
, faktorialni hisoblash ma-
salasi uchun rekkurent va boshlang‘ich munosabatlar quyidagicha 
bo‘ladi: 
Ko‘rinib turibdiki, N! 
ni hisoblash uchun 
(N-1)! ma’lum bo‘lishi 
kerak. Lekin, bo‘lgani uchun o‘z navbatida (N-2)! ni topish talab 
qilinadi. (N-2)! esa (N-3)!·(N-2) ga teng va hokazo. 
Bu yerda 
N! ni 
hisoblash algoritmi o‘zining ichiga o‘zi “cho‘kib” borishi hodisasi 
ro‘y bermoqda. Cho‘kish jarayoni boshlang‘ich holat sodir bo‘lgunga 
qadar, ya’ni 1! gacha davom etadi. Shundan keyin, “cho‘kish” 
jarayoni to‘xtaydi, ekanligi haqida ko‘rsatma olgan kompyuter 
yuqoriga qarab “suzib” chiqish bosqichini boshlaydi. Ya’ni, 2!=1, 
2!=1!·2=2, 3!=2!·3=6 va hokazo. 
Bu holat to 
N! hisoblanmaguncha 
davom etaveradi. 
Yuqorida keltirilgan rekursiv algoritmning psevdokodi quyidagicha 
yoziladi: 
algoritm fak(int m) 
// Kiruvchi ma`lumоtlar: natural m sоni 
// Chiquvchi ma`lumоtlar: qiymati m! ga teng bo’lgan sоn 

Yüklə 1,06 Mb.

Dostları ilə paylaş:
1   2   3   4   5   6   7   8




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin