1. Agar funktsiya a ni b ga turli qiymatli akslantirish bo‘lsa, u holda funktsiya a va b to‘plamlarning o‘zaro bir qiymatli mosligi

46-bilet
1. Kombinatorika – diskret matematikaning bir bo‘limi bo‘lib, u ehtimollar nazariyasi, matematik mantiq, sonlar nazariyasi, hisoblash texnikasi va kibernetika sohalarida qo‘llanilgani uchun muhim ahamiyatga ega. Insoniyat o`z faoliyati davomida ko‘p marotaba ayrim predmetlarni barcha joylashtirish usullari sonini sanab chiqish yoki biror bir harakatni amalga oshirishdagi barcha mavjud usullarni aniqlash kabi masalalarga duch keladi.
1) 26 kishini kassada navbatga necha xil usulda joylashtirish mumkin? 2) Xokkey bo‘yicha olimpiya birinchiligida necha xil usulda oltin, kumush va bronza medallarini taqsimlash mumkin. Bunday tipdagi masalalarga kombinatorika masalalari deyiladi. Kombinatorikaning asosiy masalalari.
Kombinatorika masalalari oson degan tushuncha hozirgi kunda eskirdi. Kombinatorika masalalari soni va turi tez sur`atlarda o`smoqda. Ko`pgina amaliy masalalar bevosita yoki bilvosita kombinatorika masalalariga keltirilib yechiladi.Hozirgi kunda kombinatorika usullaridan foydalanib yechiladigan zamonaviy masalalarga quyidagi 5 turdagi masalalar kiradi:1Joylashtirish masalalari – tekislikda predmetlarni joy-joyiga qo`yish;2To`ldirish va qamrab olish masalalari – masalan, berilgan fazoviy shakllarni berilgan shakl va o`lchamdagi eng kam sonli jismlar bilan to`ldirish haqidagi masala;3Marshrutlar haqidagi masala – mukammal reja masalasi, masalan, eng qisqa yo`lni topish masalasi;4Graflar nazariyasining kombinatorik masalalari – tarmoqlarni rejalashtirish masalasi: transport yoki elektr tarmoqlari masalalari, grafni bo`yash haqidagi masala;5Ro`yhatga olish masalasi – biror qoidani kuzatish uchun berilgan elementlar naborini tashkil etuvchi predmetlar sonini topish masalari kabi.Kombinatorika masalalarini yechishda diskret to`plam tadqiq qilinadi, ya`ni bu to`plam alohida ajratilgan elementlardan tashkil topgan deb qaraladi. Ko`p hollarda bu top`lamlar chekli bo`ladi, lekin elementlar soni cheksiz bo`lgan to`plamlar inkor qilinmaydi.
2. Monoton funksiya - oʻsuvchi yoki kamayuvchi funksiyalar. Berilgan funksiya biror oraliqda monoton boʻlishi uchun uning orttirmasi Af(x)=f(x+Ax)-f(x), Dx>0, oraliqda ishorasini oʻzgartirmasligi lozim. Agar Ax>0 boʻlganda D/(x) noldan qatʼiy katta yoki qatʼiy kichik boʻlsa, u holda f(x) qatʼiy monoton funksiya deyiladi. Biror oraliqda differensiyalanuvchi funksiya shu oraliqda monoton boʻlishi uchun uning hosilasi oʻzgarmas ishorani saqlashi zarur va yetarlidir. Teorema. Agar f(x) funksiya X oraliqda (qat`iy) monoton funksiya bo`lsa, u shu oraliqning istalgan nuqtasida uzluksiz bo`ladi yoki faqat birinchi tur uzilishga (sakrashga) ega bo`ladi.Isbot. f(x) funksiya X oraliqda o`suvchi bo`lsin. nuqta X ning ichki nuqtasi , ya`ni nuqtaning biror ( - ; + ) atrofii X ga tegishli bo`lsin. f(x) funksiya o`suvchi bo`lgani uchun barcha x larda f(x) f( ) ya`ni funksiya yuqoridan chegaralangan. Shuning uchun u chekli f( ­- 0) f( ) limitga ega. Xuddi shu kabi chekli f( +0) limit mavjud bo`lib, f( -0) f( ) bo`ladi.Agar f( -0)=f( )=f( +0) bo`lsa, funksiya nuqtada uzluksiz bo`ladi. Aks holda f( -0)< f( +0) bo`lib, funksiyaning birinchi tur uzilish nuqtasi bo`ladi.
3. Eyler sikli. Eyler grafi.Teorema (Eyler 1752). Tekis va bog‘lamli graf uchun tenglik o‘rinlidir, bu yerda , , – yoqlar soni.Isboti. Teoremani isbotlash uchun matematik induksiya usulini grafdagi qirralar soni bo‘yicha qo‘llaymiz. Induksiya usulining bazasi sifatida bo‘lgan holni qaraymiz. Bu holda teoremaning tasdig‘iga ko‘ra bo‘lishi kerak. Haqiqatdan ham, tekis va bog‘lamli graf bo‘lgani uchun, u yagona uchdan tashkil topadi va bu uch yagona (cheksiz) yoqda yotadi, ya’ni va . Demak, bu holda teoremaning tasdig‘i to‘g‘ridir.Induksion o‘tish: teoremaning tasdig‘i uchun to‘g‘ri bo‘lsin deb faraz qilib, uning uchun ham to‘g‘ri ekanligini ko‘rsatamiz. Farazimizga ko‘ra tenglik o‘rinlidir. ta qirraga ega tekis va bog‘lamli grafga ( )- qirrani (uni bilan belgilaymiz) shunday qo‘shish kerakki, bunda qirra graf joylashgan tekislikda yotsin va hosil bo‘lgan graf ham bog‘lamli bo‘lsin. Bu amalni bajarganda quyidagi uchta holdan biri ro‘y beradi:
1) qo‘shilayotgan qirra sirtmoqdir – bu holda qirra, albatta, grafdagi uchlardan biriga insident bo‘lib, yoqlardan birida yotadi va bu yoqni ikkiga (sirtmoq yotgan yoqning sirtmoq chizig‘i bilan chegaralangan ichki va tashqi qismlari) ajratadi, ya’ni uchlar soni o‘zgarmaydi, yoqlar soni esa birga oshadi: ;
2) qo‘shilayotgan qirra grafda bor bo‘lgan ikkita uchlarni tutashtiradi – bu holda ham grafning biror ( qirra yotgan) yoqi ikkiga ajraladi, uchlari soni esa o‘zgarmaydi: ;
3) qo‘shilayotgan qirra sirtmoq emas va u grafdagi uchlardan faqat bittasiga insidentdir – bu holda grafning biror yoqida qirraga insident bo‘lgan bitta boshqa uch yasaladi (grafning uchlari soni bittaga oshadi) va qirra joylashgan yoq yaxlitlikni saqlagan holda qirrani o‘z ichiga oladi (yoqlar soni o‘zgarmaydi): .
Teoremaning tasdig‘idagi tenglik Eyler formulasi deb ataladi. Grafda Eyler tsikli mavjud bulishi uchun: a) Graf bog`langan bo'lishi;
b) Grafning barcha tugunlarining lokal darajalari juft bo`lishi kerak; Grafda Eyler zanjiri mavjud bo`lishi uchun: Graf boglangan bo'lishi;
b) Grafning 2 ta tuguni(boshlanish va oxirgi) lokal darajalari tos bo`lib, solgan barcha tugunlarining lokal darajalari juft bo`lishi kerak.