Yunaltirilgan va yunaltirilmagan graflar

Yunaltirilgan va yunaltirilmagan graflar

Yo`naltirilmagan grafika Yo'naltirilmagan grafik - bu grafikning tepalarini bog'laydigan qirralarda yo'nalish bo'lmagan grafik. 1 -rasmda V = {V1, V2, V3} tepaliklar to'plami bilan yo'naltirilmagan grafik tasvirlangan. Yuqoridagi grafikdagi qirralarning to'plami V = {(V1, V2), (V2, V3), (V1, V3)} shaklida yozilishi mumkin. Shuni ham ta'kidlash mumkinki, qirralarning V = {(V2, V1), (V3, V2), (V3, V1)} deb yozilishiga hech narsa to'sqinlik qilmaydi, chunki qirralarning yo'nalishi yo'q. Shuning uchun yo'naltirilmagan grafikdagi qirralar tartibli juftliklar emas. Bu yo'naltirilmagan grafikning asosiy xarakteristikasi. Yo'naltirilmagan grafikalar tepaliklar bilan tasvirlangan ob'ektlar orasidagi nosimmetrik munosabatlarni ifodalash uchun ishlatilishi mumkin. Masalan, shaharlar majmuasini bog'laydigan ikki tomonlama yo'l tarmog'ini yo'naltirilmagan grafik yordamida ko'rsatish mumkin. Shaharlar grafikdagi tepaliklar bilan ifodalanishi mumkin va qirralari shaharlarni bog'laydigan ikki tomonlama yo'llarni ifodalaydi.

Yo`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.