| açar sözlər • Çəkili qraf • Çəki matrisi

| 20. Qraf məsələləri • İstiqaməti olan tilə nə deyilir? • Hər bir tilinin istiqaməti olan qraf necə adlanır?

Bir çox praktik məsələlərdə (məsələn, iki məntəqə arasında ən qısa yolun tapılmasında) yalnız təpələr arasında əlaqələr deyil, bu əlaqələrə uyğun ədədlər (əmsallar) önəmli olur. Məsələn, bu ədədlər şəhərlər arasındakı məsafə, yaxud yolpulu ola bilər. Qraflar nəzəriyyəsində hər bir tilə uyğun ədədə (əmsala) onun çəkisi, belə qrafa isə çəkili qraf deyilir.

1 | Verilmiş A, B, C və D məntəqələrinin hər birindən qalan məntəqələrə yollar var və onların uzunluqları məlumdur: AB = 7, AC=5, AD=4, BC =6, BD=1, CD=8. Bu məntəqələrin birindən başlayıb onların hər birində yalnız bir dəfə olmaqla başlanğıc məntəqəyə qayıtmaq lazımdır. Hansı marşrut üzrə hərəkət edilməlidir ki, keçilən yol ən qısa olsun? Həlli: Uyğun məntəqələrin və onlar arasındakı yolların sxemini belə bir çəkili qraf şəklində göstərmək olar. Göründüyü kimi, burada 6 mümkün dövrə var: ABCDA, ACBDA, ABDCA, ACDBA, ADBCA, ADCBA. Onların uzunluqları uyğun olaraq belədir: 25, 16, 21, 21, 16, 25. Beləliklə, ən qısa marşrutlar ACBDA və ADBCA olacaq.

Çəkili qraflarda qonşuluq matrisinin əvəzinə çəki matrisindən istifadə olunur. Çəki matrisinin xanalarında tillərin çəkisi göstərilir və əgər iki təpə arasında til yoxdursa, uyğun xana boş saxlanılır. Şəkildə yolların uzunluğu qeyd olunmuş sxem, ona uyğun qraf və çəki matrisi göstərilib.