Graflar uning turlari. Daraxtlar. Graflar va ularning turlari

6-mavzu: GRAFLAR VA DARAXTLAR


Graflar uning turlari. Daraxtlar.

1. 
   Graflar va ularning turlari
   

Ta’rif. Graf deb, shunday G₁(X,E) ikki to’plam juftligiga aytiladiki, bunda X-bo’sh bo’lmagan uchlar to’plami {x_1,,x₂, … , x_n} bo’lib, E ning elementlari esa X ning ikki elementli to’plam ostilaridir, ya’ni E={(x₁,x₂)}. Ushbu ikki elementli to’plamostilar qirralari deb ataladi.
Masalan, G = ({х,, х₂, х₃, х₄}, {(х,, х,), (х,, х₂), (х,, х₃), (х₂, х₃), (х₃, х₄)})
Murakkab bo’lmagan graflarni grafik sxemalar orqali ifodalash maqsadga muvofiqdir, u yerda uchlari nuqtalardan, qirralari esa ularni birlashtiruvchi chiziqlardan iboratdir. ¹
Ushbu sxemalarda chiziqlar uzunligi, eni va shakli hech qanday ahamiyatga ega emas.

Graflarga misollar²

Shunday qilib graf erkin konstruksiyalardir. Bunda ikki uchlari orasidagi bog’lanishning bo’lishi muhimdir, bir xilda ushbu bog’lanishni xarakteri muhimdir.
Agar x₁ va x₂lar qandaydir qirraga (x_i , x_j) ga tegishli bo’lsa, u holda ushbu qirra x_i va x_j “insindent” deyiladi, x_i va x_j lar esa qo’shni nuqtalar deyiladi. Agar qirra bir nuqtaga “insindent” bo’lsa, u sirtmoq deyiladi.
Hech qanday qirraga “insindent” bo’lmagan uch ajratilgan uch deyiladi. Agar grafda shunday uchlar bo’lsaki ular ikki va undan ko’p uchlar bilan birlashtirilgan bo’lsa bunday graf multigraf deyiladi. Ushbu uchga tegishli bo’lgan qirralar soni uchning darajasini belgilaydi. 2.6rasmda ko’rsatilgan x₂ uch 6 darajaga ega, chunki unga α₁, α₂, α₃, α₄, α_5, α_6, α₇ , qirralar “insindent”dir, x₁ uchning darajasi 3, x₄ ning darajasi esa 1.

2.6-rasm

Agar graf sirtmoqsiz yoki qirralari karrali bo’lmasa, bunda graf oddiy graf deyiladi. Graf kvadrat jadval shaklida bo’lishi mumkin.

Graf matritsasi
Matritsa ustunlari va qatorlari graf uchlarini nomerlariga mos keladi, uning elementi c_n x₁ va x_j birlashtiruvchi qirralar sonidir. 2.6.graf uchun matritsa quyidagi ko’rinishga egadir.