Mustaqil ish 7 Topshirdi: absamatov j

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 va n=m—1 tenglik Agar qandaydir ikki uch bittadan ko'p, masalan, ikkita turli oddiy zanjir vositasida tutashtirilishi imkoniyati bo'lsa, u holda bu uchlarning biridan zanjirlarning birontasi bo'ylab harakatlanib ikkinchi uchga, keyin bu uchdan ikkinchi zanjir bo'ylab harakatlanib dastlabki uchga qaytish imkoniyati bor bo'lar edi. Ya'ni qaralayotgan graf da sikl topilar edi. Minimal uzunlikka ega yo‘l haqidagi masala. Berilgan bog'lamli grafning har bir qirrasiga (agar berilgan graf oriyentirlangan bo‘lsa — yoyiga) qandaydir haqiqiy son mos qo‘yib, bu sonni qirraning (yoyning) uzunligi, deb ataymiz. Qirraning (yoyning) uzunligi additivlik xossasiga ega deb faraz qilamiz, ya’ni qirralar (yoylar) yordamida tuzilgan zanjiming (yo ‘Ining) uzunligi shu zanjirni (yo‘lni) tashkil etuvchi qirralar (yoylar) uzunliklari yig‘indisiga tengdir. Tabiiyki, qirraning yoki yoyning uzunligi tushunchasi yechilayotgan masalaning mohiyatiga 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 mumkin. Agar grafda biron i uchdan chiqib, j uchga kiruvchi yoy mavjud bo‘lmasa, u holda bu yoyning uzunligini cheksiz katta deb qabul qilamiz ( ). Bundan tashqari, G grafda umumiy uzunligi manfiy bo‘lgan sikl mavjud emas, deb hisoblaymiz, chunki aks holda uzunligi eng kichik bo‘lgan yo‘l mavjud emas. Minimal uzunlikka ega yo‘l haqidagi masalani hal etish usullari orasida Deykstra tomonidan taklif etilgan algoritm ko‘p qo‘llaniladi. Quyida grafning 1 belgili uchidan chiqib (bu uchni manba deb qabul qilamiz), grafdagi ixtiyoriy к uchgacha (bu uchni oxirgi uch deb hisoblaymiz) eng qisqa uzunlikka ega yo‘lni topish imkonini beruvchi Deykstra algoritmi keltirilgan. Graf nazariyasida eng uzun yo'li muammo oddiy topish muammo emas yo'lini berilgan chizma maksimal uzunligi. Yo'l oddiy deyiladi, agar uning takroriy uchlari bo'lmasa; yo'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