Mavzu: eng katta daraxt, eng qisqa va eng uzun yo‘l reja

MAVZU: ENG KATTA DARAXT, ENG QISQA VA ENG UZUN YO‘L

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 berish mumkin. Umuman olganda, G(m,n)-gvaf uchun daraxtlar haqidagi asosiy teorema, deb ataluvchi quyidagi teorema o'rinlidir.


1-teorema. Uchlari soni m va qirralari soni n bo 'Igan G graf uchun quyidagi tasdiqlar ekvivalentdir:

• 
  G daraxtdir;
  
• 
  G asiklikdir va n=m—l;
  
• 
  G bog'lamlidir va n=m—\;
  

Induksion o'tish: G daraxt uchun k>2 vam=k bo'lganda, 2) tasdiq o'rinli bo'lsin deb faraz qilamiz. Endi uchlari soni m=k+l va qirralari soni n bo'lgan daraxtni qaraymiz. Bu daraxtning ixtiyoriy qirrasini (vp v2) bilan belgilab, undan bu qirrani olib tashlasak, Vj uchdan v2 uchgacha marshruti (aniqrog'i, zanjiri) mavjud bo'lmagan grafni hosil qilamiz, chunki agar hosil bo'lgan grafda bunday zanjir bor bo'lsa edi, u holda G daraxtda sikl topilar edi. Bunday bo'lishi esa mumkin emas.

Hosil bo'lgan graf ikkita Gl va G2 bog'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 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 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 mavjud emas.

1-shakl
Yuqorida bayon qilingan Deykstra algoritmini berilgan grafga eng qisqa uzunlikka ega yo’lni topish bilan shug‘ullanamiz. Dastlabki qadam. Manbaga (I belgili uchga) ei=0 qiymatm mos qo'yamiz va R={1} to`plamga ega bo'lamiz. Shuning uchun. 7r.v\ R.{ 2 ,3 ,4,5,6} be' ladi.
Umumiy qadam. 1-iteratsiya. R={1} va bo‘lgani uchun boshlang‘ich uchi R to`plamga tegishli, oxirgi uchi esa to`plam elementi bo`lgan barcha yoylar to`plami ga ega bo`lamiz. (R, ) to`plamga tegishli bo`lgan har bir yoy uchun ning qiymatlarini topamiz:
(1,2) yoy uchun
(1,3) yoy uchun
(1,4) yoy uchun
Bu , va miqdorlar orasida eng kichigi bo`lgani uchun (1,2) yoyni ajratamiz. (2-shaklda bu yoy qalin chiziq bilan belgilangan) va 2 belgili uchga qiymatni mos qo`yamiz. Algoritmga ko`ra 2 uchni to`plamdan chiqarib, R to`plamga kiritamiz. Natijada R={1,2} va ={3,4,5,6} to`plamlarga ega bo`lamiz.
Ikkala uchi ham R to`plamga tegishli 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, R={1,2,3,5} va to`plarni hosil qilamiz.
Ikkala uchi ham R to`plamga tegishli bo`lgan yoylar oltita: (1,2), (2,3), (1,3), (2,5), (3,5) va (5,3). Bu yoylarning har biri uchun tengsizlikning bajarilishini tekshirishimiz kerak. Lekin, 1- va 2-iteratsiyalarda (1,2), (2,3) va (1,3) yoylar uchun bu ish bajarilganligi sababli tekshirishni tarkibida 5 belgili uch qatnashgan (2,5), (3,5) va (5,3) yoylar uchun amalga oshirib, quyidagilarga ega bo`lamiz. (2,5) yoy uchun munosabat to`g`ri ), (3,5) yoy uchun munosabat to`g`ri ), lekin (5,3) yoy uchun munosabat noto`g`ri ). Oxirgi munosabatni hisobga olib, algoritmga ko`ra, deb olamiz va (5,3) yoyni ajratilgan deb, ilgari ajratilgan (2,3) yoyni ajratilmagan deb hisoblaymiz. (2-shaklda yozuvning va (2,3) yoyning qalin chizig`i ustiga ajratilganlikni inkor qiluvchi x belgisi qo`yilgan.

2-shakl
4-iteratsiya. R={1,2,3,5}, bo`lgani uchun va bo`ladi. Demak (1,4) va (3,4) yoylarni ajratamiz hamda 4 belgili uchga qiymatni mos qo`yamiz. Natijada R={1,2,3,5,4}, to`plamga ega bo`lamiz.
munosabatning to`g`riligi (1,3),(1,4),(2,3),(3,5),(5,3) va (3,4) yoylar uchun tekshirilib ko`rilganda, uning barcha yoylar uchun bajarilishi ma’lum bo`ladi.
Oxirgi qadam. Berilgan orgrafda 1 belgili uchdan 6 belgili uchgacha eng qisqa uzunlikka ega yo'1(lar)ni topish maqsadida, algoritmga asosan, grafning oxirgi 6 belgili uchidan boshlab ajratilgan yoylar yo`nalishiga qarama-qarshi yo`nalishda harakatlanib, 1 belgili uchiga kelishimiz kerak. 6 belgili uchga kiruvchi uch yoydan faqat bittasi ((4,6) yoy) ajratilgan bo'lgani uchun yoy yo`nalishiga qarama-qarshi yo`nalishda harakat qilib, uchdan 4 belgili uchga kelamiz. 4 belgili uchga kiruvchi ikkala ((1,4) va (3,4)) yoylar ham ajratilgan bo`lgani uchun biz tuzmoqchi bo`lgan eng qisqa uzunlikka ega yo'l yagona emas.
Agar harakatni (1,4) yoy yo`nalishiga teskari yo`nalishda davom ettirsak, u holda 4 belgili uchdan 1 belgili uchga kelib, eng qisqa uzunlikka ega yo`llardan biri bo`lgan marshrutni topamiz.
Agarda harakatni (3,4) yoy yo'nalishiga teskari yo`nalishda davom ettirsak, u holda 4 belgili uchdan 3 belgili uchga kelamiz. 3 belgili uchga kiruvchi ikkita yoydan faqat bittasi ((5,3) yoy) ajratilgan bo'lgani uchun 3 belgili uchdan 5 belgili uchga kelamiz. Shu usulda davom etsak, oldin 2 belgili, keyin esa 1 belgili uchga o`tib. mumkin bo'lgan eng qisqa uzunlikka ega bolgan yo'llardan ya'ni =(1,2,5,3,4,6) marshrutni aniqlaymiz.
Shunday qilib, 1-shaklda tasvirlangan graftda eng qisqa uzunlikka ega yo'llar borligini aniqladik. Bu yo'llaming har biri =14 uzunlikka ega.
Yorliqli daraxtlar informatikaning amaliy va nazariy sohalarida qiziqish uyg'otadi. Misol uchun, Ethernet terminal qurilmalari o'rtasida noyob yo'lga ega, shuning uchun daraxt bo'ladi: tarmoqdagi har bir qurilmani noyob tarzda aniqlash uchun daraxt tugunlarini belgilash kerak. Daraxt ma'lumotlar tuzilmalarining kompyuter xotiralarida odatiy ko'rinishlariga qiziqarli alternativa tugun belgilarining satrlari orqali etiketli daraxtlarni kodlashga asoslangan. Bu tasvir birinchi marta Kayli teoremasini isbotlashda n ta tugundagi erkin yorliqli daraxtlar va n-2 uzunlikdagi satrlar o‘rtasidagi yakkama-yakka muvofiqlikni ko‘rsatish uchun ishlatilgan. Ushbu sof matematik foydalanishga qo'shimcha ravishda, daraxtlarni satrga asoslangan kodlash ko'plab amaliy dasturlarga ega. Masalan, ular tasodifiy bir xil taqsimlangan daraxtlar va tasodifiy bog'langan grafiklarni yaratishga imkon beradi: tasodifiy qatorni yaratish, keyin tez kodlash algoritmidan foydalanish odatda qirralarning qo'shilishi bilan tasodifiy daraxt hosil qilishdan ko'ra samaraliroqdir, chunki Ikkinchi holatda, tsikllarni kiritmaslikka e'tibor berish kerak. Bundan tashqari, daraxt kodlari genetik algoritmlarda qo'llaniladi, bunda populyatsiyadagi xromosomalar butun sonlar qatori sifatida ifodalanadi va qo'shimcha cheklovlar bilan, masalan, barglar soni yoki daraxtning diametri bo'yicha minimal masofani hisoblash uchun evristikada qo'llaniladi. . So'nggi emas, daraxt kodlari ma'lumotlarni siqish va grafiklarning daraxt va o'rmon hajmlarini hisoblash uchun ishlatiladi.
T tugunlari 0 dan n-1 gacha raqamlangan etiketli daraxt bo'lsin. T dagi ba'zi v cho'qqilar uchun d[v] bilan belgilangan v darajasi v ga to'g'ri keladigan qirralarning sonidir.Agar d[v]=1 bo'lsa, v barg deyiladi. Pruferning isbotiga ko'ra, n-2 raqamlarining har qanday ketma-ketligi, {0,1,...,n-1} dagi har bir raqam n ta tugunning noyob etiketli daraxtini aniqlay oladi. Bunday raqamlar ketma-ketligi etiketli daraxtning Prufer kodidir. A algoritmi Prufer isbotini to'g'ridan-to'g'ri amalga oshirishdir.
Algoritm A
Kirish: n-1 qirralarning roʻyxati sifatida n ta tugundan iborat T etiketli daraxt.
Chiqish: c, T ning Prufer kodi.
Usul:
1-qadam. B←{0,1,…,n-1}.
2-qadam. For i ← 0 to n-3 do
2.1-qadam. x ← min{k B: k - barg }.
2.2-qadam. B←B-{x}.
2.3-qadam. T dan x va uning tushuvchi chetini (x, y) olib tashlang.
2.4-qadam. c[i]←y.
3-qadam. Return c.
Misol uchun, kirish yorlig'i bilan belgilangan daraxt T 1-rasmda tasvirlangan grafik bo'lsin. Algoritm A tugagandan so'ng, c = [2,4,0,1,3,3] bu Prufer kodidir.

XULOSA
Men ushbu mustaqil ishni bajarib eng katta daraxt, eng qisqa va eng uzun yo‘l haqida tushunchaga ega bo‘ldim. Agar grafning markazidan boshqa biron 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 obyektning (kasalxona, maktab va shu kabilaming) joylashish о‘mini aniqlash bilan bog‘liq muammolami hal qilishda qo‘llanilishi mumkin. Ta’kidlash kerakki, muayyan vaziyatlarda, ko‘pincha, boshqa holatlami, jumladan, obyektgacha borish vaqti, punktlar orasidagi masofa va shu kabilami hisobga olishga to‘g‘ri keladi. Bunday vaziyatlarda joylashtirishning minimaks masalalari, deb ataluvchi masalalar vujudga keladi.

FOYDALANILGAN ADABIYOTLAR

1. 
   Diskret matematika. Sadaddinova S.S., Abduraxmanova Yu.M., Raximova F.S Toshkent-2014
   
2. 
   Kombinatorika va graflar nazariyasi., H. TO‘RAYEV, I. AZIZOV, S. OTAQULOV., Toshkent-2009
   
3. 
   Internet sahifalari va Wikipedia ma’lumotlari