Nizomiy nomidagi toshkent davlat pedagogika universiteti tabiiy fanlar fakulteti

Graf turlari:

Avvalo grafning abstrakt matematik tushuncha sifatidagi ta’rifini keltiramiz. Ixtiyoriy nuqtalarning qandaydir usulda bog’lanishidan tashkil topgan to’plamni qaraymiz. Ushbu to’plamni uchlar to’plami va uning elementlarini esa uchlar deb ataymiz. to’plamning va elementlaridan tuzilgan ko’rinishidagi barcha juftliklar to’plamini ( to’plamning o’z-o’ziga Dekrat ko’paytmasini) deb belgilaymiz.
Graf deb shunday juftlikga aytiladiki, bu erda va ko’rinishidagi juftliklar bo’lib, to’plamning elementlaridan tuzilgandir.
Grafni lotin alifbosining harfi bilan belgilaymiz.
Grafga ta’rif berishda boshqacha yondoshuvdan ham foydalanish mumkin.
graf deb bir qancha uchlar to’plamining birlashmasiga yoki qaysi uchlar bog’langanligini ko’rsatuvchi juftliklarga aytiladi.
Mos ravishda grafning geometrik tasvirida aniq har bir juftlik grafning qirrasi deyiladi, va uchlar esa qirraning oxirlari deyiladi. Qirraning ta’rifida uning oxirgi ikki uchining joylashish tartibi e’toborga olinishi ham, olinmasligi ham mumkin. Agar bunday tartib mavjud bo’lmasa, ya’ni deyish mumkin bo’lsa, u holda ni yo’naltirilmagan qirra deb ataladi. Agar bunday tartib mavjud bo’lsa, u holda qirra yo’naltirilgan qirra deyiladi. Yo’naltirilgan qirrada boshlang’ich uch, oxirgi uch deb hisoblanadi. Shuningdek qirrani uchdan chiquvchi va uchga boruvchi qirra deyiladi. Qirra yo’naltirilgan bo’lgan holda ham, yo’naltirilmagan holda ham qirra va uchlarga intsidient deb ataladi.
Grafni yo’naltirilmagan deyiladi, agar uning barcha qirralari yo’naltirilmagan bo’lsa (1.1.a–rasm), yo’naltirilgan deyiladi agar barcha qirralari yo’naltiriligan bo’lsa (1.1.b– rasm).

1.1.a–rasm 1.1.b–rasm.

Ham yo’naltirilgan, ham yo’naltirilmagan qirralarga ega bo’lgan graf aralash graf deyiladi. Misol sifatida, shaxarning xaritasini graf sifatida olsak, unda ko’chalarni qirra deb, chorrahalarni esa uchlar sifatida olish mumkin. Bunda faqat bir tomonlama harakat mavjud ko’chalarni yo’nalishga ega qirra deb olsak, u holda ikki tomonlama harakat mavjud ko’chalarni hech qanday yo’nalish orqali belgilab bo’lmaydi.
Hech bir qirraga intsidient bo’lmagan uch yakkalangan uch deyiladi. Agar grafning ikkita uchini tutashtiruvchi qirra bor bo’lsa, u holda bunday uchlar qo’shni uchlar deyiladi, aks holda esa qo’shni bo’lmagan uchlar deyiladi.
Istalgan ikkita uchi qo’shni bo’lgan sirtmoqsiz va karrali qirralarsiz, yo’naltirilmagan graf to’la graf deyiladi (1.4-rasm). Uchlari soni ga teng to’la graf bilan belgilanadi. Ravshanki, grafning qirralar soni ta bo’ladi.
Grafni tekislikda tasvirlaganda qirralarning barcha kesishish nuqtalari uchlardan iborat bo’lsa bunday graf tekis graf deyiladi (1.5–rasm).

1.4–rasm 1.5–rasm

Ba’zan graf undagi elementlar soniga qarab, ya’ni uchlar soni va qirralar soni ga qarab belgilanadi va bu holda grafni graf deb ataymiz.
Agar va graflarning uchlari to’plamlari, va to’plamlar orasida uchlarning qo’shnilik munosabatini saqlaydigan o’zaro bir qiymatli moslik o’rnatilgan bo’lsa, u holda va graflar izomorf graflar deb ataladi (1.4–rasm). Barcha izomorf graflar bir xil hossalarga ega bo’ladi.