Qrafiklərin təqdimatı

6.1 Bitişiklik Matrisi: İş Prinsipi, Üstünlüklər və Mənfi Cəhətlər.

Bitişiklik matrisi — qrafikləri təqdim etmək üçün istifadə olunan üsuldur. Bu, kvadrat matrisi ölçüsündə n x n kimi təqdim olunur, burada n — qrafdakı qovşaqların sayıdır. Matrisin elementləri qovşaqlar arasında körpünün olub-olmamasını göstərir:

• Əgər i və j qovşaqları arasında körpü varsa, matris elementi A[i][j] = 1 (və ya əgər qraf çəkiyə malikdirsə, körpünün çəkisi).
• Əgər körpü yoxdursa, onda A[i][j] = 0.

Nümunə:

A, B, C qovşaqları və (A, B), (B, C) və (C, A) körpüləri olan qraf üçün bitişiklik matrisi belə görünəcək:

Əgər bütün qovşaqlar bir-biri ilə bağlı olsaydı, bitişiklik matrisi belə görünərdi:

Üstünlüklər:

• Sadəlik: anlamaq və implementasiya etmək asandır.
• Tez çıxış: iki qovşaq arasında körpünün olub-olmamasını yoxlamaq O(1) vaxtdır.
• Sıx qraflar üçün uyğundur: körpüləri çox olan qraflar üçün daha effektivdir.

Mənfi cəhətlər:

• Daha çox yaddaş tələb edir: O(n^2) yaddaş tələb edir, hətta qrafda daha az körpü olsa belə (seyrək qraf).
• Seyrək qraflar üçün qeyri-effektivlik: əgər qovuşmalar çoxdur və körpülər azdırsa, matrisin çox hissəsi sıfırlardan ibarət olacaq, bu da yaddaşın səmərəsiz istifadəsinə gətirib çıxarır.

6.2 Əlaqə siyahıları: iş prinsipi, üstünlükləri və çatışmazlıqları.

Əlaqə siyahıları — qrafı bir növ massiv siyahılar kimi təqdim etmə üsuludur. Massivin hər bir elementi qrafın bir zirvəsinə uyğundur və həmin zirvə ilə qonşuluqda olan bütün zirvələrin siyahısını ehtiva edir.

Nümunə:

A, B, C zirvələrindən ibarət və kənarları (A, B), (B, C) və (C, A) olan qraf üçün əlaqə siyahıları belə olacaq:

Əgər bütün zirvələr bir-biri ilə bağlı olsaydı, onda əlaqə siyahıları belə görünərdi:

Üstünlüklər:

• Yaddaşın effektli istifadəsi: yaddaş istifadəsi O(V + E) təşkil edir, burada V — zirvələrin sayı, E — kənarların sayı. Bu, əlaqə siyahılarını seyrək qraflar üçün daha münasib edir.
• Qrafın axtarış asanlığı: qrafın axtarış əməliyyatlarını yerinə yetirmək (məsələn, eni ilə axtarış və ya dərinliklə axtarış) üçün uyğundur.

Çatışmazlıqlar:

• Daha mürəkkəb giriş: iki zirvə arasında kənarın olub-olmadığını yoxlamaq O(k) vaxt tələb edir, burada k — zirvənin qonşularının sayıdır.
• Daha az anlaşılan struktur: əlaqə siyahıları əlaqə matrisi ilə müqayisədə daha çətin başa düşülən və həyata keçirilən bir strukturdur.

6.3 Müxtəlif qraf təmsil üsullarının müqayisəsi.

Gəlin qraf təmsilinin müxtəlif üsullarını müqayisə edək.

1. Bitişiklik matrisi:

• Sadəlik: anlamaq və reallaşdırmaq asandır.
• Yaddaş: O(n^2) yaddaş tələb edir, bu isə seyrək qraflar üçün qeyri-effektiv ola bilər.
• Əlçatanlıq sürəti: qırıq varlığını yoxlamaq O(1) müddətində həyata keçirilir.
• Uyğunluq: çox sayda qırıq ilə fərqlənən sıx qraflar üçün uyğundur.

2. Bitişiklik siyahıları:

• Sadəlik: bitişiklik matrisindən daha az aydındır, amma yenə də başa düşüləndir.
• Yaddaş: O(V + E) yaddaş tələb edir, bu isə seyrək qraflar üçün daha effektivdir.
• Əlçatanlıq sürəti: qırığın mövcudluğunu yoxlamaq O(k) müddətindədir, burada k təpənin qonşularının sayını göstərir.
• Uyğunluq: az qırığı olan seyrək qraflar üçün uyğundur.

Müqayisə:

Bitişiklik matrisi, daha çox təpə qırıq ilə birləşdirildiyi sıx qraflar üçün daha yaxşıdır, çünki qırıq məlumatlarına sürətli giriş təmin edir və reallaşdırmaq asandır.

Bitişiklik siyahıları, potensial təpə cütlərinin sayından az qırığı olan seyrək qraflar üçün üstünlük təşkil edir. Onlar yaddaşdan effektiv istifadə edir və qrafın keçidi əməliyyatlarını asanlaşdırır.