O’zbekiston respublikasi axborot texnologiyalari va kommunikatsiyalarini rivojlantirish

Yo'naltirilgangrafik
Yo'naltirilgangrafika - bugrafikningtepaliklarnibog'laydiganqirralariyo'nalishgaegabo'lgangrafikdir. 2 -rasmda V = {V1, V2, V3} tepaliklarto'plamibilanyo'naltirilgangrafiktasvirlangan. Yuqoridagigrafikdagiqirralarningto'plami V = {(V1, V2), (V2, V3), (V1, V3)} shaklidayozilishimumkin. Yo'naltirilmagangrafikdagiqirralartartiblijuftliklardir. Rasmiyravishda, yo'naltirilgangrafikdagi e chekka e = (x, y) tartiblijuftlikbilanifodalanishimumkin, buerda x - chekkaningboshi, manbaiyokiboshlang'ichnuqtasi deb nomlangantepalik, y tepasiesa nuqta deyiladi , vertex yoki terminal nuqtasinitugatish. Masalan, shaharlarmajmuasinibirtomonlamayo'llaryordamidabog'laydiganyo'ltarmog'iyo'naltirilmagangrafikyordamidaifodalanishimumkin. Shaharlargrafikdagitepaliklarbilanifodalanishimumkinvayo'naltirilganqirralarshaharda transport harakatiyo'nalishinihisobgaolganholdabog'laydiganyo'llarniifodalaydi.

Yo'naltirilgangrafikvayo'naltirilmagangrafiko'rtasidagifarqnima?
Yo'naltirilgangrafikdachekka - butartibgasolinganjuftlik, buerdatartiblanganjuftlikikkitepaliknibog'laydiganqirraningyo'nalishiniifodalaydi. Boshqatomondan, yo'naltirilmagangrafikdachekka - butartibgasolinmaganjuftlik, chunkichekkabilanbog'liqyo'nalishyo'q. Yo'naltirilmagangrafikalarob'ektlarorasidaginosimmetrikmunosabatlarniifodalashuchunishlatilishimumkin. Yo'naltirilmagangrafikdagi har birtugunningdarajasivadarajasiteng, lekinbuyo'naltirilgangrafikuchunto'g'riemas. Yo'naltirilmagangrafikniko'rsatishuchunmatritsadanfoydalanganda, matritsa har doimnosimmetrikgrafikgaaylanadi, lekinbuyo'naltirilgangrafikalaruchunto'g'riemas. Yo'naltirilmagangrafikni har birqirraniqarama -qarshitomongayo'naltirilganikkitaqirragaalmashtirishorqaliyo'naltirilgangrafikkaaylantirishmumkin. Biroq, yo'naltirilgangrafikniyo'naltirilmagangrafikagaaylantirishmumkinemas.
Yo'naltirilgangrafiklar. Yo'naltirilgangrafik. UchtugunlibarchadigraflarningtasvirivaxossalariAlgoritmlarnito'g'ridan-to'g'rio'rganishniboshlashdanoldin, sizgrafiklarningo'zlarihaqidaasosiybilimlargaegabo'lishingiz, ularningkompyuterdaqandayifodalanishinitushunishingizkerak. Grafiknazariyasiningbarchajihatlaribuerdabatafsiltavsiflanmaydi (bushartemas), faqatbilmaslikdasturlashningushbusohasinio'zlashtirishnisezilarlidarajadamurakkablashtiradigannarsalar. Bir nechtamisollarsizgagrafikhaqidaqisqachatasavvurberadi. Shundayqilib, odatiygrafik metro xaritasiyokiboshqamarshrutdir. Xususan, dasturchikompyutertarmog'iniyaxshibiladi, bu ham grafikdir. Bu erdaumumiychiziqlarbilanbog'langannuqtalarningmavjudligi. Shunday
qilib, kompyutertarmog'idanuqtalaralohidaserverlar, chiziqlaresa har xilturdagielektrsignallaridir. Metrodabirinchisi - stansiyalar, ikkinchisi - ularorasigayotqizilgantunnellar. Grafiknazariyasidanuqtalardeyiladicho'qqilari (tugunlar) vachiziqlar - qovurg'alar (yoylar). Shundayqilib, grafikQirralarbilanbog'langancho'qqilarto'plami. Matematikanarsalarningmazmunibilanemas, balkiularningtuzilishibilanishlaydi, unibirbutunsifatidaberilgannarsalardanmavhumlashtiradi. Aynanshutexnikadanfoydalanib, biz har qandayob'ekthaqidagrafiksifatidaxulosaqilishimizmumkin. Grafiklarnazariyasimatematikaningbirqismibo'lganligisababli, uninguchunmutlaqohechqandayma'noyo'q, asosan, ob'ektnima; muhimi, bugrafikmi, ya'nigrafiklaruchunzarurbo'lganxususiyatlargaegami. Shuninguchun, misollarkeltirishdanoldin, biz ko'ribchiqilayotganob'ektdafaqato'xshashlikniko'rsatishgaimkonberadigannarsaniajratibko'rsatamiz, biz umumiyniqidiramiz. Keling, kompyutertarmog'igaqaytaylik. U ma'lumbirtopologiyagaegavaunishartliravishdama'lummiqdordagikompyuterlarvaularnibog'laydiganyo'llarshaklidatasvirlashmumkin. Quyidagirasmdamisolsifatidato'liqtarmoqlitopologiyako'rsatilgan. Bu asosangrafikdir. Beshtakompyutercho'qqilardirvaularorasidagiulanishlar (signalizatsiyayo'llari) qirralardir. Kompyuterlarnicho'qqilarbilanalmashtirib, biz matematikob'ektniolamiz - 10 qirrasiva 5 uchibo'lgangrafik. Cho'qqilarni har qandayusuldaraqamlashmumkin, lekinburasmdabajarilganishartemas. Shunita'kidlashkerakki, in bumisolbittapastadirishlatilmaydi, ya'nicho'qqidanchiqibketadiganvadarholungakiradiganchekka, lekinmuammolardahalqalarpaydobo'lishimumkin.
G  (V,U) grafningta’rifigako‘ra, U bo‘shkortejbo‘lishi ham mumkin. Agar U bo‘shbo‘lmasa, u holdabukortej (a,b) ( aV , bV ) ko‘rinishdagi juftliklardan7 tashkiltopadi, bunda a  b bo‘lishihamdaixtiyoriy (a,b) juftlik U kortejdaistalganchamartaqatnashishimumkin. (a,b)U juftliknitashkiletuvchi a va b uchlarningjoylashishtartibidanbog‘liqholda, ya’niyo‘nalishningborligiyokiyo‘qligigaqarab, uniturlichaatashmumkin. Agar (a,b) juftlikuchununitashkiletuvchilarningjoylashishtartibiahamiyatsiz, ya’ni (a,b)  (b,a) bo‘lsa, (a,b) juftlikkayo‘naltirilmagan (oriyentirlanmagan) qirra (yoki, qisqacha, qirra) deyiladi. Agar butartibmuhim, ya’ni (a,b)  (b,a) bo‘lsa, u holda (a,b) juftlikkayoyyokiyo‘naltirilgan (oriyentirlangan) qirradeyiladi.
U kortejningtarkibigaqarab, uniyografningqirralarikorteji, yoyoylarikorteji, yokiqirralarivayoylarikorteji deb ataymiz. Grafninguchlarivaqirralari (yoylari) uningelementlari deb ataladi. G  (V,U) grafelementlariningsoni ( |V |  |U | )gatengdir, buyerda G grafninguchlarisoni |V | 0 va |U | bilanuningqirralari (yoylari) sonibelgilangan. Grafningqirrasi (yoyi), odatda, unitashkiletuvchiuchlaryordamida (a,b) , yoki ab , yoki (a;b) ko‘rinishdabelgilanadi. Boshqabelgilashlar ham ishlatiladi: masalan, yoyuchun (a,b) yoki (a,b) , qirrauchun (a,b) , yoyyokiqirrauchun u (ya’niuchlariko‘rsatilmasdanbittaharfvositasida) ko‘rinishda. Graf yoyiuchununingchetkiuchlariniko‘rsatishtartibimuhimekanliginita’kidlaymiz, ya’ni (a,b) va (b,a) yozuvlarbir-biridanfarqqiluvchiyoylarniifodalaydi. Agar yoy (a,b) ko‘rinishdaifodalanganbo‘lsa, u holda a uningboshlang‘ichuchi, b esaoxirgiuchi deb ataladi. Bundantashqari, yoy (a,b) ko‘rinishdayozilsa, u haqida a uchdanchiquvchi (boshlanuvchi) va b uchgakiruvchi (uchdatugovchi) yoy deb aytish ham odattusigakirgan. Qirrauchununing (a,b) yozuvidagiharflarjoylashishtartibimuhimrolo‘ynamaydiva a va b elementlarqirraninguchlariyokichetlari deb ataladi. Agar grafdayo (a,b) qirra, yo (a,b) yoy, yoki (b,a) yoytopillsa, u holda a va b uchlartutashtirilgandeyiladi. Agar grafningikkitauchinitutashtiruvchiqirrayokiyoyborbo‘lsa, u holdaularqo‘shniuchlar deb, aksholdaesa, qo‘shnibo‘lmaganuchlar deb aytiladi. Grafningikkitauchiqo‘shnibo‘lsa, ularshuuchlarnitutashtiruvchiqirraga (yoyga) insident, o‘znavbatida, qirrayokiyoybuuchlargainsidentdeyiladi. Grafdaikkitaqirra (yoy) umumiychetgaegabo‘lsa, ularqo‘shniqirralar (yoylar) deyiladi. Shunita’kidlashkerakki, qo‘shniliktushunchasigrafningbirjinsli, insidentliktushunchasiesauningturlijinslielementlariorasidagimunosabatniifodalaydi. Ba’zangrafundagielementlarsonigaqarab, ya’niuchlarsoni m vaqirralar (yoylar) soni n gaqarabbelgilanadivabuholdagrafni (m,n)-graf deb ataydilar. Agar G  (V,U) grafda U kortejfaqatqirralardaniboratbo‘lsa, u holdayo‘naltirilmagan (oriyentirlanmagan) vafaqatyo‘naltirilgan (oriyentirlangan) qirralardan (ya’ni, yoylardan) tashkiltopganbo‘lsa, u holda u yo‘naltirilgan (oriyentirlangan) graf deb ataladi. Oriyentirlangangraf, qisqacha, orgraf deb ham ataladi. Qatorhollardaoriyentirlanmaganqirralari ham, oriyentirlanganqirralari ham bo‘lgangraflarbilanishko‘rishgato‘g‘rikeladi. Bundaygraflararalashgraflar deb ataladi. Agar G  (V,U) grafning (orgrafning) U kortejitarkibida V Vto‘plamdanolingantakrorlanuvchielementlarbo‘lsa, u holdaularkarraliyoki parallel qirralar (yoylar) deb ataladi. Karraliqirralariyokiyoylaribo‘lgangrafmultigrafdeyiladi. Ikkalachetki (boshlang‘ichvaoxirgi) uchlariustma-usttushganqirra (yoy), ya’nigrafning (a,a)U elementisirtmoq deb ataladi. Sirtmoq, odatda, yo‘naltirilmagan deb hisoblanadi. Qirralari (yoylari) orasidasirtmoqlaribo‘lgangrafpsevdografdeyiladi. Umumiyholdauchlarto‘plami V va (yoki) qirralar (yoylar, qirravayoylar) korteji U cheksizko‘pelementlibo‘lishimumkin. Bundankeyin V to‘plamva U kortejfaqatcheklibo‘lgan G  (V,U) graflarniqaraymiz. Bundaygraflarchekligraflar deb ataladi. Hechqanaqaqirra (yoy) bilanbog‘lanmaganuchyakkalangan (ajralgan, xolis, yalong‘och) uch deb ataladi. Faqatyakkalanganuchlardantashkiltopgangraf (ya’ni, grafdaqirralarvayoylarbo‘lmasa) nolgrafyokibo‘shgraf deb ataladi. Uchlarisoni m gatengbo‘lganbo‘shgrafni Om yoki Nm kabibelgilashqabulqilingan. Istalganikkitauchlariqo‘shnibo‘lgansirtmoqsizvakarraliqirralarsizoriyentirlanmagangrafto‘lagraf deb ataladi. Uchlarisoni m gatengbo‘lganto‘lagraf Km bilanbelgilanadi. Ravshanki, Km grafningqirralarsoni 2 ( 1) 2 m m Cm bo‘ladi. Agar orgrafningistalganikkitauchini har biryo‘nalishdatutashtiruvchifaqatbittadanyoymavjudbo‘lsa, u holdaungato‘laorgraf deb ataladi. Ravshanki, to‘lagrafdagiqirralarning har biriniikkita (yo‘nalishlaribir-birigaqarama-qarshibo‘lgan) yoylargaalmashtirilsa, natijadato‘laorgrafhosilbo‘ladi. Shuninguchun, to‘laorgrafdagiyoylarsonioriyentirlanmaganto‘lagrafdagiqirralarsonidanikkibaravarko‘pdir, ya’niuchlari m ta bo‘lganto‘laorgrafdagiyoylarsoni 2 ( 1) 2 Cm m mbo‘ladi. Agar grafninguchlarigaqandaydirbelgilar, masalan, 1,2,...,m sonlarimosqo‘yilganbo‘lsa, u belgilangangraf deb ataladi. Agar G  (V,U) va G'  (V' ,U') graflarninguchlarito‘plamlari, ya’ni V va V ' to‘plamlarorasidauchlarningqo‘shnilikmunosabatinisaqlaydigano‘zarobirqiymatlimosliko‘rnatishmumkinbo‘lsa, u holda G va G' graflarizomorfgraflar deb ataladi. Bu ta’rifniquyidagicha ham ifodalashmumkin: agar x,yV vaulargamosbo‘lgan x' , y'V' ( x  y , x' y' ) uchunxy x' y' ( xyU , x' y'U' ) bo‘lsa, u holda G va G' graflarizomorfdir. Agar izomorfgraflardanbirioriyentirlanganbo‘lsa, u holdaikkinchisi ham, albatta, oriyentirlanganbo‘lishivaulardagimosyoylarningyo‘nalishlari ham bir-birlarigamosbo‘lishlarishart. Graf uchigainsidentqirralarsonishuuchninglokaldarajasi, yoki, qisqacha, darajasi, yokivalentligi deb ataladi. Grafdagi a uchningdarajasini(a) bilanbelgilaymiz. Sirtmoqqainsidentbo‘lganuchningdarajasinianiqlashdashunie’tiborgaolishkerakki, qaralayotganmasalagabog‘liqholdasirtmoqnibittaqirra deb ham, ikkitaqirra deb ham hisoblashmumkin. Ravshanki, ajralganuchningdarajasinolgateng. Darajasibirgatenguchchetki (yokiosilgan) uch deb ataladi. Chetki (osilgan) uchgainsidentqirra ham chetki (yokiosilgan) qirra deb ataladi. Agar grafningbarchauchlaribirxil r darajagaegabo‘lsa, u holdabundaygraf r darajaliregulyargraf deb ataladi. Uchdarajaliregulyargrafkubik (yokiuchvalentli) graf deb ataladi. Om grafnoldarajaliregulyargrafekanligini, Km esa( m1 ) darajaliregulyargrafekanliginita’kidlaymiz. Ko‘rinibturibdiki, oriyentirlanmagangrafdabarchauchlardarajalariningyig‘indisiqirralarsoniningikkibaravarigatengjuft son bo‘ladi, chunkiqirralarnisanaganda har birqirrahisobdaikkimartaqatnashadi. Shundayqilib, XVIII asrdayoq L. Eylertomonidanisbotlanganquyidagitasdiqo‘rinlidir


Xulosa

Agar sizma'lumotlarfaninio'rganishnixohlasangiz, IIIT-B &upGradning Data Science bo'yicha Executive PG dasturiniko'ribchiqing, u ishlaydiganmutaxassislaruchunyaratilganva 10 dan ortiqamaliytadqiqotlarvaloyihalarni, amaliyamaliyseminarlarni, sohamutaxassislaribilanmaslahatlarnitaklifqiladi, 1 -on-on-1 sohamurabbiylaribilan, 400+ soato'rganishvaengyaxshifirmalarbilanishlashbo'yichayordam.