- Grafning qaysidir tuguni o’z-o’ziga zanjir bilan bog’lansa, bu sikl (yoki halqali) deb ataladi.
- Halqasiz graf daraxt deyiladi.
- Barcha mumkin bo’lgan yoylari berilgan graf to’liq deyiladi (masalan, n tuguni bo’lgan grafda n(n-1)/2 ta yoy mavjud bo’ladi).
Asosiy tushunchalar - Amaliy masalalarni yechishda odatda har bir yoy ma’lum vazn (og’irlik)ga (yoki uzunlikka) ega bo’lgan vaznli graflar (Weighted graph) qo’llaniladi. Bunday graflar tarmoq (to’r) deb ataladi.
Grafni tavsiflash - Graflarni tavsiflash uchun odatda ikki turdagi matritsalar qo’llaniladi - qo’shnilik matritsasi (vaznga ega bo’lmagan graflar uchun) va vaznli matritsa (vaznli graflar uchun).
- N ta tugunli grafning qo’shnilik matritsasi (adjacency matrix)– bu N ga N o’lchamli matritsa hisoblanib, uning har bir (i,j) indeksli elementi i tugundan j tugunga yoy mavjud yoki mavjud emasligini ko’rsatuvchi mantiqiy qiymatlardan iborat bo’ladi.
Grafni tavsiflash - Vaznli graflar uchun tugunlar orasida bog’lanish bor yoki yo’qligini oddiy ko’rsatish yetarli emas. Bunday graflarni qayta ishlash uchun xotirada har bir yoyning vazni saqlash talab etiladi, masalan, biletning narxi yoki yo’l uzunligini. Buning uchun vazn matritsasi qo’llaniladi.
- N ta tugundan iborat grafning vazn matritsasi – bu N ga N o’lchamli matritsa bo’lib, (i,j) indeksli har bir elementi i tugundan j tugungacha bo’lgan yoylarning “vazni”ga teng bo’lgan matritsa hisoblanadi.
- Masala. Tekislikda davlat xaritasi berilgan, unda aniq koordinataga ega n ta shahar mavjud. Barcha shaharlarni uzunligi eng qisqa bo’lgan telefon tarmog’i bilan bog’lash kerak.
- Shaharlarni tugun (nuqta)lar orqali ifodalab olamiz. Telefon tarmog’i to’g’ridan to’g’ri emas, balki faqat telefon stantsiyalaridan tarqatiladi. Tarmoqda tsikl (xalqa) bo’lmaydi, umumiy uzunligi minimal bo’lgan qancha tarmoq talab etilishini aniqlash uchun telefon stantsiyasi o’zidan oldingilar bilan bog’langan deb faraz qilamiz.
- Graflar nazariyasi nuqtai nazaridan bu masala quyidagicha bo’ladi:
- n ta tugunli graf berilgan; yoylar uzunligi {dij}, i,j=1..n matritsada berilgan. Grafning barcha tugunlarini bog’lash mumkin bo’lgan yoylar to’plamini (u yoyilgan daraxt -spanning tree deyiladi) va ularning eng minimal uzunligini aniqlang.
Do'stlaringiz bilan baham: |
