Graflar nazariyasi ning asosiy tushunchalari

qo`shni uchlardeyiladi. Grafning bir uchdan chiqqan ikki qirrasi qo`shni qirralardeyiladi. Agar grafda boshi va oxiri bitta tugunda tutashadigan qirra mavjud bo'lsa, unga ilmoqliqirra deyiladi.
4.-rasm. Qirra tushunchasiAgar grafda takroriy (karrali) qirralar mavjud bo`lsa, bunday grafga multigraf deyiladi. Agar grafda karrali qirralar bilan birga uchni o`z-o`zi bilan tutashtiruvchi ilmoqlar ham mavjud bo`lsa, bunday grafga psevdografdeyiladi (5.-rasm).
5.-rasm. A) multigraf; B) psevdografIxtiyoriy tugundan boshqa bironta tugunga murojaat mavjud va murojaat ikki tomonlama bo’lsa, bu holda bunday graf yo’naltirilmagangraf(graph) deyiladi (6.-rasm. A).
Agar graf tugunlari o'zaro bog'langan bo'lsa, lekin bu yoylar orqali munosabat faqat bir tomonlama bo'lsa, u xolda bunday graflar yo'naltirilgan graflar(oriented graph) deyiladi (6.-rasm. B).
6.-rasm. A) yo’naltirilmagan graf; B) yo’naltirilgan graf
Og’irlikka (vaznga) ega bo’lgan graf (weighted graph) – bu qirralari (yo’ylari) og’irliklari bilan berilgan graf hisoblandi. (i,j) qirraning og’irligi wij kabi belgilanadi (7.-rasm).
7.-rasm. Og’irlikka ega bo’lgan grafAgar Vto`plamning quvvati nga teng bo`lsa, nsoni grafning tartibideyiladi. Agar V to`plamning quvvati nga teng bo`lsa, E to`plamning quvvati m ga teng bo`lsa, graf (n, m) grafdeyiladi.
Tugun darajasi(vertex degree) – bu undan chiquvchi yoylar soni xisoblanadi. deg(7) = 2, deg(1) = 3
Halqa(cycle) – bu boshi va oxiri tutashuvchi tugundan iborat yo'l hisoblanadi: (4, 6, 7, 8, 3, 4) (1.2.8.-rasm).G(V, E) grafda uning barcha tugunlari darajalari yig'indisi – juft, grafning qirralari sonining ikkilanganiga teng.
Tugunlar darajasiga nisbatan juft yoki toq deyiladi, agar ularning darajalari mos ravishda juft yoki toq qiymatga teng bo'lsa.
8.-rasm. Grafning halqa va tugun darajasiga misol
To'liq graf(complete graph) – bu istalgan tugunlari qo'shni bo'lgan graf xisoblanadi yani barcha tugunlar o'zaro birlashtirilgan. (9. a -rasm)Grafni to'ldiruvchisi bu aynan bir tugunlar va aynan bir qirralardan tashkil topgan va mavjud grafni to'liq bo'lishini ta'minlovchi grafga aytiladi. (9. b -rasm)
a)
b)
9.-rasm.a) to’liq graf b) graf va uning to’ldiruvchisiTo'liq, yo'naltirilmagan grafda qirralar soni quyidagi formula (1) orqali aniqlanadi:
(1)qaerda n – yoylar(tugunlar) soni.
D grafning to'yinganligi (density) grafning qirralrining tugunlar nisbatiga to’liqlik munosabat koefitsientini belgilaydi va quyidagi formula (2) orqali aniqlanadi:
(2)qaerda n – grafning tugunlar soni, m – grafning qirralar soni.
Grafning to'yinganligi koefitsientiga qarab ikki hil graf ko’rinishi aniqlash mumkin: to'yingan graf va siyrak graf (10.-rasm).
To'yingan graf (dense graph) – bu qirralar soni bo'lishi mumkin bo'lgan maksimalga teng bo'lgan graf xisoblanadi. (D0.5)
Siyrak graf(sparse graph) – bu qirralari soni tugunlar soniga yaqin bo'lgan grafdir. (D
a) b)
10-rasm.a) to'yingan graf (D=0.9) b) siyrak graf (D=0.33)Quyida turli ko’rinishdagi graflar keltirilgan.

11-rasm. a-d oddiy graf, c-to’liq graf, e-multigraf, f-psevdograf, g-digrafdagi zanjir, h-digrafda xalqa.

2. Graflarni ifodalash usullariYo’naltirilmagan, yo’naltirilgan va o’girlikka ega bo’lgan graflarni kompyuter dasturlash tillari hotirasida ifodalash, ya'ni xotirada tashkil etish uchun statik tuzilmasi matritsadan yoki dinamik tuzilmasi ro’yxatlardan foydalanish mumkin. Har qanday masalalarida har bitta usulining o’zining afzalligi va kamchiliklariga egadir. Yo’naltirilmagan, yo’naltirilgan va o’girlikka ega bo’lgan graflarni ifodalash uchun har usulining o’zining qoida asosida shakllanadi. Shunday to’rtta usullarga to’xtalib o’tamiz:
Qo'shma matritsa (adjacency matrix);
Intsidientlik matritsa (incidence matrix);
Qo'shnilik ro'yxati (adjacency list);
Qirralar ro'yxati (edges list).
G grafning