1. Kombinatorika elementlari


Chinlik jadvali yordamida funksiyani Jegalkin ko‘pxadi ko‘rinishiga keltirish


Download 143.31 Kb.
bet4/6
Sana07.02.2023
Hajmi143.31 Kb.
#1174699
1   2   3   4   5   6
Bog'liq
diskrit

Chinlik jadvali yordamida funksiyani Jegalkin ko‘pxadi ko‘rinishiga keltirish
(1) formulada deb, quyidagi formulani xosil qilamiz:
(2)
xσ formuladan foydalanib, (2) yig‘indidagi barcha inkor amallaridan qutulishimiz mumkin va natijada Jegalkin ko‘pxadini xosil qilamiz.
Masalan. diz’yunksiyani Jegalkin ko‘pxadi ko‘rinishiga chinlik jadvali yordamida keltirish kerak. (2) formuladan, = .
Demak,
26.To’la orgraf.Izomorf graflar.
Agar G = (V,U) va G'= (V',U') graflarning uchlari to‘plamlari, ya’ni V va V to‘plamlar orasida uchlarning qo‘shnilik munosabatini saqlaydigan o ‘zaro bir qiymatli moslik o ‘rnatish mumkin bo‘lsa, u holda G va G' graflar izomorf graflar deb ataladi. Agar ikki bo‘lakli grafning turli bo‘laklariga tegishli istalgan ikkita uchi qo’shni bo‘lsa, u holda bu graf to‘la ikki bo‘lakli graf deb ataladi. Agar G (V,U ) grafda U kortej faqat qirralardan iborat bo‘lsa, u holda yo‘naltirilmagan (oriyentirlanraagan) 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. Istalgan ikkita uchlari qo‘shni bo‘lgan sirtmoqsiz va karrali qirralarsiz oriyentirlanmagan graf to‘la graf deb ataladi. 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 birbiriga qarama-qarshi bo‘lgan) yoylarga almashtirilsa, natijada to‘la orgraf hosil bo‘ladi. Shuning uchun, to‘la orgrafdagi yoylar soni oriyentirlanmagan to ia grafdagi qirralar sonidan ikki baravar ko‘pdir, ya’ni uchlari m ta bo‘lgan to‘la orgrafdagi yoylar soni 2C darajasi2 indeksi m = m(m -1 ) bo‘ladi.
27. Algoritm. algoritimning determinanatlanuvchanligi.
Algoritmning determinatsiyalanuvchanligi (aniqlanuvchanligi). Boshlang‘ich holatdan farq qiluvchi boshqa holatda aniqlangan miqdorlar sistemasi ilgarigi holatlarda hosil qilingan miqdorlar sistemasi orqali bir qiymatli aniqlanadi . Berilgan ommaviy muam-modagi barcha masalalarni umumiy bir xil shaklda, aniq m a ’lum bo'lgan usul bilan yechish jarayoni algoritm deb ataladi. Berilgan ommaviy muammodagi barcha masalalarni umumiy bir xil shaklda, aniq ma’lum bo'lgan usul bilan yechish jarayoni algoritm deb ataladi. Matematikaning asosiy tushun- chalaridan biri algoritm tushunchasidir. Algoritm so'zi (ba’zan, bu so'z algorifm ko'rinishida yoziladi) IX asrda yashab ijod etgan vatandoshimiz, buyuk matematik Abu Abdullo Muhammad ibn Muso al-Xorazmiy nomining lotincha “Algorithmi” tarzida buzib yozilishidan kelib chiqqan. Algoritmning o‘ziga xos xusu- siyatlari. Endi algoritmning o‘ziga xos xususiyatlarini ko‘rib o‘taylik.1 Algoritmning diskretligi. Algoritm - miqdorlarni shunday ketma-ket qurish jarayoniki, boshlang‘ich holatda miqdorlaming dastlabki chekli sistemasi berilgan bo‘lib, har bir navbatdagi momentda miqdorlar sistemasi ma’lum aniqlangan qonun (dastur) asosida oldingi holatdagi miqdorlar sistemasidan hosil qilinadi. Algoritmning determinatsiyalanuvchanligi (aniqlanuvchanligi). Boshlang‘ich holatdan farq qiluvchi boshqa holatda aniqlangan miqdorlar sistemasi ilgarigi holatlarda hosil qilingan miqdorlar sistemasi orqali bir qiymatli aniqlanadi. Algoritm qadamlarining elementarligi. Ilgarigi miqdorlar siste- masidan keyingisini hosil qilish qonuni sodda qadamlardan iborat boMishi kerak. Algoritmning ommavivligi. Boshlang‘ich miqdorlar sistemasini ayrim potensial cheksiz to‘plamdan tanlash mumkin. Algoritmning natijaviyligi. Miqdorlarni topish jarayoni chekli boMishi va natijani (masalaning yechimini) berishi kerak. Matematik amallar asosiy rolni o‘ynaydigan algoritmlar sonli algoritmlar deb yuritiladi.
28.mulohazalar hisobi, mulohazalr hisobi formulalari

Download 143.31 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling