O‘zbekiston respublikasi axborot te

Qirra (edge, link)
Qoʼshni tugunlar
(adjacent vertices)
Yoʼl (path) – bu bironta tugundan boshqa bir tugungacha boʼlgan yonma-yon joylashgan tugunlar ketma-ketligidir.
Graflarni ifodalash usullari

Tugun(vertex, node),Qir ra (edge, link),Qoʼshni tugunlar (adjacent vertices).Yoʼl (path) – bu bironta tugundan boshqa bir tugungacha boʼlgan, yonma-yon joylashgan tugunlar ketma-ketligidir.
Yoʼl: (10, 8, 3, 5)


Xalqa(cycle) – bu boshi va oxiri tutashuvchi tugundan iborat yoʼl xisoblanadi: (4, 6, 7, 8, 3, 4)
(vertex degree) –бу ундан чиқувчи ёйлар сони хисобланади.
deg(7) = 2, deg(1) = 3

G(V, E) ГРАФДА УНИНГ БАРЧА ТУГУНЛАРИ ДАРАЖАЛАРИ ЙИҒИНДИСИ – ЖУФТ , ГРАФНИНГ ҚИРРАЛАРИ СОНИНИНГ ИККИЛАНГАНИГА ТЕНГ.

ТЕОRЕМА

ТУГУНЛАР ЖУФТ(ТОҚ) ДЕЙИЛАДИ, АГАР УЛАРНИНГ ДАРАЖАЛАРИ – ЖУФТ(ТОҚ) ҚИЙМАТЛИ БЎЛСА.
ТЕОРЕМА: ИХТИЁРИЙ ГРАФДА ТОҚ ТУГУНЛАР СОНИ – ЖУФТ БЎЛАДИ
Kelib chiqadiki: Toq sonli toq tugunlardan iborat grafni chizib boʼlmaydi.
Toʼliq graf (complete graph) – bu istalgan tugunlari qoʼshni boʼlgan graf xisoblanadi. (barcha tugunlar oʼzaro birlashtirilgan)

Grafni toʼldiruvchisi bu aynan bir tugunlar va aynan bir qirralardan tashkil topgan va mavjud grafni toʼliq boʼlishini taʼminlovchi grafga aytiladi.

Toʼliq, yoʼnaltirilmagan grafda qirralar soni: m=n(n-2)/2;

D grafning toʼyinganligi (density):D=2m/(n(n-1));
Toʼyingan graf (dense graph) – bu qirralar soni boʼlishi mumkin boʼlgan maksimalga teng boʼlgan graf xisoblanadi. (D>0.5)
Siyrak raf (sparse graph) – bu qirralari soni tugunlar soniga yaqin boʼlgan grafdir. (D<0.5)
Graflarni kompьyuterda ifodalash, yaʼni xotirada tashkil etish mumkin va uning baʼzi usullari:

•