Mustaqil ish Mavzu: Yo‘naltirilgan graflarda marshrut, zanjir, sikl. Eng qisqa yo‘l topish algoritmlari Bajardi: Xoliqberdiyev Sardor Tekshirdi: Begimov O’ktam

O‘ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA
KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI



diskret tuzilmalar fanidan asoslari fanidan
mustaqil ish
Mavzu: Yo‘naltirilgan graflarda marshrut, zanjir, sikl. Eng qisqa yo‘l topish algoritmlari
Bajardi: Xoliqberdiyev Sardor


Tekshirdi: Begimov O’ktam
22-Mavzu
Yonaltirilgan graflarda marshrut, zanjir, sikl. Graflar nazariyasida “uch” iborasi o‘rniga, ba’zan, tugun yoki nuqta iborasi ham qo‘llaniladi. Umuman olganda, hanuzgacha graflar nazariyasining ba’zi iboralari bo‘yicha umumiy kelishuv qaror topmagan. Shuning uchun, bundan keyingi ta’riflarda, imkoniyat boricha, muqobil (alternativ) iboralarni ham keltirishga harakat qilamiz.
G U U grafning ta’rifiga ko‘ra, bo‘sh kortej bo‘lishi ham mumkin. Agar bo‘sh
b ( a a bo‘lmasa, u holda bu kortej ( , ) ko‘rinishdagi juftliklardan1 tashkil topadi.
Graflar nazariyasida “uch” iborasi o‘rniga, ba’zan, tugun yoki nuqta iborasi ham qo‘llaniladi. Umuman olganda, hanuzgacha graflar nazariyasining ba’zi iboralari bo‘yicha umumiy kelishuv qaror topmagan. Shuning uchun, bundan keyingi ta’riflarda, imkoniyat boricha, muqobil (alternativ) iboralarni ham keltirishga harakat qilamiz.
G U U  (V, U) grafning ta’rifiga ko‘ra, bo‘sh kortej bo‘lishi ham mumkin. Agar bo‘sh
b ( a a  , b V V ) bo‘lmasa, u holda bu kortej ( , ) ko‘rinishdagi juftliklardan1 tashkil topadi,
U ( a a  , b b ) bunda bo‘lishi hamda ixtiyoriy juftlik kortejda istalgancha marta qatnashishi mumkin.
(a b a , b)  U juftlikni tashkil etuvchi va uchlarning joylashish tartibidan bog‘liq holda, ya’ni
(a, b) yo‘nalishning borligi yoki yo‘qligiga qarab, uni turlicha atash mumkin. Agar juftlik uchun
( ( a, a b) ,  b (b, ) a) uni tashkil etuvchilarning joylashish tartibi ahamiyatsiz, ya’ni bo‘lsa, juftlikka yo‘naltirilmagan (oriyentirlanmagan) qirra (yoki, qisqacha, qirra) deyiladi. Agar bu
( ( a, a b) ,  b (b, ) a) tartib muhim, ya’ni bo‘lsa, u holda juftlikka yoy yoki yo‘naltirilgan (oriyentirlangan) qirra deyiladi.
U kortejning tarkibiga qarab, uni yo grafning qirralari korteji, yo yoylari korteji, yoki