Графтар

[pic 1]

РЕФЕРАТ

Тақырыбы: Графтар

Тобы: ПИ 21-11

Орындаган: Алламбергенов Ислам

Алматы 2022ж

Мазмұны

Графтар және олардың териясы                                                          3

Эйлер циклы.Гамильтон теориясы                                                     5

Циклдар түрлері. Мысалдар                                                                6

Пайдаланған мәліметтер                                                                      9

Көптеген қолданбалы есептерде айналамызды қоршаған ортаның әртүрлі объектілер  арасындағы байланыстар жүйесі зерттеледі. Объектілер төбелер деп аталып, нүктелер арқылы белгіленеді, ал төбелер арасындағы байланыстар доғалар деп аталып, сәйкес нүктелерді қосатын бағытталған түзулермен  белгіленеді. Қала көшелерін граф арқылы кескіндеуге болады: көше қиылысуларын графтардың төбесі деп, ал көшелерді  доғалар деп алуға болады; Блок-схемаларды да граф түрінде кескіндеуге болады: блоктар — граф төбелері, ал операцияның орындалу кезегін көрсететін стрелкалар доғалар.

G=(M,R) алгебралық жүйе граф деп аталады. Мұндағы М—жиынтығы бос емес жиын, оның элементтері графтың төбелері деп аталады, ал бинарлы R қатынасының R  M2 элементтері доғалар деп аталады. Сонымен   граф төбелері дегеніміз –айналамызды қоршаған ортаның кез келген объектісі. Олардың саны шектеулі болғандықтан,біз оларды натурал сандармен белгілейміз. Ал граф қабырғалары оның кейбір төбелерін қосады. Граф қабырғаларын әдетте латын әріптерімен белгілейді. G= ‹M,R› графының геометриялық кескіні жазықтықта графтың әр төбесін нүкте арқылы белгілеп ,  егер (a,b)  R болса а төбесінен b төбесіне доға жүргізу арқылы алынады. Мысалы: төбелері М={1,2,3,4}, ал доғалары R={(1,1),(1,2),(2,3),(3,4),(4,3),(4,1)} болатын G графының геометриялық кескіні төмендегідей:

[pic 2][pic 3]

Графтың төбелерінің қандай сызықтарымен қосылатындығы (түзу әлде қисық), сызықтардың ұзындығы туралы ақпараттар маңызды емес.Төбелердің арасында байланыс бар екендігі және ол байланыс туралы ақпарат R доғалар жиынында екендігі болса болды.Төбелерді қосатын сызықтардың бағыты көрсетілген болуы мүмкін (мысалдағы сияқты). Мұндай граф бағытталған граф деп аталады (орграф). Оған математикалық түрде мынандай анықтама беруге болады.

3

[pic 4]

Графтар, негізінен, геометриялық фигура түрінде бейнеленеді, сондықтан графтың төбелері нүкте арқылы, қабырғалары нүктелерді бір-бірімен қосатын сызықтар арқылы бейнеленеді. Графтың шеткі төбелері бірдей болса, онда барлық қабырғалары параллель болып табылады. Ал, егер қабырғасының басы мен соңы бір төбеде орналасса онда оны ілмек деп атаймыз. Жалпы айтқанда, ілмектің бағыты болмайды. Бірақ бағытталған графтарды аралас графтардан ажырату үшін бағытталған графтарда ілмектің бағыты көрсетіледі.

Ілмек – бұл бастапқы жəне шеткі доғаның бір-бірмен сəйкестенуі. Ілмексіз жəне параллель қабырғасыз графтар қарапайым граф деп аталады.

Графтың төбелерінің жиыны n элементтен тұратын болса, онда G граф n-ретті граф болады. Қабырғалары жоқ графтар бос граф деп аталады (1.1 в-сурет). Ал, егер графтың төбелері жоқ болса (онда əрине қабырғалары да жоқ), онда мұндай граф нөл-граф деп аталады.

Маршрутты төбелердің тізбегі арқылы беруге болады. Маршрут доғаларының саны оның ұзындығы деп аталады.

        Айталық, G  н-граф болсын. Егер (*) маршрутта қабырғалар [a1a2],…, [anan+1] әртүрлі болса, яғни әр қабырға бірден артық кездеспесе, маршрут шынжыр деп аталады, ал графтың кез келген төбесі 2-ден артық емес қабырғаға инцидентті болса (төбелер әртүрлі ), онда маршрут қарапайым шынжыр деп аталады.