1-blok Toʼplam tushunchasi, toʼplam elementlari Tа’rif 1


Kontaktlar kompozitsiyasi



Download 358,64 Kb.
bet24/24
Sana09.07.2022
Hajmi358,64 Kb.
#760506
1   ...   16   17   18   19   20   21   22   23   24
Bog'liq
Diskret yakuniy barchasi

Kontaktlar kompozitsiyasi.
12.1-Ta’rif. x va u kontaktlarning kompozitsiyasi deb, ularni ketma – ket ulash natijasida xosil buladigan ushbu sxemaga aytiladi:


Kontaktlar yigindisi.
12.2-Ta’rif. x va u kontaktlarning yigindisi deb, ularni parallel ulash natijasida xosil buladigan ushbu sxemaga aytiladi:



Qarama – qarshi kontakt.
12.3-Ta’rif. x kontaktga qarama – qarshi kontakt deb, x kontakt yopik bulganda ochik, x kontakt ochik bulganda yopik bo‘luvchi kontaktga aytiladi.

Quyidagi kontaktlar mos ravishda doimo yopik va doimo ochik kontaktlar deyiladi:

yopik – 1 ochiq - 0
Yuqorida keltirilgan operatsiyalar yordamida uzgaruvchilari kontaktlardan iborat bulgan funksiyalar tuzish mumkin.

39.Kontakt sxemalarni minimallashtirish muammosi.
M inimal kontaktli sxema tushunchasi. Ma’lumki, bitta funksiyaning o'zini har xil kontaktli sxemalar orqali realizatsiya qilish mumkin, chunki funksiyaning DNSh (KNSh) ko‘rinishi yagona emas. Funksiyani kontaktli sxema orqali realizatsiya qilishda, tabiiyki, sxemada mavjud bo'lgan kontaktlar soni mumkin boMguncha eng kam b o‘ lishiga yoki, hech bo‘ lmaganda, shu eng kam sondan salgina ortiqroq boMishiga intilamiz. Bitta o'tkazuvchanlik funksiyasiga ega bo‘ lgan hamma sxemalar ichida mumkin bo‘ lguncha eng kam sonli kontaktga ega bo‘ lgan sxema minimal sxema deb ataladi. Mantiq algebrasi funksiyalarini minimal sxemalar orqali realizatsiya qilish muammosini yechish juda katta ilmiy-amaliy ahamiyatga ega bo‘ lgan dolzarb muammodir. Afsuski, aniq sxemalaming minimal sxema ekanligini isbotlash ayrim hollardagina mumkin. Sxemalarni minimallashtirish muammosi mantiq algebrasi funksiyalarini minimallashtirish muammosi bilan chambarchas bog‘ langandir. T Ayrim hollarda berilgan sxemaning minimal sxema ekanligini ko‘rsatadigan xususiyatlami topish mumkin.

40.Marshrutlar va zanjirlar.


M arshrutlar va zanjirlar haqida umumiy m a’lumotlar. Uchlari to‘plami V = {v1;v2,...,vm} va qirralar korteji U — {ux,u2,...,un} boigan oriyentirlanmagan G = (V,U) graf berilgan bo‘lsin. Bu G grafdagi uchlar va qirralaming har ikki qo‘shni qirralari umumiy chetki uchga ega (•••>V * № “ j2’V " ) ko'rinishidagi chekli yoki cheksiz ketma-ketligi marshrut deb ataladi. Marshrutni uning uchlari ketma-ketligi (...,v/ ,vj ,...) yoki qirralari ketma-ketligi ,uf ,...) ko‘rinishida ham belgilash mumkin. Agar marshrutda qandaydir uchdan oldin uchlar bo‘lmasa, bu uchni marshrutning boshlang‘ich uchi deb, shu uchdan keyin marshrutga tegishli uchlar bo‘lmaganda esa, uni marshrutning oxirgi uchi deb ataydilar. Agar marshrutning boshlang‘ich uchi vp va oxirgi uchi vq bo‘lsa, u holda uni vp uchdan vq uchga yo‘nalgan marshrut yoki chetlari vp va i' bo‘lgan marshrut deb ataladi. Marshrutdagi ikkita qoshni qirralarga tegishli uch ichki uch yoki oraliq uch deb ataladi. Marshrutda qirralar va uchlar takrorlanishi mumkin boMgani uchun marshrutning ichki uchi, bir vaqtning o ‘zida, uning boshlang‘ich va (yoki) oxirgi uchi bo‘lishi ham mumkin va teskarisi, marshrutning boshlang‘ich va (yoki) oxirgi uchi uning ichki uchi bo‘lishi ham mumkin.
Marshrutning uzunligi deb undagi qirralar soniga aytiladi. Turli qirralardan tashkil topgan marshrutga zanjir deb ataladi. Agar zanjirning chetlaridan tashqari barcha uchlari turlicha bo‘lsa, u ho Ida uni oddiy zanjir deb ataydilar. Berilgan (v],v2,...,viS) zanjir yoki oddiy zanjir uchun v,=v5 bo‘lsa, u yopiq zanjir deb ataladi. Hech bo‘lmaganda bitta qirraga ega yopiq oddiy zanjir sikl deb ataladi.

41.Minimizatsiyalash masalasining qo‘yilishi.

42.Graflar xakida tushuncha.


XVIII asrda mashhur shvetsariyalik matematik, mexanik va fizik Leonard Eyler (1707-1783 yy) Kyonigsberg ko’prigi haqidagi masalani yechish uchun birinchi marta graf tushunchasidan foydalanadi. Hozirda bu masala klassik yoki Eyler masalasi nomi bilan mashhur: Shu davrda Kyonigsberg shahrida 2 ta orol bo’lib, ular Pregol daryosining 7 ta ko’prigi bilan birlashtirilgan edi. Masala quyidagicha qo’yilgan edi: Shahar bo’ylab shunday sayr uyushtirish kerakki, bunda har bir ko’prikdan bir marta o’tib yana sayr boshlangan joyga qaytib kelish kerak. Eyler bunday sayr marshruti yo’qligini isbotladi.
Ta’rif . (V, E) sonlar juftligiga graf deyiladi, bu yerda V – iхtiyoriy bo`sh bo`lmagan to`plam, E esa ning qism to`plami , bunda V to`plam elementlarining tartiblanmagan juftliklari to`plami. V to`plam elementlari grafning uchlari deyiladi, E to`plam elementlari esa grafning qirralari deyiladi. Agar V chekli bo`lsa, graf chekli deyiladi, aks holda cheksiz graf deyiladi.

Qirra ikkita uch bilan aniqlanadi. Umumiy uchga ega bo`lgan ikkita qirra qo`shni hisoblanadi. Grafning uchlari va qirralari to`plamini mos ravishda va kabi belgilanadi.


Agar grafda takroriy (karrali) qirralar mavjud bo`lsa, bunday grafga multigraf deyiladi.
Agar grafda karrali qirralar bilan birga uchni o`z-o`zi bilan tutashtiruvchi ilmoqlar ham mavjud bo`lsa, bunday grafga psevdograf deyiladi.
Agar V to`plamning quvvati n ga teng bo`lsa, n soni grafning tartibi deyiladi. Ta’rif 4. Agar V to`plamning quvvati n ga teng bo`lsa, E to`plamning quvvati m ga teng bo`lsa, graf (n, m) graf deyiladi.
Ta’rif 5. Agar grafning ikkita uchi qirra bilan tutashtirilgan bo`lsa, bu uchlar qo`shni uchlar deyiladi.
Ta’rif 6. Grafning bir uchdan chiqqan ikki qirrasi qo`shni qirralar deyiladi.
Ta’rif 7. Agar berilgan uch qirraning oхiri bo`lsa, qirra va uch intsident deyiladi. Ta’rif 8. Agar graf bironta qirraga ega bo`lmasa, bunday graf bo`sh graf deyiladi.

43.DNSh ni soddalashtirishvatupikli DNSh.

44.Qisqartirilgan DNSh.

45.Grafda radius va diametrni topishmasalasi.



Bog‘lamli G graf barcha uchlarining ekssentrisitetlari orasidagi qiymati eng kichigi (minimali) shu grafning radiusi deb ataladi. G grafning radiusi, odatda, r(G) bilan belgilanadi: r(G) = m in e (v ). veV Ravshanki, r(G) = rninm axaf(v],v2) . vjeT v2er Bog‘lamli G grafdagi ekssentrisiteti radiusga teng v0 uch grafning markazi (markaziy uchi) deb ataladi. Tabiiyki, grafning radiusi uning diametridan katta emas va graf bittadan ko‘p markazga ega bo‘lishi ham mumkin. Bundan tashqari, grafning barcha uchlari uning markaziy uchlari boiishi ham mumkin
Bog‘lamli G graf barcha uchlarining ekssentrisitetlari orasidagi qiymati eng kattasi (maksimali) shu grafning diametri deb ataladi. www.ziyouz.com kutubxonasi G grafning diametri, odatda, d(G ) bilan belgilanadi: d(G) = m a x e (v ). Diametr bu grafning istalgan ikki uchi orasidagi v e K mumkin bo‘lgan eng katta masofadir, ya’ni d(G) = max d ( v x, v2) . Uzunligi d(G) ga teng bo‘lgan oddiy zanjir diametral zanjir deb ataladi



1


2 “Mukammal kon’yunktiv normal shakl” iborasini, qisqacha, MKNSh, “mukammal diz’yunktiv normal shakl” iborasini esa, MDNSh deb yozamiz.

3 “Mukammal kon’yunktiv normal shakl” iborasini, qisqacha, MKNSh, “mukammal diz’yunktiv normal shakl” iborasini esa, MDNSh deb yozamiz.

Download 358,64 Kb.

Do'stlaringiz bilan baham:
1   ...   16   17   18   19   20   21   22   23   24




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

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish