9-mavzu: Graflar nazariyasining asosiy tushunchalari. Graflarning ba’zi turlari. Graflarning berilish usullari. Qo`shnilik va insidentlik matritsalari. Graflarning izomorfligi. Qoshnilik. Insidentlik. Uchning darajasi

Psevdograf. Multigraf
Shunday graflar mavjudki, ularning uchlari bir nechta qirralar bilan bog`langan bo`ladi. Bunday qirralar karrali qirralar deyiladi. Biror uchini o`zi bilan bog`laydigan qirraga ilmoq (tugun) deyiladi.

Agar uchdan hech qanday qirra chiqmasa, bunday uch yakkalangan uch deyiladi yoki hech qanday qirra (yoy) bilan bog‘lanmagan uch yakkalangan uch deb ataladi.

Faqat yakkalangan uchlardan tashkil topgan graf nolgraf yoki bo‘sh graf deb ataladi yoki bitta ham qirrasi bo`lmagan graf nol deyiladi.

Uchlari soni ga teng bo‘lgan bo‘sh grafni yoki kabi belgilash qabul qilingan.

Ham ilmoq, ham karrali qirraga ega bo`lgan grafga psevdograf deyiladi

(2-rasm)

2-rasm
Yuqorida keltirilgan grafda 1 uch 2 ta qirrali ilmoqqa, 2 uch 1 ta ilmoqqa ega, 2 va 3 uchlar 2 ta karrali qirralar bilan bog’langan.

Ilmoqlarsiz psevdograf multigraf deyiladi.

Multigrafga misol 3-rasmda keltirilgan.

3-rasm

Agar grafning uchlari va qirralari to`plamida refleksivlik va simmetriklik хossalarini qanoatlantiruvchi binar munosabat mavjud bo`lsa, bunday graf tolerant graf deyiladi.

            

4- rasm

 Tolerant graf                                   Oriyentirlanmagan graf

      

5- rasm

 Tolerant graf                                    Oriyentirlanmagan graf

Qism graf
Agar G grafdan bitta yoki bir nechta uchlar olib tashlansa, u holda bu uchlardan chiquvchi qirralar ham yo`qoladi qolgan uchlar va qirralar berilgan G grafning qism grafi bo`lgan G^/ grafni tashkil qiladi. Ma’lumki, har qanday graf o`zining qism grafiga ega bo`ladi.


7a- rasm
Bu 4 a-rasmdagi grafdan 1- uchni olib tashlaymiz. Undan {1,2}, {1,3}, {1,4}, {1,7} qirralar ham yo`qoladi natijada 4 b-rasmdagi graf paydo bo`ladi.

7b -rasm