Mustaqil ish Ma’lumotlar tuzilmasi va algoritmlar

Mustaqil ish Ma’lumotlar tuzilmasi va algoritmlar

712_21-guruh talabasi E.Rivojiddinov

Mavzu:Graflarni tasvirlash usullari. Eng qisqa yo’lni aniqlash algoritmi.

• Daraxt (tree) aslida graph’ning ma’lum bir cheklov va qoidalarga asoslangan varianti xolos. Qisqacha aytganda, istalgan tree bu graph, ammo istalgan graph tree emas.

Graf – bu tugunlar va qirralar (tugunlar juftligini birlashtiruvchi) to’plamidan iborat bo’lgan abstrakt matematik ob’ektdir.

• Graf — obyektlar toʻplamining grafik koʻrinishi boʻlib, unda baʼzi juft obyektlar linklar orqali bogʻlanadi. Oʻzaro bogʻlangan obyektlar uchlari deb ataladigan nuqtalar bilan ifodalanadi, uchlarini bogʻlaydigan boʻgʻinlar esa qirralar deb nomlanadi

Rasmiy ravishda, grafik - bu juftlik to'plami (V, E), bu erda V - tepaliklar to'plami va E - qirralarning to'plami, tepalik juftlarini bir-biriga bog'lab turadi. Quyidagi grafaga qarang

Yuqoridagi grafikada,

V = {a, b, c, d, e}

E = {ab, ac, bd, cd, de}

Graflar vaznli va vaznsiz graflarga ajratiladi. Har bir yoyga mos ravishda qandaydir sonli qiymatlar – og’irlik qo’yilgan graflar vaznli graf deb ataladi. Agar yoylarga hech qanday qimatlar qo’yilmagan bo’lsa, bunday graflar vaznsiz graf deyiladi. Umuman olganda graflar nomlari ularning yo’naltirilganligi yoki yo’naltirilmaganligi, hamda ularning vaznli yoki vaznsiz ekanligini anglatadi.

Agar grafning ixtiyoriy ikkita tuguni orasida hech bo’lmaganda bitta yo’l (bog’lovchi yoy) mavjud bo’lsa, bunday graflar bog’langan deyiladi. Agar grafda hech bo’lmaganda birorta tugunlar juftligi bog’lanmagan bo’lsa (ular orasida yo’l bo’lmasa), bunday graflar bog’lanmagan deb ataladi.

• Agar grafning ixtiyoriy ikkita tuguni orasida hech bo’lmaganda bitta yo’l (bog’lovchi yoy) mavjud bo’lsa, bunday graflar bog’langan deyiladi. Agar grafda hech bo’lmaganda birorta tugunlar juftligi bog’lanmagan bo’lsa (ular orasida yo’l bo’lmasa), bunday graflar bog’lanmagan deb ataladi.

Grafning yoylari soni maksimal (mumkin bo’lgan yoylar) soniga yaqin bo’lsa (ya’ni, grafning har bir tuguni ixtiyoriy boshqa tuguni bilan yoy orqali bog’langan bo’lsa), bunday graflar zich (to’liq) graf deb ataladi.

• Grafning yoylari soni maksimal (mumkin bo’lgan yoylar) soniga yaqin bo’lsa (ya’ni, grafning har bir tuguni ixtiyoriy boshqa tuguni bilan yoy orqali bog’langan bo’lsa), bunday graflar zich (to’liq) graf deb ataladi.

Yuqoridagilarga teskari xususiyatlarga ega bo’lgan graflar, ya’ni yoylar soni kam bo’lgan graflar tarqoq (yoki siyrak) graf deb ataladi.

• Yuqoridagilarga teskari xususiyatlarga ega bo’lgan graflar, ya’ni yoylar soni kam bo’lgan graflar tarqoq (yoki siyrak) graf deb ataladi.
• Ustma –ust tushuvchi tugunlarni bog’lovchi yoy xalqa (petlya) deb ataladi. Boshqacha qilib aytganda xalqa yoy bitta tugundan boshlanib, shu tugunning o’zida yakunlanadi.

Graph qachon ishlatiladi?

• Graph qachon ishlatiladi?
• Real hayotdagi juda ko’p tizimlar graph’larga asoslangan bo’ladi. Masalan Facebook ijtimoiy tarmog’idagi do’stlik aloqalari undirected graph’ga asoslangan. Siz Facebookdagi do’stingiz uchun ham do’st hisoblanasiz.
• Twitter va Instagram tarmoqlaridagi do’stlik (yoki kuzatish – follow) esa bir tomonlama bog’lanishga ega. Siz kuzatadigan odamlar sizni kuzatmasligi mumkin. Demak Twitter va Instagramdagi following – directed graph hisoblanadi.

E’tiboringiz uchun raxmat