tarmoq tushunchasi

DOCX 10 pages 361.9 KB Free download

Page preview (5 pages)

Scroll down 👇
1 / 10
mavzu: tarmoq tushunchasi. tarmoqdagi oqimlar. graf. uch. qirra. orgraf. yoy. tarmoq. to‘plam. blok-sxema. gipergraf. bog‘lamli tarmoq. sirtmoq. yoyning o‘tkazish qobiliyati. uchning chiqish va kirish yarim darajalari. manba. o‘pqon. tarmoqdagi oqim. yoy bo‘ylab oqim. tarmoqdagi oqim miqdori. maksimal oqim. to‘yingan, to‘yinmagan, to‘g‘ri va teskari yoylar. zanjir. tarmoqning “tor joyi”. kesim. manbani o‘pqondan ajratuvchi kesim. kesimning o‘tkazish qobiliyati. minimal kesim. 8.1. tarmoq tushunchasi. graflar nazariyasida hozirgacha ba’zi iboralar bo‘yicha umumiy kelishuv qaror topmaganligini qayd qilgan edik. bu fikr graflar nazariyasining tarmoq va tarmoqqa oid tushunchalari bilan ish ko‘rganda yaqqol namoyan bo‘ladi. ba’zan, “tarmoq” iborasi o‘rniga “to‘r” iborasini ham qo‘llaydilar. masalan, s.v. yablonskiyning 1986 yilda bosilib chiqqan vvedenie v diskretnuyu matematiku (diskret matematikaga kirish) nomli o‘quv qo‘llanmasida ([1]da) graf tushunchasi umumlashtirilib, tarmoqning quyidagi ta’rifi berilgan va “tarmoq” tushunchasi xususida fikrlar ham bayon qilingan. “berilgan to‘plam va har bir elementi dan olingan majmuani (naborni) tarmoq deb ataymiz va bilan belgilaymiz, bu yerda . to‘plamning …
2 / 10
iga ekvivalent bo‘lgan quyidagi ikki ta’rifini keltiramiz: 1) har bir yoyiga manfiymas haqiqiy son mos qo‘yilgan orgraf tarmoq deb ataladi; 2) tarmoq deb shunday juftlikka aytiladiki, bunda – orgraf, esa orgrafning yoylari to‘plamini manfiymas haqiqiy sonlar to‘plamiga akslantiruvchi funksiya. 8.2. tarmoqdagi oqimlar. graflar (orgraflar) bilan bog‘liq ko‘plab tushunchalarni osonlik bilan tarmoqlar uchun ko‘chirish mumkin. tarmoq berilgan bo‘lsin, bu yerda – bog‘lamli graf (yoki orgraf, yo bo‘lmasa, aralash graf), esa grafning yoylarini manfiymas () haqiqiy sonlar to‘plamiga akslantiruvchi funksiya. grafda sirtmoq va karrali qirra va/yoki yoylar bo‘lmasin deb faraz qilamiz. ikkita va uchlarni tutashtiruvchi oriyentirlanmagan yoyni (qirrani) ikkita oriyentirlangan yoylarga almashtirish mumkin deb hisoblaymiz. shuning uchun bundan buyon grafni orgraf deb hisoblash mumkin. ta’kidlaymizki, “tarmoq” tushunchasi har bir yoyga bir necha sonlarni mos qo‘yish imkoniyatini beradi, grafda (orgrafda) esa yoy faqatgina mos uchlarning tutashtirilgan yoki tutashtirilmaganligini aniqlaydi, xolos. har bir yoyga manfiymas sonni mos qo‘yib, bu sonni yoyning o‘tkazish qobiliyati deb …
3 / 10
aqat bitta o‘pqonga ega bo‘lsin. bir necha manba va/yoki o‘pqonga ega bo‘lgan tarmoqning orgrafiga yangi elementlar qo‘shib olish yo‘li bilan yuqoridagi xususiy holga osonlik bilan keltiriladi[footnoteref:1]. [1: masalan, agar manbalar bittadan ko‘p bo‘lsa, u holda yangi (qalbaki) manba tarmoqqa kiritiladi va grafning qalbaki manbaga mos yangi uchi uning haqiqiy manbalariga mos uchlari bilan yoylar vositasida tutashtiriladi. o‘pqonlar ko‘p bo‘lganda ham shunga o‘xshash ish amalga oshiriladi.] orgrafning har bir yoyiga manfiymas sonlar mos qo‘yilgan bo‘lib, biror uchun quyidagi shartlar bajarilsin: 1) 2) orgrafda mavjud barcha yoylar uchun . bu shartlar bajarilganda to‘plamga tarmoqdagi manbadan o‘pqonga yo‘nalgan oqim deb, miqdorga esa, bu oqimning miqdori deb ataladi. 1) va 2) shartlarni qanoatlantiruvchi har bir songa yoy bo‘ylab oqim yoki yoy oqimi deyiladi. yuqoridagi 1) shartga ko‘ra manba va o‘pqondan farqli istalgan uchga “kiruvchi” oqim shu uchdan “chiquvchi” oqimga tengdir, 2) shartga ko‘ra esa, istalgan yoy bo‘ylab oqim miqdori shu yoyning o‘tkashish qobiliyatidan oshmaydi. …
4 / 10
imal oqim emas, chunki berilgan tarmoq uchun miqdori 5 bo‘lgan oqim bor (ushbu paragrafning oxiriga qarang). 7 3 2 5 4 3 1 2 4 2 1- shakl albatta, umumiy holda, tarmoqda bir necha turli maksimal oqimlar bo‘lishi mumkin. maksimal oqimni o‘rganishda quyidagi tushunchalarni kiritish maqsadga muvofiqdir. to‘yingan yoy – bu yoy bo‘ylab oqim miqdori uning o‘tkazish qobiliyatiga teng, to‘yinmagan yoy – bu yoy bo‘ylab oqim miqdori uning o‘tkazish qobiliyatidan kichik. 2- misol. 1- misolda qaralgan tarmoq uchun aniqlangan oqimda va bo‘lgani uchun to‘yinmagan, esa to‘yingan yoylardir. ■ tarmoqdagi oqimlarni o‘rganishda zanjir tushunchasi muhim rol o‘ynaydi. bu yerda zanjir deganda tarmoqdagi yo‘nalishi e’tiborga olinmasdan bir-biriga ulangan yoylar ketma-ketligini tushunamiz. biror zanjirga tegishli yoyning yo‘nalishi zanjirdagi uchlar ketma-ketligini o‘tish yo‘nalishiga mos tushsa, bu yoyni to‘g‘ri yoy deb, aks holda esa, uni teskari yoy deb ataymiz. tarmoqdagi oqimlarni tadqiq qilganda kesim tushunchasi ham muhim hisoblanadi. tarmoqning orgrafi uchlari to‘plami ni o‘zaro kesishmaydigan …
5 / 10
ch uchi manbada va oxirgi uchi o‘pqonda bo‘lgan zanjirdangina iborat bo‘lsa, bu tarmoq bo‘ylab o‘tkazish mumkin bo‘lgan maksimal oqim qiymati shu zanjirni tashkil etuvchi yoylarning o‘tkazish qobiliyatlarining minimal qiymati bilan chegaralangan bo‘ladi. shu tufayli, bu yerda, minimal o‘tkazish qobiliyatiga ega bo‘lgan yoy tarmoqning (zanjirning) “tor joyi” deb atalishi joyizdir. tarmoqdagi manbani o‘pqondan ajratuvchi kesim iborasi istalgan tarmoqda “tor joy” iborasining o‘xshashi sifatida qaralishi mumkin. faraz qilaylik, – tarmoqdagi qandaydir oqim bo‘lsin. bu tarmoqdagi uchdan uchga yo‘nalgan biror yo‘l bo‘ylab oqim shu yo‘l yoylaridagi oqimlarning eng kichik qiymati sifatida aniqlanadi: . tabiiyki, tarmoqdagi oqimning miqdori uchun tenglik o‘rinlidir, bu yerda – orgrafdagi uchdan uchga yo‘nalgan barcha yo‘llar to‘plamidan iborat. kesimning ta’rifidan ko‘rinib turibdiki, uchdan uchga olib boruvchi ixtiyoriy yo‘l shu va uchlarni ajratuvchi har qanday kesimning hech bo‘lmaganda bitta yoyini o‘zida saqlaydi. shuning uchun, agar ixtiyoriy kesimning barcha yoylarini tarmoqdan olib tashlasak, u holda orgrafda uchdan uchga boradigan birorta ham yo‘l …

Want to read more?

Download all 10 pages for free via Telegram.

Download full file

About "tarmoq tushunchasi"

mavzu: tarmoq tushunchasi. tarmoqdagi oqimlar. graf. uch. qirra. orgraf. yoy. tarmoq. to‘plam. blok-sxema. gipergraf. bog‘lamli tarmoq. sirtmoq. yoyning o‘tkazish qobiliyati. uchning chiqish va kirish yarim darajalari. manba. o‘pqon. tarmoqdagi oqim. yoy bo‘ylab oqim. tarmoqdagi oqim miqdori. maksimal oqim. to‘yingan, to‘yinmagan, to‘g‘ri va teskari yoylar. zanjir. tarmoqning “tor joyi”. kesim. manbani o‘pqondan ajratuvchi kesim. kesimning o‘tkazish qobiliyati. minimal kesim. 8.1. tarmoq tushunchasi. graflar nazariyasida hozirgacha ba’zi iboralar bo‘yicha umumiy kelishuv qaror topmaganligini qayd qilgan edik. bu fikr graflar nazariyasining tarmoq va tarmoqqa oid tushunchalari bilan ish ko‘rganda yaqqol namoyan bo‘ladi. ba’zan, “tarmoq” iborasi o‘rniga “to‘r” iborasini ham qo‘llaydilar. mas...

This file contains 10 pages in DOCX format (361.9 KB). To download "tarmoq tushunchasi", click the Telegram button on the left.

Tags: tarmoq tushunchasi DOCX 10 pages Free download Telegram