|
Guruh talabasi rejabov nodirbek adiljonovichning
|
| bet | 4/6 | | Sana | 30.09.2023 | | Hajmi | 107.7 Kb. | | #85737 |
Bog'liq Diskret tuzilmalar 1. KTE xxx, diskerit bazza 22.02.2023, Тестлар Big Data-uz, MUSTAQIL TA'LIM MAVZULARI, 713, 1-dedlayn G, 1-6 simsizMarshrutning uzunligi deb undagi qirralar soniga aytiladi.
Turli qirralardan tashkil topgan marshrutga zanjir deb ataladi
Grafning bog‘lamliligi tushunchasi. Agar oriyentirlanmagan grafda chetlari a va b uchlardan iborat marshrut topilsa, bu a va b uchlar bog‘langan deb, marshrutning o‘zi esa a va b uchlarni bog‘lovchi marshrut deb ataladi.
Tabiiyki, agar qandaydir uchlarni bog‘lovchi marshrut biror at uchdan bir necha marta o‘tsa, u holda marshrutning siklik qismini olib tashlab (bunda siklik qismning o‘rniga marshrutda faqat ai uch qoldiriladi) yana o‘sha uchlarni bog‘lovchi oddiy zanjir ko‘rinishdagi marshrutni hosil qilish mumkin. Shuning uchun, marshrut bilan bog‘langan uchlar doimo oddiy zanjir bilan ham bo'glangan bo‘ladi, degan xulosaga kelamiz.
Bir-biri bilan ustma-ust tushmaydigan ixtiyoriy ikkita uchlari bog‘langan graf bog‘lamli graf deb ataladi.
Bir-biri bilan ustma-ust tushmaydigan ixtiyoriy ikkita uchlari bog‘langan graf bog‘langan graf deb ataladi.
Agar grafdagi ikkita uchni biror oddiy zanjir bilan tutashtirish mumkin bo`lsa, u holda bu ikkita uch bog‘langan deyiladi. Bunday uchlar to‘plami grafda ekvivalentlik munosabati bilan aniqlangan deb hisoblanadi. Uchlar to‘plami bo‘yicha ekvivalentlik munosabatini inobatga olgan holda berilgan grafni bog‘lamlilik komponentlari deb ataluvchi bog‘lamli qismlarning birlashmasi deb qarash mumkin.
Tekis G(V,U) graf uchun mr1nk tenglik o`rinlidir, bunda mV , nU , r – yoqlar soni, k – bog‘lamlilik komponentalar soni.
n uzunlikdagi marshrut deb n ta qirraning bo`sh bo`lmagan ketma-ketligiga aytiladi. Qo`shni yoylar ketma-ketligi yo`l, qo`shni qirralar ketma-ketligi zanjir deyiladi. Boshqacha ta’riflansa, takroriy qirralarga ega bo`lmagan marshrut zanjir deyiladi. Yopiq zanjir esa sikl deyiladi.
|
| |
