O’zbekiston respublikasi oliy ta‟lim, fan va innovatsiyalar vazirligi

2.1Yo`naltirilgan grafika

Yo'naltirilgan grafika - bu grafikning tepaliklarni bog'laydigan qirralari yo'nalishga ega bo'lgan grafikdir. 2 -rasmda V = {V1, V2, V3} tepaliklar to'plami bilan yo'naltirilgan grafik tasvirlangan. Yuqoridagi grafikdagi qirralarning to'plami V = {(V1, V2), (V2, V3), (V1, V3)} shaklida yozilishi mumkin. Yo'naltirilmagan grafikdagi qirralar tartibli juftliklardir. Rasmiy ravishda, yo'naltirilgan grafikdagi e chekka e = (x, y) tartibli juftlik bilan ifodalanishi mumkin, bu erda x - chekkaning boshi, manbai yoki boshlang'ich nuqtasi deb nomlangan tepalik, y tepasi esa nuqta deyiladi , vertex yoki terminal nuqtasini tugatish. Masalan, shaharlar majmuasini bir tomonlama yo'llar yordamida bog'laydigan yo'l tarmog'i yo'naltirilmagan grafik yordamida ifodalanishi mumkin. Shaharlar grafikdagi tepaliklar bilan ifodalanishi mumkin va yo'naltirilgan qirralar shaharda transport harakati yo'nalishini hisobga olgan holda bog'laydigan yo'llarni ifodalaydi.

Yo'naltirilmagan grafikda tepaliklarni bog'laydigan qirralar bilan bog'liq yo'nalish yo'q. Yo'naltirilgan grafikda tepaliklarni bog'laydigan qirralar bilan bog'liq yo'nalish mavjud. Yo'naltirilgan grafikda chekka - bu tartibga solingan juftlik, bu erda tartiblangan juftlik ikki tepalikni bog'laydigan qirraning yo'nalishini ifodalaydi. Boshqa tomondan, yo'naltirilmagan grafikda chekka - bu tartibga solinmagan juftlik, chunki chekka bilan bog'liq yo'nalish yo'q. Yo'naltirilmagan grafikalar ob'ektlar orasidagi nosimmetrik munosabatlarni ifodalash uchun ishlatilishi mumkin. Yo'naltirilmagan grafikdagi har bir tugunning darajasi va darajasi teng, lekin bu yo'naltirilgan grafik uchun to'g'ri emas. Yo'naltirilmagan grafikni ko'rsatish uchun matritsadan foydalanganda, matritsa har doim nosimmetrik grafikga aylanadi, lekin bu yo'naltirilgan grafikalar uchun to'g'ri emas. Yo'naltirilmagan grafikni har bir qirrani qarama -qarshi tomonga yo'naltirilgan ikkita qirraga almashtirish orqali yo'naltirilgan grafikka aylantirish mumkin. Biroq, yo'naltirilgan grafikni yo'naltirilmagan grafikaga aylantirish mumkin emas.