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

3. Intsidentlik matritsasi va qo’shnilik ro’yxati.
Intsidentlik – faqat tugunlar va yoylar munosabatida qo’llaniladigan tushuncha. Agar, v1, v2 - tugunlar, e=(v1, v2) esa ularni tutashtiruvchi yoy bo’lsa, u holda v1 tugun va e yoy intsident, v2 tugun va e yoy ham intsident bo’ladi. Ikkita tugun (yoki ikkita yoy) intsident bo’la olmaydi. Masalan, 7-rasmdagi 1 tugun 1-2 yoyga intsident.
Qo’shnilik – faqat ikkita yoy yoki faqat ikkita tugunga nisbatan ishlatiladigan tushuncha: ikkita yoy bitta tugunga intsident bo’lsa, ushbu yoylar qo’shni deb ataladi; shuningdek, ikkita tugun bitta yoyga intsident bo’lsa, ushbu tugunlar qo’shni deyiladi. Masalan, 7-rasmdagi bitta yoyga intsident bo’lgan 1 va 2 tugunlar qo’shni,
Marshrut – bu graf bo’yicha berilgan ketma-ketlikdagi tugunlar dan graf bo’yicha o’tish. Agar tugunlar ketma-ketligining boshlang’ich tuguni v0 va oxiri vk ustma-ust tushsa, ya’ni v0=vk, u holda marshrut yopiq (9-rasm), aks holda marshrut ochiq (8-rasm) deyiladi. 

8-rasm. Ochiq marshrut: tugunlar 2-4-1-2-3-4-1

9-rasm. Yopiq marshrut: tugunlar 2-3-5-4-3-2
Zanjir – grafning ixtiyoriy yoyi ko’pi bilan bir marta kiritilgan marshrut. Agar bunday marshrutning barcha tugunlari takrorlanmasa, u holda zanjir oddiy (10-rasm) bo’ladi. 10-rasmda tasvirlangan zanjirda 2 va 4 tugunlari zanjir oxirlari deyiladi. Marshrutning boshlang’ich va oxirgi nuqtalari (marshrut oxirlari) bitta tugunda bo’lgan zanjir tsikl deyiladi.
11-rasmdagi 2 tuguni tsiklik marshrutning boshlang’ich va oxirgi tuguni hisoblanadi.

10-rasm. Ochiq zanjir: 2-5-1-2-4 tugunlar

11-rasm. Yopiq zanjir: 2-4-1-2-3-5-2 tugunlar

2. Graflarni tavsiflash. Qo’shnilik matritsasi.
Grafning qo’shnilik matritsasi – bu vaznsiz graf uchun har bir elementi 0 yoki 1 qiymatlardan birini qabul qiluvchi kvadrat matritsa bo’lib, grafni matritsa ko’rinishda ifodalash uchun qo’llaniladi. 1 va 0 qiymatlar tugunlar orasida yoy mavjud yoki mavjud emasligini anglatadi. Masalan, 12-rasmda tasvirlangan vaznsiz yo’naltirilmagan grafning 1 va 2 tugunlari orasida yoy mavjud, shuning uchun matritsaning birinchi satr va ikkinchi ustuni kesishmasi hamda ikkinchi satr va birinchi ustuni kesishmasida 1 qiymati qo’yiladi. 13-rasmdagi vaznsiz yo’naltirilgan grafda esa, 1 tugundan 2 tugunga o’tish yo’li (yoyi) bo’lgani uchun qo’shnilik matritsasining birinchi satr va ikkinchi ustuni kesishmasida 1 qiymati bo’ladi, lekin ikkinchi satr va birinchi ustun kesishmasida esa 0 qiymati qo’yiladi, chunki 2 tugundan 1 tugunga to’g’ridan to’g’ri o’tish yo’li mavjud emas. Agar graf vaznli bo’lsa, qo’shnilik matritsasining elementlari tugunlarni bog’lovchi yoylar vazniga mos qiymatlar bilan to’ldiriladi (14-rasm).

12-rasm. Vaznsiz yo’naltirilmagan graf
12-rasmda tasivrlangan graf uchun qo’shnilik matritsasi quyidagi ko’rinishda bo’ladi:

№ tugunlar