Graflar bilan ishlovchi sodda algoritmlar

Graflar bilan ishlovchi sodda algoritmlar

Iskandar Xurramov

Graf

Graf -bu uchlar to‘pIami va har bsr uchlar juftliklarini bog‘lovchi qirralar kolleksiyasidir. Ta’rifda uchlarni nomlash shart emas, ammo foydalanlshda ularni nomlash kerak bo’1adi.

Graflar nazariyasi

Graflar nazariyasi - bu diskret matematikaning sohasi bo‘lib, ayniqsa geometrik yondashuv asosida obyektlarni o ‘rganishni bildiradi. Odatda, graflarni topologiyaga kiritish mumkin, lekin ular juda ko‘p fanlarda ham uchraydi. Graflar nazariyasining birinchi masalalari turli xil mantiqga oid masalalar bo’lgan.

Grafli tuzilish(tarmoq)

Grafda yo‘nalish-

Grafda yo‘nalish- bu qirralar bilan bog‘langan

ucblarning ketma-ketligi. Oddiy yo‘na!ish bu takrorlanmaydigan uchlardan iborat yo‘nalishdir. Sikl bu, boshi va oxiri mos tushuvchi kamida bitta qirradan iborat bo‘lgan yo‘nalish. Oddiy sikl bu takrorlanmaydigan qirra va uchga ega sikldir. Yo‘nalish uzunligi yoki sikli uning qirralar soniga teng bo‘ladi.

Daraxt

Daraxt bu atsiklik bog’langan grafdir. O‘zaro bo‘glanmagan daraxtlar o‘rmon deb ataladi. Bog‘langan grafning asos daraxti - bu berilgan grafning barcha uchlaridan iborat

qism graf bo‘Iib, yagona daraxt hisoblanadi. Grafning asos o‘rmoni bu asos daraxtlarining grafning komponentlarini bo‘glanishi.

Graf