grafning metrik xarakteristikalari

DOCX 6 pages 270.9 KB Free download

6 pages

FaylHub.uz

Download via Telegram

Size 270.9 KB

File type DOCX

Pages 6

Updated Dec 2025

Page preview (5 pages)

Scroll down 👇

1 / 6

mavzu: grafning metrik xarakteristikalari graf. uch. qirra. uchlar orasidagi masofa. zanjir. oddiy zanjir. metrika aksiomalari. uchburchak tengsizligi. uchning ekssentrisiteti. grafning diametri. diametral zanjir. grafning radiusi, markazi. markaziy uch. radial oddiy zanjir. qirraning, yoyning, zanjirning, yo‘lning uzunligi. additivlik. minimal uzunlikka ega yo‘l. deykstra algoritmi. 1. graflarda masofa tushunchasi. bog‘lamli graf berilgan bo‘lsin. bu grafda har qanday ikkita va uchlar bog‘langan bo‘lgani uchun chetlari va uchlardan iborat bo‘lgan hech bo‘lmasa bitta marshrut bor. va uchlarni bog‘lovchi eng qisqa marshrutning uzunligi va uchlar orasidagi masofa deb ataladi va u bilan belgilanadi. ravshanki, eng qisqa marshrut oddiy zanjirdir. tabiiy ravishda deb qabul qilamiz. shuni ta’kidlash kerakki, graflarda masofa tushunchasini boshqa usul bilan ham aniqlash mumkin. yuqoridagi usul bilan aniqlangan masofa metrika aksiomalari deb ataluvchi quyidagi shartlarni qanoatlantiradi: 1) ; 2) bo‘lgandagina bo‘ladi; 3) ; 4) . oxirgi aksioma uchburchak tengsizligi deb ataladi. bog‘lamli graf berilgan bo‘lsin. grafning ixtiyoriy uchi uchun aniqlangan miqdor shu uchning …

2 / 6

egadir. agar grafning markazidan boshqa biror uchigacha bo‘lgan oddiy zanjir eng uzun masofaga ega bo‘lsa, u holda bu zanjir radial oddiy zanjir 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 bo‘lishi ham mumkin. grafning markaziy uchlarini topish bilan bog‘liq masalalar aholiga xizmat ko‘rsatadigan qandaydir ob’yektning (kasalxona, maktab va shu kabilarning) joylashish o‘rnini aniqlash bilan bog‘liq muammolarni hal qilishda qo‘llanilishi mumkin. ta’kidlash kerakki, muayyan vaziyatlarda, ko‘pincha, boshqa holatlarni, jumladan, ob’yektgacha borish vaqti, punktlar orasidagi masofa va shu kabilarni hisobga olishga to‘g‘ri keladi. bunday vaziyatlarda joylashtirishning minimaks masalalari deb ataluvchi masalalar vujudga keladi. 1- misol. 1- shaklda tasvirlangan grafni qaraymiz. bu ghafda , , ; va zanjirlar diametral zanjirlardir, va zanjirlar esa diametral zanjirdirlar bo‘la olmaydi. berilgan grafda 4, 5 va 6 belgili uchlar markazlar bo ‘lib, hamda va radial oddiy zanjirlardir. ■1 3 …

3 / 6

ma’noga ega deb hisoblanadi. amaliyotda uchraydigan ko‘plab masalalarda marshrut uzunligi maksimallashtirilishi yoki minimallashtirilishi talab etiladi. shunday masalalardan biriga, aniqrog‘i, kommivoyajer masalasiga gamilton graflari bilan shug‘ullanganda duch kelgan edik (ushbu bobning 5- paragrafiga qarang). oriyentirlangan graf berilgan bo‘lsin, bu yerda . grafning biror uchidan boshqa uchiga boruvchi yo‘llar orasida uzunligi eng kichik bo‘lganini topish masalasi bilan shug‘ullanamiz. bu masalani minimal uzunlikka ega yo‘l haqidagi masala deb ataymiz. quyida bu masalaning umumlashmasi hisoblangan masalani qarab, uni ham o‘sha nom bilan ataymiz. grafdagi yoyning uzunligini bilan belgilab, , matritsa berilgan deb hisoblaymiz. yuqorida ta’kidlaganlarimizga ko‘ra, matritsaning elementlari orasida manfiylari yoki nolga tenglari ham bo‘lishlari mumkin. agar grafda biror uchdan chiqib uchga kirruvchi yoy mavjud bo‘lmasa, u holda bu yoyning uzunligini cheksiz katta deb qabul qilamiz (). bundan tashqari, grafda umumiy uzunligi manfiy bo‘lgan sikl mavjud emas deb hisoblaymiz, chunki aks holda uzunligi eng kichik bo‘lgan yo‘l mavjud emas[footnoteref:1]. [1: agar grafda umumiy uzunligi …

4 / 6

l qilingan to‘plamga kiritamiz: . deb olamiz. umumiy qadam. boshlang‘ich uchi to‘plamga, oxirgi uchi esa to‘plamga tegishli bo‘lgan barcha yoylar to‘plami bo‘lsin. har bir yoy uchun miqdorni aniqlaymiz, bu yerda deb uchga mos qo‘yilgan qiymat (grafning 1 belgili uchidan chiqib belgili uchigacha eng qisqa yo‘l uzunligi) belgilangan. qiymatni aniqlaymiz. to‘plamning oxirgi tenglikda minimum qiymat beruvchi barcha elementlarini, ya’ni yoylarni ajratamiz. ajratilgan yoylarning har biridagi belgili uchga qiymatni mos qo‘yamiz. qiymat mos qo‘yilgan barcha uchlarni to‘plamdan chiqarib to‘plamga kiritamiz. ikkala uchi ham to‘plamga tegishli bo‘lgan barcha yoylar uchun tengsizlikning bajarilishini tekshiramiz. tekshirilayotgan tengsizlik o‘rinli bo‘lmagan (ja’ni bo‘lgan) barcha belgili uchlarning har biriga mos qo‘yilgan eski qiymat o‘rniga yangi qiymatni mos qo‘yamiz va yoyni ajratamiz. bunda eski qiymat aniqlangan paytda ajratilgan yoyni ajratilmagan deb hisoblaymiz. uchlarga qiymat mos qo‘yish jarayonini oxirgi ( belgili) uchga qiymat mos qo‘yilguncha davom ettiramiz. grafning 1 belgili uchidan (manbadan) chiqib uning ixtiyoriy uchigacha (oxirgi uchigacha) eng qisqa …

5 / 6

ing uchun, bo‘ladi. umumiy qadam. 1- iteratsiya. va bo‘lgani uchun boshlang‘ich uchi to‘plamga tegishli, oxirgi uchi esa to‘plam elementi bo‘lgan barcha yoylar to‘plami ga ega bo‘lamiz. to‘plamga tegishli bo‘lgan har bir yoy uchun ning qiymatlarini topamiz: yoy uchun ; yoy uchun ; yoy uchun . bu , va miqdorlar orasida eng kichigi bo‘lgani uchun yoyni ajratamiz (3- shaklda bu yoy qalin chiziq bilan belgilangan) va belgili uchga qiymatni mos qo‘yamiz. algoritmga ko‘ra uchni to‘plamdan chiqarib, to‘plamga kiritamiz. natijada[footnoteref:3] va to‘plamlarga ega bo‘lamiz. [3: yozuvning ixchamligi nuqtai nazardan bu yerda va bundan keyin hosil bo‘lgan to‘plamlar uchun va belgilar qoldiriladi.] ikkala uchi ham to‘plamga tegishli bo‘lgan bitta yoy bo‘lgani uchun faqat bitta tengsizlikning bajarilishini tekshirish kifoya. bu tengsizlik ko‘rinishdagi to‘g‘ri munosabatdan iborat bo‘lgani uchun 2- iteratsiyaga o‘tamiz. 2- iteratsiya. bo‘lgani sababli , , va qiymatlarni va ekanligini aniqlaymiz. bu yerda eng kichik qiymat yoyga mos keladi. shuning uchun, yoyni ajratamiz va …

Want to read more?

Download all 6 pages for free via Telegram.

Download full file

About "grafning metrik xarakteristikalari"

mavzu: grafning metrik xarakteristikalari graf. uch. qirra. uchlar orasidagi masofa. zanjir. oddiy zanjir. metrika aksiomalari. uchburchak tengsizligi. uchning ekssentrisiteti. grafning diametri. diametral zanjir. grafning radiusi, markazi. markaziy uch. radial oddiy zanjir. qirraning, yoyning, zanjirning, yo‘lning uzunligi. additivlik. minimal uzunlikka ega yo‘l. deykstra algoritmi. 1. graflarda masofa tushunchasi. bog‘lamli graf berilgan bo‘lsin. bu grafda har qanday ikkita va uchlar bog‘langan bo‘lgani uchun chetlari va uchlardan iborat bo‘lgan hech bo‘lmasa bitta marshrut bor. va uchlarni bog‘lovchi eng qisqa marshrutning uzunligi va uchlar orasidagi masofa deb ataladi va u bilan belgilanadi. ravshanki, eng qisqa marshrut oddiy zanjirdir. tabiiy ravishda deb qabul qilamiz. shuni ta’kid...

This file contains 6 pages in DOCX format (270.9 KB). To download "grafning metrik xarakteristikalari", click the Telegram button on the left.

Tags: grafning metrik xarakteristikal… DOCX 6 pages Free download Telegram