3-rasm Daraxt - bu bogʻlangan asiklik graf
Graflar nazariyasining asosiy tushunchalari
Grafdagi marshrut - bu har bir uch (oxirgisidan tashqari)
ketma-ketlikdagi
keyingi uchga qirra bilan bogʻlangan uchlarning cheklangan ketma-ketligi.
Yoʻl - bu qirralarning takrorlanmagan yoʻlidir.
Oddiy zanjir - bu uchlarni takrorlamaydigan marshrut (bu
oddiy zanjirda
takrorlanadigan qirralarning yoʻqligini anglatadi) .
Orgrafdagi
yoʻnaltirilgan marshrut (yoki yoʻl) - bu har bir element oldingi va
keyingi qismga tushadigan uchlar va yoylarning cheklangan ketma-ketligi.
Birinchi va oxirgi uchlar bir-biriga toʻgʻri keladigan zanjirlar sikl deb ataladi.
Yoʻlning (yoki siklning) uzunligi uni tashkil etuvchi qirralarning soni deyiladi.
Agar uning qirralari takrorlanmasa,
yoʻl (yoki sikl) oddiy deb nomlanadi; agar u
sodda boʻlsa va undagi tepaliklar takrorlanmasa u
elementar deb nomlanadi.
Graf turlari.
Yoʻnaltirilgan graf - (qisqacha orgraf) - qirralari yoʻnaltirilgan graf.
Yoʻnaltirilmagan graf - uchlar juftligi tartiblanmagan graf.
Bogʻlangan graf - bu har qanday uch juftligi oʻrtasida kamida bitta yoʻl mavjud
boʻlgan graf.
Daraxt - bu bogʻlangan asiklik grafik, ya‘ni sikllar yoʻq va tepalik juftligi orasida
bitta yoʻl bor. Kirishning nol darajasiga ega boʻlgan uch
daraxtning ildizi, chiqish
nol darajaga
ega tugunlar esa barglar deb nomlanadi.
Bogʻlangan va bogʻlanmagan graflar. koʻrsatilganlar
graflarni ikki guruhga
boʻlish mumkin (kesilgan chiziq bilan ajratilgan): bogʻlanmagan (G
1
-G
5
) va
bogʻlangan (G
6
-G
11
).
Bogʻlanmagan graflarda qirralar bilan ulanmagan ikki yoki undan ortiq qismlar
mavjud boʻladi. Ushbu qismlar bogʻlanish komponentlari deb ataladi.
Yuqorida keltirilgan graflarda G
1
da toʻrtta komponent, G
2
da uchta komponent,
G
3
, G
4
va G
5
da 2
ta komponent mavjud, qolganlarida
esa bittadan komponent
mavjud. G
6
va G
11
graflari oʻrtasida G
11
grafini alohida ajratib koʻrsatish mumkin,
chunki toʻrtinchi darajali graf uchun maksimal sondagi qirralarga ega.
