Графтар теориясы

Қазақстан Республикасы ғылым және білім министрлігі

Л. Н. Гумилев атындағы Еуразия ұлттық университеті

Ақпаратты технологиялар факультеті

          [pic 1] 

Студенттің Өзіндік Жұмысы

Орындаған: Қуанбай Қ

Тобы: АБ-23

Тексерген: Кисикова Н.М

Астана 2024 ж.

Графтар теориясы

Табиғаттың кез-келген объектісінен алынған төбелер деп аталатын V – жиыны (оларды жазықтықта нүктелер түрінде көрсетуге болады) және қабырға деп аталатын, ei=(vi1, vi2), vijV, төбелер жұбының жиыны (оларды доғалармен, немесе екі төбе арасындағы бағыттармен көрсетеді) - E болатын екі жиыннан тұратын  G = (V,E) жұбы граф деп аталады. V –төбелер жиыны, E –қабырғалар жиыны деп аталады. Егер ei қабырғасын беретін төбелер ретінің мәні болса, онда граф бағдарланған (ориентирациялы) граф қысқаша – орграф деп деп аталады. Бұл жағдайда графтың доғасына (қабырғасына) бағыт көрсетеді және бір төбесін басы екіншісін –соңы деп айтады. Қарсы жағдайда граф бағдарланбаған (ориентирациясыз, бағдарсыз) деп аталады. Алдағы жағдайларда бағдарланғандығы көрсетілмеген, нақтыланбаған «граф» сөзін бағдарланбаған граф деп есептейміз.

Псевдограф

Псевдограф G(V,E) екі жиынтық жиыны – бос емес жиын V және көптеген Eжиын элементтерінің ретсіз жұптары V.

G(V,E)=(V,E), V, EV  V[pic 2][pic 3][pic 4]

Элемент псевдографтың жиектер жинағында рұқсат етіледі.{ ,}  E(G)[pic 5][pic 6][pic 7]

Цикл - бұл элемент _e = {, }, бұл шеткі төбелері сәйкес келетін жиек.[pic 8][pic 9]

Басқаша айтқанда, егер Е жиынының элементтері циклдар болуы мүмкін болса, онда график псевдограф деп аталады.

Мультиграф

Қарапайым графтың ілгегі және еселі қабырғасы болмайды. Қарапайым графты жай граф деп те айтады. Оларды еселі қабырғалары бар графтардан ажырату үшін еселі қабырғасы бар графтарды мультиграф деп айтады. Ары қарай тек ақырлы графтарды ғана қарастырамыз. Мультиграф G(V,E) екі жиынтық жиыны – бос емес жиын V және мультисеттер E жиынның әртүрлі элементтерінің ретсіз жұптары V.

G(V,E)=(V,E), V, EV  V { ,}  E,   V[pic 10][pic 11][pic 12][pic 13][pic 14][pic 15][pic 16][pic 17]

[pic 18]

1-сурет Бірнеше жиектері (қызыл) және ілмектер (көк) бар мультиграф. Барлық авторлар мультиграфтарда ілмектер болуы мүмкін емес

Бірнеше жиектер мультижиынның бірдей элементтері болып табылады,{e,e, …,e}E яғни соңғы төбелері сәйкес келетін жиектер.[pic 19]

Басқаша айтқанда, егер E жиынтық емес, отбасы, яғни, егер E бірдей элементтерді қамтиды, онда мұндай элементтерді көп қырлы деп, ал графикті мультиграф деп атайды.

Гиперграфтар

Теорияның модельдердің гиперграфтары – теориялардың өздері туралы да, соған байланысты семантикалық объектілер туралы да маңызды құрылымдық ақпаратты алуға мүмкіндік беретін туынды объектілер болып табылады . Еске салайық, гиперграф – кез келген жұп (X, Y), мұндағы Y X жиыны P(X) булеанының кейбір ішкі жиыны. Бұл жағдайда Х жиыны гиперграфтың (X, Y) тірегі деп аталады, ал Y-тің элементтері гиперграфтың (X, Y) қабырғалары деп аталады. M толық T теориясының кейбір моделі болсын. [1]-ге сәйкес, M моделінің N элементар ішкі модельдің негізгі жиыны болып табылатын M жүйесінің M тірегінің барлық ішкі жиындарының N жиынын H(M) арқылы белгілейміз: H (М) = {N | N≺B}.(M, H(M)) жұбы М моделінің элементар ішкі моделінің гиперграфы деп аталады және Н деп белгіленеді.

[pic 20]

2-сурет Көптеген төбелері бар гиперграф

Графтағы маршрут – əрбір i=1, 2, …, n – 1 үшін xi жəне xi+1 төбелері қабырғамен байланысқан x1 , x2 , …, xn төбелер тізбегі. Бұл n-1 қабырғалары маршрут қабырғалары деп аталады, маршрут қабырғалары арқылы өтеді деп айтады, ал n-1санын маршрут ұзындығы деп атайды. Маршрут x1 жəне xn төбелерін байланыстырады дейді, оларды сəйкесінше маршрут басы жəне соңы деп атайды, x2 , …, xn-1 төбелерін аралық деп атайды. Егер x1 =xn болса, онда маршрутты тұйық деп атайды.