Muhammad Al - Xorazmiy
nomidagi Toshkent axborot texnologiyalar universiteti “Elektr energetika yoʻnalishi talabasi Tilovov Shahbozning Diskret tuzilmalar fanidan yozgan
MUSTAQIL ISHI
O’qituvchi:Turg’unov Abrorjon
MAVZU : Graflarda marshrutlar, sikllar marshrut narxi
REJA :
Graflarda marshrutlar
Graflarda sikllar
Marshrut narxi
Xulosa
Foydalanilgan adabiyotlar
Graflarda marshrutlar
Marshrutlar va zanjirlar haqida umumiy ma’lumotlar. Uchlari to‘plami F = { v1, v2, . . . , vn} va qirralar korteji U={u1 u2 ...,un} bolgan oriyentirlanmagan G=( V, U) graf berilgan bolsin. Bu G grafdagi uchlar va qirralaming har ikki qo‘shni qirralari umumiy chetki uchga ega
ko‘rinishdagi chekli yoki cheksiz ketma-ketligi marshrut, deb ataladi. Marshrutni uning uchlari ketma-ketligi (..., vi1, vi2...) yoki qirralari ketma-ketligini (...,uj1,uj2,...) ko‘rinishda ham belgilash
mumkin.
Agar marshrutda qandaydir uchdan oldin uchlar bo‘lmasa,
bu uchni marshrutning boshlang‘ich uchi deb, shu uchdan keyin marshrutga tegishli uchlar bo‘lmaganda esa, uni marshrutning oxirgi uchi, deb ataydilar.
Agar marshrutning boshlang‘ich uchi vp va oxirgi uchi vq bo‘lsa, u holda uni vp uchdan vq uchga yo ‘nalgan marshrut yoki chetlari vp va vq b o ‘Igan marshrut, deb ataladi.
Marshrutdagi ikki qo'shni qirraga tegishli uch ichki uch yoki oraliq uch, deb ataladi.
Marshrutda qirralar va uchlar takrorlanishi mumkin bo‘lgani uchun marshrutning ichki uchi, bir vaqtning o'zida, uning boshlang‘ich va (yoki) oxirgi uchi bo'lishi ham mumkin va teskarisi, marshrutning boshlang‘ich va (yoki) oxirgi uchi uning ichki uchi bo‘lishi ham mumkin.
Tabiiyki, marshrut:
— boshlang‘ich uchga ham, oxirgi uchga ham ega bo‘lmasligi mumkin (bunday marshrut ikki tomonlama cheksiz marshrut, deb ataladi);
— boshlang‘ich uchga ega bo‘lib, oxirgi uchga ega bo‘lmasligi mumkin yoki, aksincha, oxirgi uchga ega bo‘lib, boshlang‘ich uchga ega bo‘lmasligi mumkin (bir tomonlama cheksiz marshrut)
—yagona qirradan iborat bo‘lishi mumkin (notrivial marshrut)
— bironta ham qirraga ega bolmasligi mumkin (noI marshrut yoki trivial marshrut).
Marshrutning uzunligi deb undagi qirralar soniga aytiladi.
1-misol. Ushbu shaklda tasvirlangan graf uchun
ketma-ketlik 3 belgili uchdan 4 belgili uchga yo‘nalgan marshrutdir, bunda 3 — boshlang‘ich uch, 4 — oxirgi uchdir. Bu marshrutda 1, 2 va 3 belgili uchlar oraliq uchlar hisoblanadi. Qaralayotgan marshrutning uzunligi 6a teng bo‘lib, u zanjir bo‘la olmaydi, chunki unda 1 belgili uch 2 marta (bir marta oraliq uch sifatida,
ikkinchi marta esa oxirgi uch sifatida) qatnashmoqda.
Yana o‘sha grafuchun (3,2,1,3) zanjiming oxirgi bo‘g‘ini sifatida u2 yoki u1qirralardan qaysisi olinishiga bog'liqsiz ravishda, u yopiq
zanjir va sikldir.
Oriyentirlangan graflar uchun ham undagi yoylaming yo‘na-
lishi (oriyentatsiyasi)ni inobatga olmasdan oriyentirlanmagan marshrut, zanjir va oddiy zanjir tushunchalarini kiritish mumkin. Lekin oriyentirlangan graflar uchun oriyentirlangan marshrut tushunchasini kiritish tabiiydir.
Yoylaming oriyentatsiyalari hisobga olingan yoylar va uchlar ketma-ketligi oriyentirlangan marshrut, deb ataladi. Oriyentirlangan marshrut uchun zanjir tushunchasiga o‘xshash yo‘l (yoki oriyentirlangan zanjir) tushunchasini ham kiritish mumkin.
|
