|
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
Do'stlaringiz bilan baham: |
