eng katta daraxt haqida, eng qisqa vaeng uzun yo’l haqida, tarmoqli rejalashtirish, kommunikatsiyalar turlari oqimi

DOCX 382,5 КБ Бесплатная загрузка

Предварительный просмотр (5 стр.)

Прокрутите вниз 👇

1693470927.docx eng katta daraxt haqida, eng qisqa vaeng uzun yo’l haqida, tarmoqli rejalashtirish, kommunikatsiyalar turlari oqimi eng katta daraxt haqida, eng qisqa vaeng uzun yo’l haqida, tarmoqli rejalashtirish, kommunikatsiyalar turlari oqimi reja: 1. kirish 2. daraxt va unga ekvivalent tushunchalar 3. eng qisqa va eng uzun yo‘l 4. daraxtlarni prufer usulida kodlash 5. xulosa 6. foydalanilgan adabiyotlar daraxt va unga ekvivalent tushunchalar. siklga ega bo'lmagan oriyentirlanmagan bog'lamli graf daraxt deb ataladi. ta'rifga ko'ra, daraxt sirtmoqlar va karrali qirralarga ega emas. siklga ega bo'lmagan oriyentirlanmagan graf о'rmon (asiklik graf) deb ataladi. 1-misol.1-shaklda bog'lamli komponentali soni beshga teng bo'lgan graf tasvirlangan bo'lib, u o'rmondir. bu grafdagi bog'lamli komponentalarning har bin daraxtdir. 2-misol 2-shaklda to'rtta uchga ega bir-biriga izomorf bo'lmagan barcha (ular bor-yog'i ikkita) daraxtlarning geometrik ifodalanishi tasvirlangan.beshta uchga ega birbiriga izomorf bo'lmagan barcha daraxtlar uchta, oltita uchga ega bunday barcha daraxtlar esa oltita ekanligini ko'rsatish qiyin emas. daraxt tushunchasiga boshqacha ham ta'rif …

$lamli komponentalardan iborat bo'lib, bu komponentalarning har biri daraxtdir. yana shuni ham e'tiborga olish kerakki, gl va g2 daraxtlarning har biridagi uchlar soni к dan oshmaydi. matematik induksiya usuliga ko'ra, bu daraxtlarning har birida qirralar soni uning uchlari sonidan bitta kam bo'lishini ta'kidlaymiz, ya'ni gxgraf (m, «)-graf bo'lsa, quyidagi tengliklar o'rinlidir: n=nx+n2+\, k+l=ml+m2 va. n=m — \ (/=1,2). bu tengliklardan n=nl+n2+l=m]— l+m2—1+1= (mx+m2)—l= (k+l)—l endi daraxtlar haqidagi asosiy teoremaning 2) tasdig'idan uning 3) tasdig'i kelib chiqishini isbotlaymiz. g graf asiklik, ya'ni u siklga ega bo'lmagan graf van=m— 1 bo'lsin. g grafning bog'lamli bo'lishini isbotlash kerak. agar g graf bog'lamli bo'lmasa, u holda uni har bir bog'lamli komponentasi siklsiz graf g. (ya'ni daraxt) bo'lgan qandaydir k ta (k>l) graflar dizyunktiv birlashmasi sifatida ^=u^ tenglik bilan ifodalash mumkin. har bir i=l,kuchun g.tgraf daraxt bo'lgani uchun, yuqorida isbotlangan tasdiqqa ko'ra, agar unda mj ta uch va «.ta qirra bo'lsa, u holda g. asiklikdir …$

ga qarab, muayyan bir ma’noga ega bo‘lishi mumkin. masalan, ikki shahar orasidagi masofa, qandaydir operatsiyani bajarish uchun zarar mablag‘ (xarajatlar) yoki vaqt va boshqalar. shu nuqtayi nazardan, umuman olganda, bu yerda manfiy uzunlikka ega yoki uzunligi nolga teng qirra (yoy) ham 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 g=( v, u) oriyentirlangan graf berilgan bo‘lsin, bu yerda v={l,2,...,m}. g grafning biron se vuchidan boshqa te vuchiga 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 (i,j) yoyning uzunligini bilan belgilab, c= , i, j=l ,m, matritsa berilgan deb hisoblaymiz. yuqorida ta’kidlaganlarimizga ko‘ra, с matritsaning c.. elementlari orasida manfiylari yoki nolga tenglari ham bo‘lishi …

lning uzunligi uning qirralari soni bilan o'lchanishi mumkin yoki ( vaznli grafiklarda ) uning qirralari og'irliklarining yig'indisi bilan o'lchanishi mumkin . eng qisqa yo'l muammosidan farqli o'laroq , polinom vaqtida manfiy vaznli tsikllarsiz grafiklarda echilishi mumkin bo'lgan muammodan farqli o'laroq , eng uzun yo'l muammosi np-qiyin va muammoning qaror versiyasi bo'lib, u kamida berilgan yo'l bor-yo'qligini so'raydi. uzunligi, np-to'liq. bu shuni anglatadiki, p = np bo'lmasa , qaror masalasini ixtiyoriy grafiklar uchun polinom vaqtida hal qilib bo'lmaydi . kuchli qattiqligi natijalar ham u uchun qiyin ekanligini ko'rsatib ma'lum yondashadi . biroq, u yo'naltirilgan asiklik grafiklar uchun chiziqli vaqt yechimiga ega bo'lib , u rejalashtirish muammolarida muhim yo'lni topishda muhim ilovalarga ega . 1-misol. 1-shaklda tasvirlangan orgrafda oltita uch va o'n bitta yoy bo'lib, har bir yoy uzunligi uning yoniga yozilgan. ko`rinib turibdiki, berilgan grafda manfiy uzunlikka ega (5,3) yoy ham bor. isbotlash mumkinki, bu grafda umumiy uzunligi manfiy bolgan sikl …

i bo`lgan bitta (1,2) yoy bo`lgani uchun faqat bitta tengsizlikning bajarilishini tekshirish kifoya. bu tengsizlik ko`rinishidagi to`g`rimunosabatdan iborat bo`lgani uchun 2-iteratsiyaga o`tamiz. 2-iteratsiya. (1,3),(1,4),(2,3),(2,5)} bo’lgani sababli , , va qiymatlarni va min ekanligini aniqalaymiz. bu yerda eng kichik qiymat (2,3) yoyga mos keladi. shuning uchun, (2,3) yoyni ajratamiz va qiymatni 3 belgili uchga mos qo’yamiz. 3 belgili uchni to’plamdan chiqarib, r to`plamga kiritilgandan so`ng r={1,2,3} va to`plamlar hosil bo`ladi. ikkala uchi ham r to`plamga tegishli bo`lgan uchta (1,2),(1,3) va (2,3) yoylardan birinchisi uchun tengsizlikning bajarilishi 1-iteratsiyada tekshirilganligi va qiymatlarning o`zgarmaganligi sababli faqat ikkinchi va uchinchi yoylarga mos va munosabatlarni tekshirish kifoya. bu musosabatlar va ko`rinishida bajariladi. shuning uchun 3-iteratsiyaga o`tamiz. 3-iteratisiya. boshlang`ich uchi r={1,2,3} to`plamga tegishli, oxiri esa to`plamga tegishli bo`lgan yoylar to`rtta: (1,4), (2,5), (3,4) va (3,5). shu yoylarga mos ning qiymatlari va shuning uchun min bo`ladi. demak, bu iteratsiyada (2,5) yoyni ajratamiz va deb olamiz. endi algoritmga ko`ra, …

Хотите читать дальше?

Скачайте полный файл бесплатно через Telegram.

Скачать полный файл

О "eng katta daraxt haqida, eng qisqa vaeng uzun yo’l haqida, tarmoqli rejalashtirish, kommunikatsiyalar turlari oqimi"

1693470927.docx eng katta daraxt haqida, eng qisqa vaeng uzun yo’l haqida, tarmoqli rejalashtirish, kommunikatsiyalar turlari oqimi eng katta daraxt haqida, eng qisqa vaeng uzun yo’l haqida, tarmoqli rejalashtirish, kommunikatsiyalar turlari oqimi reja: 1. kirish 2. daraxt va unga ekvivalent tushunchalar 3. eng qisqa va eng uzun yo‘l 4. daraxtlarni prufer usulida kodlash 5. xulosa 6. foydalanilgan adabiyotlar daraxt va unga ekvivalent tushunchalar. siklga ega bo'lmagan oriyentirlanmagan bog'lamli graf daraxt deb ataladi. ta'rifga ko'ra, daraxt sirtmoqlar va karrali qirralarga ega emas. siklga ega bo'lmagan oriyentirlanmagan graf о'rmon (asiklik graf) deb ataladi. 1-misol.1-shaklda bog'lamli komponentali soni beshga teng bo'lgan graf tasvirlangan bo'lib, u o'rmondir. bu grafdagi bog'lamli k...

Формат DOCX, 382,5 КБ. Чтобы скачать "eng katta daraxt haqida, eng qisqa vaeng uzun yo’l haqida, tarmoqli rejalashtirish, kommunikatsiyalar turlari oqimi", нажмите кнопку Telegram слева.

Теги: eng katta daraxt haqida, eng qi… DOCX Бесплатная загрузка Telegram

eng katta daraxt haqida, eng qisqa vaeng uzun yo’l haqida, tarmoqli rejalashtirish, kommunikatsiyalar turlari oqimi

Предварительный просмотр (5 стр.)

Хотите читать дальше?

О "eng katta daraxt haqida, eng qisqa vaeng uzun yo’l haqida, tarmoqli rejalashtirish, kommunikatsiyalar turlari oqimi"

Похожие файлы