graflar nazariyasi haqida umumiy ma'lumotlar

DOCX 7 sahifa 325,0 KB Bepul yuklash

7 sahifa

FaylHub.uz

Telegram orqali yuklab olish

Hajm 325,0 KB

Fayl turi DOCX

Sahifalar 7

Yangilangan Dek 2025

Sahifa ko'rinishi (5 sahifa)

Pastga aylantiring 👇

1 / 7

22-ma’ruza. graflar nazariyasi haqida umumiy ma’lumotlar reja: 1. graflar nazariyasi haqida umumiy ma’lumotlar. 2. grafning abstrakt ta’rifi va u bilan bog‘liq boshlang‘ich tushunchalar. 1. graflar nazariyasi haqida umumiy ma’lumotlar. 1736 yilda l. eyler tomonidan o‘sha davrda qiziqarli amaliy masalalardan biri hisoblangan kyonigsberg ko‘priklari haqidagi masalaning qo‘yilishi va yechilishi graflar nazariyasining paydo bo‘lishiga asos bo‘ldi. 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 masalani hal qilish jarayonida graflarda maxsus marshrut (hozirgi vaqtda graflar nazariyasida bu marshrut eyler sikli nomi bilan yuritiladi) mavjudligi shartlari ham topildi. bu natijalar e’lon qilingan tarixiy ilmiy ishning birinchi sahifasi 2- shaklda keltirilgan. …

2 / 7

ushuncha 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 deb shunday juftlikka aytiladiki, bu yerda va – (, ) ko‘rinishdagi juftliklar korteji bo‘lib, to‘plamning elementlaridan tuzilgandir.denes kyonig bundan buyon grafni belgilashda yozuv o‘rniga yozuvdan foydalanamiz. grafning tashkil etuvchilarini ko‘rsatish muhim bo‘lmasa, u holda uni lotin alifbosining bitta harfi, masalan, bilan belgilaymiz. graf berilgan bo‘lsin. to‘plamning elementlariga grafning uchlari, to‘plamning o‘ziga esa, graf uchlari to‘plami deyiladi. graflar nazariyasida “uch” iborasi o‘rniga, ba’zan, tugun yoki nuqta iborasi ham qo‘llaniladi. umuman olganda, hanuzgacha graflar nazariyasining ba’zi iboralari bo‘yicha umumiy kelishuv qaror topmagan. shuning uchun, bundan keyingi ta’riflarda, imkoniyat boricha, muqobil (alternativ) iboralarni ham keltirishga harakat qilamiz. grafning ta’rifiga ko‘ra, bo‘sh kortej bo‘lishi ham mumkin. agar bo‘sh bo‘lmasa, u holda bu kortej (, ) ko‘rinishdagi juftliklardan tashkil topadi, bunda bo‘lishi hamda ixtiyoriy juftlik …

3 / 7

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: masalan, yoy uchun yoki , qirra uchun , yoy yoki qirra uchun (ya’ni uchlari ko‘rsatilmasdan bitta harf vositasida) ko‘rinishda. graf yoyi uchun uning chetki uchlarini ko‘rsatish tartibi muhim ekanligini ta’kidlaymiz, ya’ni va yozuvlar bir-biridan farq qiluvchi yoylarni ifodalaydi. agar yoy ko‘rinishda ifodalangan bo‘lsa, u holda uning boshlang‘ich uchi, esa oxirgi uchi deb ataladi. bundan tashqari, yoy ko‘rinishda yozilsa, u haqida uchdan chiquvchi (boshlanuvchi) va uchga kiruvchi (uchda tugovchi) yoy deb aytish ham odat tusiga kirgan. qirra uchun uning yozuvidagi harflar joylashish tartibi muhim rol o‘ynamaydi va va elementlar qirraning uchlari yoki chetlari deb ataladi. agar grafda yo qirra, yo yoy, yoki yoy topillsa, u holda va uchlar tutashtirilgan deyiladi. agar grafning ikkita uchini tutashtiruvchi qirra yoki yoy bor bo‘lsa, u holda …

4 / 7

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 deb ataladi. agar grafning (orgrafning) korteji tarkibida to‘plamdan olingan takrorlanuvchi elementlar bo‘lsa, u holda ular karrali yoki parallel qirralar (yoylar) deb ataladi. karrali qirralari yoki yoylari bo‘lgan graf multigraf deyiladi. ikkala chetki (boshlang‘ich va oxirgi) uchlari ustma-ust tushgan qirra (yoy), ya’ni grafning elementi sirtmoq deb ataladi. sirtmoq, odatda, yo‘naltirilmagan deb hisoblanadi. qirralari (yoylari) orasida sirtmoqlari bo‘lgan graf psevdograf deyiladi. umumiy holda uchlar to‘plami va (yoki) qirralar (yoylar, qirra va yoylar) korteji cheksiz ko‘p elementli bo‘lishi mumkin. bundan keyin to‘plam va kortej faqat chekli bo‘lgan graflarni qaraymiz. bunday graflar chekli graflar deb ataladi. hech qanaqa qirra (yoy) bilan bog‘lanmagan uch yakkalangan (ajralgan, xolis, yalong‘och) uch deb ataladi. faqat yakkalangan uchlardan tashkil topgan graf (ya’ni, grafda qirralar va yoylar bo‘lmasa) nolgraf yoki bo‘sh graf deb ataladi. uchlari soni ga …

5 / 7

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 qiymatli moslik o‘rnatish mumkin bo‘lsa, u holda va graflar izomorf graflar deb ataladi. bu ta’rifni quyidagicha ham ifodalash mumkin: agar va ularga mos bo‘lgan (, ) uchun (, ) bo‘lsa, u holda va graflar izomorfdir. agar izomorf graflardan biri oriyentirlangan bo‘lsa, u holda ikkinchisi ham, albatta, oriyentirlangan bo‘lishi va ulardagi mos yoylarning yo‘nalishlari ham bir-birlariga mos bo‘lishlari shart. graf uchiga insident qirralar soni shu uchning lokal darajasi, yoki, qisqacha, darajasi, yoki valentligi deb ataladi. grafdagi uchning darajasini bilan belgilaymiz. sirtmoqqa insident bo‘lgan uchning darajasini aniqlashda shuni e’tiborga olish kerakki, qaralayotgan masalaga bog‘liq holda sirtmoqni bitta qirra deb ham, ikkita qirra deb ham hisoblash mumkin. ravshanki, ajralgan uchning darajasi nolga teng. darajasi birga teng uch chetki (yoki osilgan) uch deb ataladi. chetki (osilgan) uchga insident qirra ham chetki …

Ko'proq o'qimoqchimisiz?

Barcha 7 sahifani Telegram orqali bepul yuklab oling.

To'liq faylni yuklab olish

"graflar nazariyasi haqida umumiy ma'lumotlar" haqida

22-ma’ruza. graflar nazariyasi haqida umumiy ma’lumotlar reja: 1. graflar nazariyasi haqida umumiy ma’lumotlar. 2. grafning abstrakt ta’rifi va u bilan bog‘liq boshlang‘ich tushunchalar. 1. graflar nazariyasi haqida umumiy ma’lumotlar. 1736 yilda l. eyler tomonidan o‘sha davrda qiziqarli amaliy masalalardan biri hisoblangan kyonigsberg ko‘priklari haqidagi masalaning qo‘yilishi va yechilishi graflar nazariyasining paydo bo‘lishiga asos bo‘ldi. 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‘prikl...

Bu fayl DOCX formatida 7 sahifadan iborat (325,0 KB). "graflar nazariyasi haqida umumiy ma'lumotlar"ni yuklab olish uchun chap tomondagi Telegram tugmasini bosing.

Teglar: graflar nazariyasi haqida umumi… DOCX 7 sahifa Bepul yuklash Telegram