Mühazirə 14. Qraflar və onlar haqqında ümumi məlumatlar Əsas anlayışlar

Mühazirə 14. Qraflar və onlar haqqında ümumi məlumatlar


1.Əsas anlayışlar. Qraf anlayışı müasir riyaziyyatın əsas anlayışlarından biridir və sonlu həndəsəyə aid oluna bilər.
Tərif 1. Tutaq ki, çoxluğu və elementləri çoxluğunun elementləri cütlüyündən ibarət olan çoxluğu verilmişdir. cütlüyünə qraf deyilir.
çoxluğu qrafın daşıyıcısı və ya qrafın təpələr çoxluğu adlanır. çoxluğu qrafın siqnaturası və ya tillər çoxluğu adlanır.
Təyindən göründüyü kimi -dir. çoxluğunun elementlərini kimi yazaq. Burada . tili və təpəsini birləşdirir.
Əgər qrafın tillərinə istiqamətlər yazılırsa, belə qrafa orqraf və ya oriyentasiyalı qraf deyilir. Oriyentasiyalı qrafda tillərə qövs də deyirlər.
Nümunə 1. Tutaq ki,
,
.
Onda qrafdır.
Əgər və çoxluqları sonlu olarsa, onda qrafa sonlu qraf deyilir.
Əgər qrafda iki təpəni birləşdirən bir neçə til olarsa, belə qrafa multiqraf deyilir.
Şəkil 1, şəkil 2 və şəkil 3-də qrafın, multiqrafın və orqrafın həndəsi təsvirləri verilir.
Tutaq ki, və qrafının ixtiyari təpə nöqtələridir.
Tərif 2. qrafının

tillər sistemi və təpələrini birləşdirən yol və ya marşrut adlanır, harada ki, və .
yoluna aid olan istənilən til üçün deyilir ki, bu
tildən keçir. Əgər təpəsi yolunun hər hansı bir tilinə aid olarsa, onda da deyilir ki, yolu təpəsindən keçir.

Şəkil 1. Şəkil 2. Şəkil 3.

Tərif 3. Əgər yolu üçün olarsa, onda ona dövrə deyilir. Xüsusi halda dövrəsinə ilgək deyilir.
Tərif 4. Əgər qrafında istənilən iki müxtəlif təpəni birləşdirən yol mövcuddursa, onda qraf rabitəli qraf adlanır.
Tərifdən göründüyü kimi rabitəli qraf izolə edilmiş təpələrə malik olmur.
Qraflarda tilləri təpələrsiz də adlandırmaq olar, yəni çoxluğunu kimi də təsvir etmək olar. Bu halda -nin elementləri üçün insidiyent və koinsidiyent anlayışları istifadə olunur.
tili təpəsi ilə birləşərsə, onda tili təpəsi ilə insidiyent olan til, təpəsi isə tili ilə konsidiyent olan təpə adlanır.
və təpələri tillə birləşirsə, onda onlara qonşu təpələr deyilir. təpəsi ilə qonşu olan təpələr çoxluğuna təpəsinin ətrafı deyilir və ilə işarə olunur.
və tilləri eyni bir təpə ilə insidiyent olarsa, onda
onlara qonşu tillər deyilir.
Çəkili qraf anlayışı ilə tanış olaq. qrafının hər bir təpəsinə çoxluğundan olan əmsalı qarşı qoyaq. Onda qraf çəkili təpəyə malik qraf adlanır. qrafının istənilən tilinə çoxluğundan bir əmsalı qarşı qoyaq. Onda qraf çəkili tilə malik qraf adlanır. Təpələri və (və ya) tilləri çəkili olan qraf çəkili qraf adlanır.
Qrafların verilməsi üçün qonşuluq və insidiyentlik matrisləri istifadə oluna bilər.
Tutaq ki, qrafının təpələr çoxluğu olan çoxluğu sayda elementdən ibarətdir. Çəkili olmayan qraflarda qonşuluq matrisinin elementləri aşağıdakı kimi təyin olunur:

Çəkili qraf halında isə

Tutaq ki, qraf sayda təpəyə və sayda tilə malikdir, yəni , . qrafının insidiyentlik matrisinin elementləri aşağıdakı kimi təyin olunur: