1
O‘ZBEKISTON RESPUBLIKASI AXBOROT
TEXNOLOGIYALARI VA
KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI
UNIVERSITETI
MUSTAQIL ISH
Bajardi:
Tashniyozov Sardor
Tekshirdi:
Begimov Oybek
Toshkent-2024
2
Mavzu: Oriyentirlangan graflar uchun insidensiya matritsasi.
Narxlangan grafda arzon marshrutni aniqlash
Reja:
Kirish
1.
Graf haqida tushunchasi
2.
Oriyentirlangan graflar uchun insidensiya matritsasi.
3.
Grafda arzon marshrutni aniqlash
Xulosa
FOYDALANILGAN ADABIYOTLAR
3
Mavzu: Oriyentirlangan graflar uchun insidensiya matritsasi
Narxlangan grafda arzon marshrutni aniqlash
Kirish
Graflar nazariyasi haqida umumiy ma’lumotlar. 1736 yilda L. Eyler tomonidan
o‘sha davrda qiziqarli amaliy masalalardan biri hisoblangan Kyonigsberg ko‘priklari
haqidagi masalaning qo‘yilishi va yechilishi graflar nazariyasining paydo bo‘lishiga
asos bo‘ldi.
Graf yoyi uchun uning chetki uchlarini ko‘rsatish tartibi muhim ekanligini
ta’kidlaymiz, ya’ni va yozuvlar bir-biridan farq qiluvchi yoylarni ifodalaydi. Agar
yoy ko‘rinishda ifodalangan bo‘lsa, u holda uning boshlang‘ich uchi, esa oxirgi uchi
deb ataladi.
Qator hollarda oriyentirlanmagan qirralari ham, oriyentirlangan qirralari ham
bo‘lgan graflar bilan ish ko‘rishga to‘g‘ri keladi. Bunday graflar aralash graflar deb
ataladi.
mumiy holda uchlar to‘plami va (yoki) qirralar (yoylar, qirra va yoylar) korteji
cheksiz ko‘p elementli bo‘lishi mumkin. Bundan keyin to‘plam va kortej faqat chekli
bo‘lgan graflarni qaraymiz. Bunday graflar chekli graflar deb ataladi.
|
