19-ma`ruza. Ma’lumotlarning tarmoqli tuzilmalari. Graf tushunchasi va uning ko’rinishlari

19-MA`RUZA. MA’LUMOTLARNING TARMOQLI TUZILMALARI. GRAF TUSHUNCHASI VA UNING KO’RINISHLARI.
Reja:
1. Graflar nazariyasiga kirish asosiy tushunchalar;
2. Graflarni tavsiflash: qo’shnilik matritsasi;
3. Intsidentlik matritsasi va qo’shnilik ro’yxati;
4. Adabiyotlar ro’yxati 


Kalit so’zlari: graf, tugun (cho’qqi), yoy (qirra), yo’nalitirilgan graf, yo’naltirilmagan graf, vaznli graf, vaznsiz graf, aralash graf, zis graf, tarqoq (siyrak) graf, grafni tasvirlash, qo’shnilik matritsasi, intsidentlik matritsasi, qo’shnilik ro’yxati. 
1. Graflar nazariyasiga kirish: asosiy tushunchalar.
Tugunlar va ular orasidagi bog’lanishlar to’plami graf deyiladi. Har bir tugun cho’qqi, har bir bog’lanish esa qirra (yoy) deb ataladi. Har bir yoy ikkita tugunni bog’laydi.
Graflar odatda yo’naltirilgan va yo’naltirilmagan kabi turlarga ajratiladi. Yo’naltirilgan graflarda bitta tugundan boshqa tugungacha faqat ko’rsatilgan yo’nalishda harakatlanish mumkin. Masalan, 1-rasmda tasvirlangan grafda v0 tugundan v1 tugunga tomon harakatlanish mumkin, v1 dan v0 tomonga harakatlanish mumkin emas. Yo’naltirilmagan graflarda esa ikkila tomonga ham harakatlanish mumkin bo’ladi. Masalan, 2-rasmda tasvirlangan grafda 1 tugundan 2 tugunga tomon va aksincha harakat tashkil etish mumkin bo’ladi.

1-rasm. Yo’naltirilgan graf

2-rasm. Yo’naltirilmagan graf
Shunday graflar ham mavjudki, ularda yo’naltrilgan, shuningdek yo’naltirilmagan bog’lovchi yoylar bo’lishi mumkin. Bunday graflar aralash graf deyiladi (3-rasm).

3-rasm. Aralash graf
Bulardan tashqari graflar vaznli va vaznsiz graflarga ajratiladi. Har bir yoyga mos ravishda qandaydir sonli qiymatlar – og’irlik qo’yilgan graflar vaznli graf deb ataladi (4-rasm). Agar yeyolarga 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 (4-rasm). Agar grafda hech bo’lmaganda birorta tugunlar juftligi bog’lanmagan bo’lsa (ular orasida yo’l bo’lmasa), bunday graflar bog’lanmagan deb ataladi (5-rasm)

4-rasm. Vaznli bog’langan yo’naltirilgan graf

5-rasm. Bog’lanmagan graf.
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 (6-rasm).

6-rasm. Zich grafga misol
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. Bunga misol 7-rasmda tasvirlangan.

7-rasm. Xalqali graf