graflar nazariyasining boshlang‘ich ma’lumotlari

DOCX 7 pages 295.9 KB Free download

7 pages

FaylHub.uz

Download via Telegram

Size 295.9 KB

File type DOCX

Pages 7

Updated Dec 2025

Page preview (5 pages)

Scroll down 👇

1 / 7

mavzu: graflar nazariyasining boshlang‘ich ma’lumotlari graf. uch. qirra. yoy. yo‘nalish. orgraf. qo‘shni uchlar. yakkalangan uch. karrali qirralar. multigraf. psevdograf. nolgraf. to‘la, belgilangan va izomorf graflar. grafning geometrik ifodalanishi. uchlar, qirralar va yoylar insidentligi. 1.1. graflar nazariyasi haqida umumiy ma’lumotlar. 1736 yilda l. eyler tomonidan o‘sha davrda qiziqarli amaliy masalalardan biri hisoblangan kyonigsberg[footnoteref:1] ko‘priklari haqidagi masalaning qo‘yilishi va yechilishi graflar nazariyasining paydo bo‘lishiga asos bo‘ldi. [1: kyonigsberg (königsberg) – bu shahar 1255 yilda asoslangan bo‘lib, sharqiy prussiyadagi pregel daryosi qirg‘oqlarida joylashgan. 1946 yildan boshlab kaliningrad, hozir rossiya federatsiyasi tarkibida.] kyonigsberg shahridagi pregel daryosi ustida qurilgan yettita ko‘priklar joylashuvi 1- shakldagi qadimiy xaritada tasvirlangan va qurilishi tartibida 1, 2, 3, 4, 5, 6 va 7 raqamlar bilan belgilangan. pregel daryosi kyonigsberg shahrini o‘sha davrda to‘rtta , , va qismlarga bo‘lgan. shaharning ixtiyoriy qismida joylashgan uydan chiqib yettita ko‘priklardan faqat bir martadan o‘tib, yana o‘sha uyga qaytib kelish mumkinmi? kyonigsberg ko‘priklari haqidagi bu …

2 / 7

eref:4] tomonidan 1936 yilda graflar nazariyasiga bag‘ishlangan dastlabki darslikda[footnoteref:5] uchraydi. [4: kyonig (dénes könig, 1884-1944) – venger matematigi.] [5: bu darslik olmon tilida yozilgan.] graflar nazariyasi bo‘yicha tadqiqotlar natijalari inson faoliyatining turli sohalarida qo‘llaniladi. ulardan ba’zilari quyidagilardir: boshqotirmalarni hal qilish; qiziqarli o‘yinlar; yo‘llar, elektr zanjirlari, integral sxemalari va boshqarish sistemalarini loyihalashtirish; avtomatlar, blok-sxemalar va komp’yuter uchun programmalarni tadqiq qilish va hokazo. 1.2. grafning abstrakt ta’rifi va u bilan bog‘liq boshlang‘ich tushunchalar. avvalo, grafning abstrakt matematik tushuncha sifatidagi ta’rifini va boshqa ba’zi sodda tushunchalarni keltiramiz. qandaydir bo‘shmas to‘plam bo‘lsin. uning va elementlaridan tuzilgan ko‘rinishdagi barcha juftliklar (kortejlar) to‘plamini ( to‘plamning o‘z-o‘ziga dekart ko‘paytmasini) bilan belgilaymiz. graf[footnoteref:6] deb shunday juftlikka aytiladiki, bu yerda va – (, ) ko‘rinishdagi juftliklar korteji[footnoteref:7] bo‘lib, to‘plamning elementlaridan tuzilgandir. [6: yunoncha γράφω tirnayman, chizaman, yozaman ma’nosini beradi.] [7: bundan keyin “juftliklar korteji” iborasi o‘rniga, qisqacha kortej iborasini qo‘llaymiz.] bundan buyon grafni belgilashda yozuv o‘rniga yozuvdan foydalanamiz. grafning …

3 / 7

o‘sh bo‘lmasa, u holda bu kortej (, ) ko‘rinishdagi juftliklardan[footnoteref:8] tashkil topadi, bunda bo‘lishi hamda ixtiyoriy juftlik kortejda istalgancha marta qatnashishi mumkin. [8: bu yerda ham juftlikning (kortejning) odatdagi yozuvi o‘rniga yozuvdan foydalanamiz.] juftlikni tashkil etuvchi va uchlarning joylashish tartibidan bog‘liq holda, ya’ni yo‘nalishning borligi yoki yo‘qligiga qarab, uni turlicha atash mumkin. agar juftlik uchun uni tashkil etuvchilarning joylashish tartibi ahamiyatsiz, ya’ni bo‘lsa, juftlikka yo‘naltirilmagan (oriyentirlanmagan) qirra (yoki, qisqacha, qirra) deyiladi. agar bu tartib muhim, ya’ni bo‘lsa, u holda juftlikka yoy yoki yo‘naltirilgan (oriyentirlangan) qirra deyiladi. kortejning tarkibiga qarab, uni yo grafning qirralari korteji, yo yoylari korteji, yoki qirralari va yoylari korteji deb ataymiz.2- shakl grafning uchlari va qirralari (yoylari) uning elementlari deb ataladi. graf elementlarining soni ()ga tengdir, bu yerda grafning uchlari soni va bilan uning qirralari (yoylari) soni belgilangan. grafning qirrasi (yoyi), odatda, uni tashkil etuvchi uchlar yordamida , yoki , yoki ko‘rinishda belgilanadi. boshqa belgilashlar ham ishlatiladi: …

4 / 7

utashtiruvchi qirra yoki yoy bor bo‘lsa, u holda ular qo‘shni uchlar deb, aks holda esa, qo‘shni bo‘lmagan uchlar deb aytiladi. grafning ikkita uchi qo‘shni bo‘lsa, ular shu uchlarni tutashtiruvchi qirraga (yoyga) insident, o‘z navbatida, qirra yoki yoy bu uchlarga insident deyiladi. grafda ikkita qirra (yoy) umumiy chetga ega bo‘lsa, ular qo‘shni qirralar (yoylar) deyiladi. shuni ta’kidlash kerakki, qo‘shnilik tushunchasi grafning bir jinsli, insidentlik tushunchasi esa uning turli jinsli elementlari orasidagi munosabatni ifodalaydi. ba’zan graf undagi elementlar soniga qarab, ya’ni uchlar soni va qirralar (yoylar) soni ga qarab belgilanadi va bu holda grafni -graf deb ataydilar. agar grafda kortej faqat qirralardan iborat bo‘lsa, u holda yo‘naltirilmagan (oriyentirlanmagan) 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. qator hollarda oriyentirlanmagan qirralari ham, oriyentirlangan qirralari ham bo‘lgan graflar bilan ish ko‘rishga to‘g‘ri keladi. bunday graflar aralash graflar …

5 / 7

akkalangan uchlardan tashkil topgan graf (ya’ni, grafda qirralar va yoylar bo‘lmasa) nolgraf yoki bo‘sh graf deb ataladi. uchlari soni ga teng bo‘lgan bo‘sh grafni yoki kabi belgilash qabul qilingan. istalgan ikkita uchlari qo‘shni bo‘lgan sirtmoqsiz va karrali qirralarsiz oriyentirlanmagan graf to‘la graf deb ataladi. uchlari soni ga teng bo‘lgan to‘la graf bilan belgilanadi. ravshanki, grafning qirralar soni bo‘ladi. 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 bir-biriga qarama-qarshi bo‘lgan) yoylarga almashtirilsa, natijada to‘la orgraf hosil bo‘ladi. shuning uchun, to‘la orgrafdagi yoylar soni oriyentirlanmagan to‘la grafdagi qirralar sonidan ikki baravar ko‘pdir, ya’ni uchlari ta bo‘lgan to‘la orgrafdagi yoylar soni bo‘ladi. agar grafning uchlariga qandaydir belgilar, masalan, sonlari mos qo‘yilgan bo‘lsa, u belgilangan graf deb ataladi. agar va graflarning uchlari to‘plamlari, ya’ni va to‘plamlar orasida uchlarning qo‘shnilik munosabatini saqlaydigan o‘zaro bir …

Want to read more?

Download all 7 pages for free via Telegram.

Download full file

About "graflar nazariyasining boshlang‘ich ma’lumotlari"

mavzu: graflar nazariyasining boshlang‘ich ma’lumotlari graf. uch. qirra. yoy. yo‘nalish. orgraf. qo‘shni uchlar. yakkalangan uch. karrali qirralar. multigraf. psevdograf. nolgraf. to‘la, belgilangan va izomorf graflar. grafning geometrik ifodalanishi. uchlar, qirralar va yoylar insidentligi. 1.1. graflar nazariyasi haqida umumiy ma’lumotlar. 1736 yilda l. eyler tomonidan o‘sha davrda qiziqarli amaliy masalalardan biri hisoblangan kyonigsberg[footnoteref:1] ko‘priklari haqidagi masalaning qo‘yilishi va yechilishi graflar nazariyasining paydo bo‘lishiga asos bo‘ldi. [1: kyonigsberg (königsberg) – bu shahar 1255 yilda asoslangan bo‘lib, sharqiy prussiyadagi pregel daryosi qirg‘oqlarida joylashgan. 1946 yildan boshlab kaliningrad, hozir rossiya federatsiyasi tarkibida.] kyonigsberg shahridagi...

This file contains 7 pages in DOCX format (295.9 KB). To download "graflar nazariyasining boshlang‘ich ma’lumotlari", click the Telegram button on the left.

Tags: graflar nazariyasining boshlang… DOCX 7 pages Free download Telegram