Режа: Асосий тушунчалар ва граф турлари Графларни ифодалаш усуллари Графларни кўрувдан ўтказиш

Графларни ифодалаш усуллари

Графларни ифодалаш усуллари

Тугун(vertex, node)
Қирра (edge, link)
Қўшни тугунлар
(adjacent vertices)
Йўл (path) – бу биронта тугундан бошқа бир тугунгача бўлган ёнма-ён жойлашган тугунлар кетма-кетлигидир.

Йўл: (10, 8, 3, 5)

Тугун(vertex, node),Қир ра (edge, link),Қўшни тугунлар (adjacent vertices).Йўл (path) – бу биронта тугундан бошқа бир тугунгача бўлган, ёнма-ён жойлашган тугунлар кетмa-кетлигидир.
Йўл: (10, 8, 3, 5)



Халқа(cycle) – бу боши ва охири туташувчи тугундан иборат йўл хисобланади: (4, 6, 7, 8, 3, 4)
Тугун даражаси
(vertex degree) –бу ундан чиқувчи ёйлар сони хисобланади.
deg(7) = 2, deg(1) = 3

ТЕОРЕМА

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

ТУГУНЛАР ЖУФТ(ТОҚ) ДЕЙИЛАДИ, АГАР УЛАРНИНГ ДАРАЖАЛАРИ – ЖУФТ(ТОҚ) ҚИЙМАТЛИ БЎЛСА.
ТЕОРЕМА: ИХТИЁРИЙ ГРАФДА ТОҚ ТУГУНЛАР СОНИ – ЖУФТ БЎЛАДИ
Келиб чиқадики: Тоқ сонли тоқ тугунлардан иборат графни чизиб бўлмайди.
Тўлиқ граф (complete graph) – бу исталган тугунлари қўшни бўлган граф хисобланади. (барча тугунлар ўзаро бирлаштирилган)
Графни тўлдирувчиси бу айнан бир тугунлар ва айнан бир қирралардан ташкил топган ва мавжуд графни тўлиқ бўлишини таъминловчи графга айтилади.
ГРАФНИ ТЎЛДИРУВЧИСИ

Тўлиқ, йўналтирилмаган графда қирралар сони: m=n(n-2)/2;

D графнинг тўйинганлиги (density):D=2m/(n(n-1));
Тўйинган граф (dense graph) – бу қирралар сони бўлиши мумкин бўлган максималга тенг бўлган граф хисобланади. (D>0.5)
Сийрак раф (sparse graph) – бу қирралари сони тугунлар сонига яқин бўлган графдир. (D<0.5)

Графларни компьютерда ифодалаш, яъни хотирада ташкил этиш мумкин ва унинг баъзи усуллари:

•