Mustaqil ish 7 Topshirdi: absamatov j

. 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

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.