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

Oʻzbek	Рус	En
Tavsif
Uch	Вершина	vortex	Grafning elementi
Tugun	Узел	node	Uch tushunchasi bilan bir xil
Qirra	Ребро	edge	Ikki qoʻshni uchlarning bogʻlanishi
Yoy	Дуга	arc	Qirra bilan bir xil, lekin orgrafda emas
Aloqa, bogʻlanish, munosabat	Связь	link	Graf elementi (qirra yoki yoy)
Qoʻshnilik	Смежность	adjacent	Ikkita uch oʻrtasida aloqa mavjud boʻlganini bildiruvchi atama
Insidentlik	Инцидентность	incident on	Uchga nisbatan qirra haqida
Daraja	Степень	degree	Uchga tutashgan qirralarning soni

4-jadval. Graflar nazariyasining boshlang’ich terminologiyasi

6.2. 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 (1-rasmda ACD va ACDE sikllar)
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 (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 (_{ }) va bogʻlangan (_{ }).
Bogʻlanmagan graflarda qirralar bilan ulanmagan ikki yoki undan ortiq qismlar mavjud boʻladi. Ushbu qismlar bogʻlanish komponentlari deb ataladi.
Yuqorida keltirilgan graflarda _{ }da toʻrtta komponent, _{ }da uchta komponent, _{ }da 2 ta komponent mavjud, qolganlarida esa bittadan komponent mavjud. _{ } va _{ } graflari oʻrtasida _{ } grafini alohida ajratib koʻrsatish mumkin, chunki toʻrtinchi darajali graf uchun maksimal sondagi qirralarga ega.