6-ma’ruza. Graflar nazariyasi elementlari va o'tish algoritmlari

Daraxtlar va zanjirlar. Bogʻlangan graflarda minimal miqdordagi qirralar mavjud boʻlsa, (_{ }) ular daraxtlar sinfini tashkil etadi. Yuqorida rasmda bu _{ }va _{ } 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 (_{ } oʻzgaruvchan ketma-ketligi. Bu yerda _{ } va _{   } qirraning oxirlari hisoblanadi. Ushbu yozuvni qisqacha shaklda quyidagicha yozishimiz mumkin: _{ } yoki _{ }. Umumiy turdagi oddiy zanjirdan farqli oʻlaroq, u takrorlanadigan uchlarni oʻz ichiga olishi mumkin. Masalan, quyida keltirilgan graflarda (_{ } – oddiy zanjir, (_{ } – zanjir.



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 _{ } 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.
R
egulyar graflar. 16-rasmdagi _{ } 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.