T. M. Magrupov, B. M. Mirshaxodjayev

M a s h q la r:
1. A g a r ustunlik grafi kuchli tranzitiv va antirefleksiv b o ‘ lsa, u 
holda tanlov bir kriteriyali masalaga keltirilishini k o ‘ rsating.
2. Binar munosabatlar tilin ing asosiy tushunchalari nimalardan 
iborat.
3. Binar 
munosabatlaming 
berilishining 
qanday 
usullari 
mavjud.
4. E kvivalentlik, tartib va dominirlash munosabatlari deganda 
nima tushuniladi?
59

---

5. T I Z I M L I T A H L I L D A T A N L O V N I A N I Q L A S H  
F U N K S I Y A L A R T I L I
5.1. T anlovn i matematik funksiyasida obyekt tushunchasi.
T aniov funksiyalarida chegaraianishlar
Ta n lovn i ba’ zi xususiyatlari uchinchi umum iyroq tilni qurishga 
olib keldi. Birinchidan, k o ‘ pincha shunday holga duch kelinadiki, 
ikki altem ativa orasidagi ustunlik qolgan boshqa altem ativlarga 
b o g ‘ liq b o ‘ ladi. Masalan, oluvchining choynak yoki kofe qaynatgich 
olishida savdoda kofem avdalagich bor yoki y o ‘ q ligin i ahamiyati 
boMishi mumkin.
Ikkinchidan, shunday holatlarga duch kelish mumkinki, ustunlik 
tushunchasi umuman m a’ nosini y o ‘ qotishi mumkin. Masalan, 
altem ativlar to‘ plam iga nisbatan, « t ip ik » tanlov, « o ‘ rtacha» tanlov, 
« a ’ lo ro g ‘ ini, o rig in a lin i» tanlov deganda ikki altem ativa holatida 
tanlov m a’ nosini y o ‘ qotadi.
T a n lo v funksiyalari tili tanlovni X altem ativalam i ixtiyoriy 
to ‘ plam i ustidagi amal sifatida ifodalaydi va bu to ‘ plam ga uning 
to ‘ plamchasini mos q o ‘ yadi, y a ’ ni
C ( x ) : C (x ) с X
(B elgilash in gliz choise - tanlov so ^ in in g birinchi harfi).
T a n lov funksiyasi to ‘ p!am lar to ‘ plamida aks ettirilishi b o ‘ lib 
(qachonki, tanlov uchun ixtiyoriy to‘ plam ga ta k lif qilinishi mumkin, 
y a 'n i X j c X ) bir to ‘ plamning boshqasiga elem entlarsiz aks ettirilishi 
va to ‘ plam lam ing sanoq o ‘ qiga aks ettirilm asligi o ‘ zig a xos va hali 
to ‘ Iiq 
o ‘ rganilmagan 
matematik 
obyekt 
hisoblanadi. 
T a n lov 
funksiyasida aniqlangan talablami q o ‘ ygan holda, biz a w a lg i 
variantlarda k o ‘ rilgan inasalalami ham ifodalashim iz mumkin.
Y a n g i din ing bosh ustunligi tanlovning murakkab qoidalarini 
qurish 
im koniyatiga egaligidir. 
Bunday 
imkoniyatni 
mumkin 
b o ‘ lgan tanlov funksiyalari soni va n altem ativii to ‘ plamda ustunlik
60

---

graflarining mumkin boMgan soni turlichaligi, y a ’ ni ulami farqini 
ko‘ rsatadi.
Graflar 
soni, 
(b ir 
qobiqni 
borligi 
yoki 
y o ‘ q lig i 
bilan 
farqlanadigan) 
2
-'g a teng. A g a r tanlov uchun p altem ativdan к ta 
ta k lif qilinsa, u holda tanlov funksiyasi soni 2k ga teng. (har bir 
altem ativ yoki С (X k ) ga kirishi mumkin yoki y o ‘ q). Shunday qilib, 
alternativlam i berish variantlarini mumkin b o ‘ lgan soni C nk ga teng, 
u holda tanlov funksiyalarining umumiy soni
П (г * Г = 2 - ~
*=i
K o ‘ rinib 
turganidek, 
tanlov 
funksiyalarining 
turlichaligi 
ustunlik graflarining turlichaligidan anchagina k o ‘ p. Undan tashqari, 
bu yerda tanlovdan v o z kechish im koniyati ham bor, y a ’ ni С ( X i ) 
= 0 b o ‘ sh tanlov, bu ham tanlov qoidalari to ‘ p!am ini kengaytiradi.