Yo`naltirilgan grafika Yo'naltirilgan grafika - bu grafikning tepaliklarni bog'laydigan qirralari
yo'nalishga ega bo'lgan grafikdir. 2.b-rasmda
1
2
3
,
,
V V V V =
tepaliklar to'plami bilan
yo'naltirilgan grafik tasvirlangan. Yuqoridagi grafikdagi qirralarning to'plami
(
) (
) (
)
1
2
2
3
1
3
,
,
,
,
,
V V V V V V V =
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.
2.
A) yo’naltirilmagan graf; 2.B) yo’naltirilgan graf
