1-ma’ruza. Graflar nazariyasi elementlari va o'tish algoritmlari. Grafni aniqlanishi orientirlangan va orientirlanmagan graflar. Lokal daraja. Yo`l va sikl. Grafni mashina xotirasida ifodalash usullari

Graf turlari. Yoʻnaltirilgan graf - (qisqacha orgraf) - qirralari yoʻnaltirilgan graf (4-rasm 
pastga qarang). 
Yoʻnaltirilmagan graf - uchlar juftligi tartiblanmagan graf (22-rasm) 
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 (18-rasm). Kirishning nol darajasiga ega boʻlgan uch daraxtning ildizi, chiqish nol darajaga 
ega tugunlar esa barglar deb nomlanadi. 
Bogʻlangan va bogʻlanmagan graflar. 16-rasmda koʻrsatilganlar graflarni ikki guruhga 
boʻlish mumkin (kesilgan chiziq bilan ajratilgan): bogʻlanmagan (
𝐺
1
− 𝐺
5
) va bogʻlangan (
𝐺
6
−
𝐺
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 
𝐺
1
da toʻrtta komponent, 
𝐺
2
da uchta komponent, 
𝐺
3
, 𝐺
4
𝑣𝑎 𝐺
5
da 2 ta komponent mavjud, qolganlarida esa bittadan komponent mavjud. 
𝐺
6
va 
𝐺
11
graflari oʻrtasida 
𝐺
11
grafini alohida ajratib koʻrsatish mumkin, chunki toʻrtinchi darajali graf 
uchun maksimal sondagi qirralarga ega.

---

Daraxtlar va zanjirlar. Bogʻlangan graflarda minimal miqdordagi qirralar mavjud boʻlsa, 
(|
𝐸𝐺| = 𝑛 − 1) ular daraxtlar sinfini tashkil etadi. Yuqorida rasmda bu 𝐺
6
va 
𝐺
7
daraxtga toʻgʻri 
keladi. Daraxtlar haqida keyingi mavzuda batafsil toʻxtalamiz. Bu yerda biz 16-rasmda
P4 sifatida 
belgilangan G7 grafini qayd etamiz, bu daraxtning alohida holati va oddiy zanjir deb ataladi. 
Umuman olganda zanjir – uchlar va qirralarning (
𝑣
0
, 𝑒
1
, 𝑣
1
, 𝑒
2
, 𝑣
2
, … , 𝑣
𝑘−1
, 𝑒
𝑘
, 𝑣
𝑘
) 
oʻzgaruvchan ketma-ketligi. Bu yerda 
𝑣
𝑖−1
va 
𝑣
𝑖
𝑒
𝑖
qirraning oxirlari hisoblanadi. Ushbu yozuvni 
qisqacha shaklda quyidagicha yozishimiz mumkin: 
(𝑣
0
, 𝑣
1
, … , 𝑣
𝑘−1
, 𝑣
𝑘
) yoki (𝑒
1
, 𝑒
2
, … , 𝑒
𝑘−1
, 𝑒
𝑘
). 
Umumiy turdagi oddiy zanjirdan farqli oʻlaroq, u takrorlanadigan uchlarni oʻz ichiga olishi 
mumkin. Masalan, quyida keltirilgan graflarda (
𝑣
1
, 𝑣
2
, 𝑣
5
, 𝑣
4
, 𝑣
3
) – oddiy zanjir, 
(
𝑣
1
, 𝑣
2
, 𝑣
5
, 𝑣
4
, 𝑣
1
, 𝑣
3
) – zanjir.