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

19-rasm. Graflarning vizual namoyish qilinishi 
Odatda zanjir mustaqil graf sifatida emas, balki ba’zi bir graflarning bir qismi sifatida 
qaraladi. Zanjirning uzunligi - uni tashkil etuvchi qirralarning soni. Oddiy zanjirning uzunligi oʻz 
ichiga olgan graf uchlari sonidan, umumiy zanjirning uzunligi esa ushbu graf qirralarining sonidan 
oshmasligi aniq. 
Graflar nazariyasida zanjir tushunchasi keng qoʻllaniladi. Masalan, bogʻlangan grafni har 
qanday uchlar juftligi kamida bitta zanjir bilan bogʻlangan graf sifatida belgilash mumkin. 
Sikllar. Sikl (oddiy sikl) - bu yopiq zanjir (oddiy zanjir). Oddiy siklga 
𝐺
8
grafi misol boʻla 
oladi. Oddiy siklni ifodalovchi graf 
𝐶
𝑛
bilan belgilanadi. Zanjirlarda boʻlgani kabi, sikllarni ba’zi 
bir graflarning qismlari sifatida koʻrib chiqish qiziq. 
Regulyar graflar. 16-rasmdagi 
𝐺
1
, 𝐺
3
, 𝐺
8
, 𝐺
11
graflari ularning har birida barcha uchlar bir 
xil darajaga ega ekanligi bilan ajralib turadi. Bunday graflar regulyar yoki bir jinsli deb nomlanadi. 
20-rasmda uchinchi, toʻrtinchi va beshinchi darajadagi muntazam sakkizta uchli graflar 
koʻrsatilgan. 
20-rasm. Regulyar graflar 
Uchinchi darajali graflar kubik deb nomlanganiga e’tibor bering. –rasmdagi 
𝐺
11
va –
rasmdagi 
𝐺
1
. Shubhasiz, d darajali regulyar grafdagi qirralarning soni 
𝑚 =
1
2
𝑛𝑑 ga teng. Bundan 

---

kelib chiqadiki, toq sonli uchlar uchun regulyar graf faqat juft darajaga, toq daraja uchun esa faqat 
uchlar soni boʻlishi mumkin. Shuning uchun har qanday kubik graf uchlarning juft soniga ega. 
6.2. Grafni tasvirlash usullari 
Grafni tasvirlash uchun bir nechta usullardan foydalaniladi. Graflardan oʻtish uchun siz 
oʻzingizning muammoingizni eng samarali hal qiladiganlardan foydalanishingiz kerak. Koʻpincha, 
tanlov qoʻshnilik matritsasi va qoʻshnilik roʻyxati oʻrtasida boʻladi (quyidagi jadval ikkala 
yondashuvning samaradorligini taqqoslaydi). Shu bilan birga, oʻrnatilgan C-massivga tayanib, 
oʻzingizning ma’lumotlar tuzilmalaringizni modellashtirishingiz va STD-da mavjud boʻlgan turli 
xil konteynerlardan foydalanishingiz mumkin.