Yönləndirilmiş və İstiqamətsiz Qrafik
Qrafik təpə və kənarlar toplusundan ibarət riyazi strukturdur. Qrafik bəzi keçidlər (kənarlarla təmsil olunan) vasitəsilə birləşdirilən obyektlər toplusunu (təpələrlə təmsil olunur) təmsil edir. Riyazi qeydlərdən istifadə edərək qrafiki G ilə təmsil etmək olar, burada G=(V, E) və V təpələr çoxluğu, E isə kənarlar çoxluğudur. İstiqamətsiz qrafikdə təpələri birləşdirən kənarlarla əlaqəli istiqamət yoxdur. İstiqamətləndirilmiş qrafikdə təpələri birləşdirən kənarlarla əlaqəli istiqamət var.
İstiqamətsiz Qrafik
Daha əvvəl qeyd edildiyi kimi, istiqamətsiz qrafik qrafikin təpələrini birləşdirən kənarlarında heç bir istiqamətin olmadığı qrafikdir. Şəkil 1-də V={V1, V2, V3} təpələri dəsti olan istiqamətsiz qrafik təsvir edilmişdir. Yuxarıdakı qrafikdəki kənarlar çoxluğu V={(V1, V2), (V2, V3), (V1, V3)} kimi yazıla bilər. Onu da qeyd etmək olar ki, kənarların istiqaməti olmadığı üçün kənarlar çoxluğunu V={(V2, V1), (V3, V2), (V3, V1)} kimi yazmağa heç nə mane olmur. Buna görə də yönləndirilməmiş qrafikdə kənarlar sıralanmış cütlər deyil. Bu, yönləndirilməmiş qrafikin əsas xüsusiyyətidir. İstiqamətsiz qrafiklər təpələrlə təmsil olunan obyektlər arasında simmetrik əlaqələri təmsil etmək üçün istifadə edilə bilər. Məsələn, bir sıra şəhərləri birləşdirən ikitərəfli yol şəbəkəsi istiqamətləndirilməmiş qrafikdən istifadə etməklə təqdim edilə bilər. Şəhərlər qrafikdə təpə nöqtələri ilə, kənarlar isə şəhərləri birləşdirən iki tərəfli yolları təmsil edə bilər.
İstiqamətli Qrafik
İstiqamətləndirilmiş qrafik təpələri birləşdirən qrafikin kənarlarının istiqamətə malik olduğu qrafikdir. Şəkil 2-də V={V1, V2, V3} təpələri dəsti ilə istiqamətlənmiş qrafik təsvir edilmişdir. Yuxarıdakı qrafikdəki kənarlar çoxluğu V={(V1, V2), (V2, V3), (V1, V3)} kimi yazıla bilər. İstiqamətsiz qrafikin kənarları sıralanmış cütlərdir. Formal olaraq, istiqamətləndirilmiş qrafikdə e kənarı sıralı e=(x, y) cütü ilə təmsil oluna bilər, burada x e kənarının başlanğıcı, mənbəyi və ya başlanğıc nöqtəsi adlanan təpədir və y təpəsi son nöqtə adlanır., son nöqtə və ya son nöqtə. Məsələn, bir tərəfli yollardan istifadə edərək bir sıra şəhərləri birləşdirən yol şəbəkəsi yönləndirilməmiş qrafikdən istifadə etməklə təqdim edilə bilər. Şəhərlər qrafikdə təpə nöqtələri ilə, istiqamətlənmiş kənarlar isə yolda nəqliyyatın hərəkət istiqamətini nəzərə alaraq şəhərləri birləşdirən yolları təmsil edə bilər.
İstiqamətli Qrafik və İstiqamətsiz Qrafik arasındakı fərq nədir?
Yönləndirilmiş qrafikdə kənar sıralı cütdür, burada sifarişli cüt iki təpəni birləşdirən kənarın istiqamətini təmsil edir. Digər tərəfdən, yönləndirilməmiş bir qrafikdə kənar nizamlanmamış cütdür, çünki kənar ilə əlaqəli istiqamət yoxdur. İstiqamətsiz qrafiklər obyektlər arasında simmetrik əlaqələri təmsil etmək üçün istifadə edilə bilər. İstiqamətsiz qrafikdə hər bir düyünün dərəcə və xarici dərəcələri bərabərdir, lakin bu, yönəldilmiş qrafik üçün doğru deyil. İstiqamətsiz qrafiki təmsil etmək üçün matrisdən istifadə edərkən, matris həmişə simmetrik bir qrafikə çevrilir, lakin bu, yönəldilmiş qrafiklər üçün doğru deyil. İstiqamətsiz qrafik, hər bir kənarı əks istiqamətdə gedən iki yönəldilmiş kənar ilə əvəz etməklə istiqamətləndirilmiş qrafikə çevrilə bilər. Bununla belə, istiqamətləndirilmiş qrafiki yönləndirilməyən qrafikə çevirmək mümkün deyil.
