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 yol pulu 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.
Mәsәlә
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?
Sözlük
• Çəkili qrafÇə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.