1. Kombinatorika elementlari

Graflar nazariyasi haqida umumiy m a’lumotlar. 1736- yilda L. Eyler tomonidan o‘sha davrda qiziqarli amaliy masalalardan biri hisoblangan Kyonigsberg1 ko'priklari haqidagi masalaning qo‘yilishi va yechilishi graflar nazariyasining paydo bo‘lishiga asos bo‘ldi. Kyonigsberg shahridagi Pregel daryosi ustida qurilgan yettita ko'prikning 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 A , В , С va D qismlarga bo‘lgan. Shaharning ixtiyoriy qismida joylashgan uydan chiqib yettita ko‘prikdan 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, ushbu bobning 5- paragrafiga qarang) mavjudligi shartlari ham topildi. Bu natijalar e’lon qilingan tarixiy ilmiy ishning birinchi sahifasi 2- shaklda keltirilgan. L. Eyleming bu maqolasi yuz yildan ko‘p vaqt mobaynida graflar nazariyasi bo‘yicha yagona ilmiy ish bo‘lib keldi. XIX asming o‘rtalarida graflar nazariyasi bilan bog‘liq tadqiqotlar G. Kirxgof1 va A. Keli2 ishlarida paydo bo‘ldi. “G raf’ iborasi D. Kyonig3 tomonidan 1936- yilda graflar nazariyasiga bagMshlangan dastlabki darslikda4 uchraydi. Graflar nazariyasi bo‘yicha tadqiqotlar natijalari inson faoliyatining turli sohalarida qo‘llaniladi. Ulardan ba’zilari quyidagilardir: boshqotirmalami hal qilish; qiziqarli o‘yinlar; yo‘llar, elektr zanjirlari, integral sxemalari va boshqarish sistemalarini loyihalashtirish; avtomatlar, bloksxemalar va komp’yuter uchun programmalarni tadqiq qilish va hokazo.Grafning geometrik ifodalanishi. Graflarning turlicha berilish usullari mavjud. Grafning abstrakt matematik ta’rifi uning berilish usullaridan biridir. Grafning abstrakt matematik ta'rifi uni tasavvur qilish, anglash, uning xossalarini o‘rganish va bu xossalarni amalda qoMlash jarayonida ba’zi qiyinchiliklar tug'dirishi tabiiydir. Shuning uchun grafning boshqa berilish usullaridan ham foydalaniladi. Masalan, grafning elementlarini, ya’ni uchlari va qirralarini (yoylarini) yozish yoki aytish grafning berilish usuli sifatida qaralishi munkin. Albatta, grafning yana boshqa berilish usullari ham mavjud. Quyida bu usullaming bir nechasi bilan tanishamiz. Grafning uchlarini tekislikda yoki fazoda nuqtalar bilan, qirralarini (yoylarini) esa mos uchlarni tutashtiruvchi uzluksiz chiziqlar bilan ifodalab, qandaydir diagrammaga - grafning ko‘rgazmali tasviriga ega bo‘lamiz. Agar uchlar to‘plami va bu uchlaming tutashishlarini ko‘rgazmali qilib taqdim qilish kerak bo'lsa, grafning geometrik tasvirlanishiga mos shaklni qog‘ozda chizib grafni tasvirlash mumkin. Shuni ta’kidlaymizki, ba’zi hollarda diagrammada graf uchlari doirachalar yordamida yoki qandaydir boshqa usulda ifodalanadi. Grafning qirralariga (yoylariga) mos chiziqlarning to‘g‘ri yoki egri bo‘lishi va ulaming uzunligi ahamiyatga ega emas. Muhimi, bu chiziqlar uzluksiz bo‘lib, grafning qandaydir ikkita uchlarini tutashtirishi lozim. Agar qirra yo‘nalishga ega bo‘lsa (ya’ni u yoy bo‘lsa), u holda bunday qirrani ifodalovchi chiziqda yo‘nalish biror usul bilan, masalan, strelka bilan ko‘rsatiladi. Ixtiyoriy graf uchun bunday diagrammalarni istalgancha tuzish mukinligi ravshan. Agar biror diagrammada grafning uchlariga mos keluvchi nuqtalar ustma-ust tushmasa, qirralarga mos keluvchi chiziqlar, chetki nuqtalami hisobga olmaganda, umumiy nuqtalarga ega boMmasa, bunday diagramma grafning geom etrik ifodalanishi deyiladi. Shuni ta’kidlash kerakki, bitta graf turlicha geometrik ifodalanishi mumkin. Graflar izomorfligining ta’rifi va grafni geometrik ifodalashning mohiyatidan kelib chiqib, abstrakt ta’rif yordamida ifodalangan graf va uning geometrik ifodalanishi o ‘zaro izomorf bo‘ladi. Tabiiyki, izomorf graflar turlicha geometrik ifodalanishlari mumkin. 1- teorema. Har qanday chekli grafni 3 о ‘Ichovli Evklid1 fazosida2 geometrik ifodalash mumkin. Isboti. Teoremaning quyidagi konstruktiv isbotini keltiramiz. Grafning abstrakt ta’rifiga binoan uning hech bo‘lmasa bitta uchi mavjud. Agar grafda faqat bitta uch bo‘Isa, u holda uni 3 o ‘lchovli Evklid fazosining biror nuqtasi sifatida ifodalaymiz. Agar grafda uchlar bittadan ko‘p bo'lsa, u holda ulami uch oichovli Evklid fazosidagi biror to‘g ‘ri chiziqning (hech qaysi ikkitasi ustma-ust tushmaydigan) nuqtalariga mos keladi deb hisoblaymiz. Shu to‘g‘ri chiziqdan qirralarning (yoylaming) har biriga mos keluvchi turli yarim tekisliklami o‘tkazamiz (graf chekli bo‘lgani uchun buning imkoniyati bor). Har bir qirrani (yoyni) unga mos yarim tekislikda, chetlari mos uchlarni ifodalovchi nuqtalarda bo‘lgan hamda bu to‘g‘ri chiziq bilan boshqa umumiy nuqtasi bo‘lmagan qandaydir chiziq vositasida ifodalaymiz. Yarim tekisliklaming tuzilishiga ko‘ra bu chiziqlar, chetki nuqtalami hisobga olmaganda, umumiy nuqtalarga ega emas
21.Kombinatorikada umumlashgan ko’paytirish qoidasi.
ko‘paytirish qoidasi: agar X to‘plam m elementga, Y to‘plam n elementga ega bo‘lsa, u holda X Y to‘plam (Dekart ko‘paytma) m  n elementga ega bo‘ladi. Haqiqatdan, { , ,..., }, 1 2 m X  x x x { , ,..., } 1 2 n Y  y y y bo‘lsa, X Y to‘plam ushbu mumkin bo‘lgan barcha juftliklardan tashkil topadi: ( , ), 1 1 x y ( , ),..., 1 2 x y ( , ) 1 n x y ( , ), 2 1 x y ( , ),..., 2 2 x y ( , ) 2 n x y …………………………. 10 ( , ), 1 x y m ( , ),..., 2 x y m ( , ) m n x y Ko‘rinib turibdiki, bu juftliklar soni mn ga teng. Buni qisqacha n(X Y)  n(X ) n(Y) ko‘rinishda ham yozish mumkin. Umuman, n ta n x , x ,...,x 1 2 to‘plamlar berilgan bo‘lsa, u holda ( .... ) ( ) ( ) .... ( ) 1 2 n 1 2 n n x  x   x  n x  n x   n x tenglik o‘rinli bo‘ladi. 2-misol. A shahardan B shaharga uchta yo‘l, B dan C ga esa 2 ta yo‘l olib boradi. A shahardan C shaharga necha xil usul bilan borish mumkin? Yechish. A dan B ga 1-, 2- va 3-yo‘llar olib boradi. B shahardan C shaharga a va b yo‘llar olib boradi. U holda A dan C ga qo‘yiladigan usullar bilan borish mumkin: (1,a), (1,b), (2,a), (2,b), (3,a), (3,b). Buni boshqacha usul bilan ham hal qilsa bo‘ladi. A va B gacha boradigan yo‘llarki, tanlash usuli 3 ta, B dan C gacha boradigan yo‘llarni tanlash usuli esa 2 ta. Bunda ko‘paytma qoidasiga ko‘ra, yo‘llarning tartiblangan juftliklarini 32=6 usul bilan tanlash mumkinligi ko‘rinib turibdi. Quyida kombinatorik masalalardan o‘rin almashtirishlar, takrorlanmaydigan o‘rin almashtirishlar, takrorlanmaydigan o‘rinlashtirishlar va guruhlashlarni ko‘rib chiqamiz.
22.mulohazalar algebrsi funksiyasi bul funksiyasi,
Mulohazalar algebrasining argumentli funksiyasi deb, 0 va 1 qiymat qabul qiluvchi funksiyaga aytiladi va uning argumentlari ham 0 va 1 qiymat qabul qiladi. Funksiya o‘zining chinlik jadvali bilan beriladi. har bir satrida avval o‘zgaruvchilarning qiymatlari va shu qiymatlar satrida funksiyaning qiymati beriladi. Oldingi paragraflarda isbot qilgan edikki, ta o‘zgaruvchi uchun qiymatlar satrlarining soni 2ⁿ va funksiyalarning soni ga teng bo‘ladi. Oddiy algebradagi funksiya tushunchasiga o‘xshash, mulohazalar algebrasida ham funksiya tushunchasi kiritilishi mumkin. Argumentlari va o ’zi E2 to’p lamdan qiymatlar qabul qiluvchi funksiya mulohazalar algebrasining funksiyasi deb ataladi. Kon’yunksiya, diz'yunksiya, inkor amallari hamda 0 va 1 elementlari aniqlangan M to’plamda shu mantiqiy amallar bajarilsa, bunday M to ’plam Bul algebrasi deb ataladi. f va g funksiyalar mulohazalar algebrasining funksiyalari, x1,x2,...,xn о ’zgaruvchilar esa ularning hech bo’lmaganda bittasining argumentlari bo’lsin. Agar x1,x2,...,xn argumentlarning barcha qiymatlar satrlari uchun f va g funksiyalarning mos qiymatlari bir xil bo ’Isa, u holda f va g funksiyalar teng kuchli funksiyalar deb ataladi. Agar berilgan funksiyalar teng kuchli bo‘lmasa, u holda ular teng kuchlimas funksiyalar deb yuritiladi.
23.multigraf. pvesdograf. Chekli graflar.
Multigrafning chetlarini belgilashning ikki xil usuli mavjud. Ba'zilarning ta'kidlashicha, bir nechta qirralari bo'lmagan grafiklarda bo'lgani kabi, chekka u bog'laydigan uchlari bilan belgilanadi, lekin har bir chekka bir necha marta takrorlanishi mumkin. Boshqalar esa chekkalarni grafikning uchlari bilan teng elementlari sifatida belgilaydi va ular o'z identifikatsiyasiga ega bo'lishi kerak. Grafik nazariyasida multigraf (yoki psevdograf) bir nechta qirralarning (shuningdek, "parallel" [1] deb ham ataladi) mavjudligini ta'minlaydigan grafik, ya'ni bir xil uchlari bir xil bo'lgan qirralardir. Shunday qilib, ikkita cho'qqi bir nechta qirra bilan bog'lanishi mumkin (shunday qilib, multigraflar gipergraflardan farq qiladi, ulardagi har bir chekka aniq ikkita emas, har qanday sondagi uchlarni birlashtira oladi,
24.kombinatorika takrorli o’rin almashtirish
n ta elementli o’rin almashtirishlar deb bir-biridan faqat elementlarining tartibibilan farq qiladigan n ta elementli birikmalarga aytiladi. Masalan, uchta A, B, Celementdan olti ta o’rin almashtirishbajarish mumkin: ABS, ACV, BAC, SBA, VCA,CAB. n ta elementli o’rin almashtirishlar soni Pn bilan belgilanadi bir necha elementi bir xil bo’lgan n ta elementni o’rin almashtirish takrorlanuvchi o’rin almashtirish deyiladi. kombinatorika deb ataluvchi bo‘limida chekli yoki muayyan ma’noda cheklilik shartini qanoatlantiruvchi to‘plamni (bu to‘plamning elementlari qanday bo‘lishining ahamiyati yo‘q: harflar, sonlar, hodisalar, qandaydir predmetlar va boshqalar) qismlarga ajratish, ularni o'rinlash va o‘zaro joylash ya’ni, kombinatsiyalar, kombinatorik tuzilmalar bilan bog‘liq masalalar o‘rganiladi. Hozirgi davrda kombinatorikaga oid ma’lumotlar inson faoliyatining turli sohalarida qo‘llanilmoqda. Jumladan, matematika, kimyo, fizika, biologiya, lingvistika, axborot texnologiyalari va boshqa sohalar bilan ish ko‘ruvchi mutaxassislar kombinatorikaning xilma-xil masalalariga duch keladilar.
25.post teoremasi noma;lim koeffisentlar usuli yordamida jegalkin ko’p hadiga keltirish
ko‘rinishidagi ko‘pxadga Jegalkin ko‘pxadi deyiladi.