Графтар теориясының элементтері

Презентация қосу

Графтар.
Графтар теориясының элементтері.
Сәйкестік, түрлері және қасиеттері

Тексерген: Тазабекова А.С.
Орындаған: Нурлан А.Н.
1 курс 3 жылдық
Граф ұғымы
Граф ұғымы
Көптеген қолданбалы есептерде айналамызды
қоршаған ортаның әртүрлі объектілер арасындағы
байланыстар жүйесі зерттеледі. Объектілер
төбелер деп аталып, нүктелер арқылы белгіленеді,
ал төбелер арасындағы байланыстар доғалар деп
аталып, сәйкес нүктелерді қосатын бағытталған
түзулермен белгіленеді.
Қала көшелерін граф арқылы кескіндеуге болады:
көше қиылысуларын графтардың төбесі деп, ал
көшелерді доғалар деп алуға болады;
Блок-схемаларды да граф түрінде кескіндеуге
болады: блоктар — граф төбелері, ал операцияның
орындалу кезегін көрсететін стрелкалар доғалар.
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 графының геометриялық
кескіні төмендегідей:
Графтың төбелерінің қандай сызықтарымен
қосылатындығы (түзу әлде қисық), сызықтардың ұзындығы

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

Анықтама: Егер R қатынасы симметриялы болмаса, яғни (a,b) R,
(b,а) R онда G= графы бағытталған (оргграф) деп аталады, ал
R қатынасы симметриялы болса (a,b) R, (b,а) R онда G
бағытталмаған (неоргграф) немесе н-граф деп аталады Айталық:
a,b-граф төбелері, e=(a,b) оларды қосатын доға болсын. Мұндай
жағдайда а, b төбелері мен е доғасы инцидентті деп
аталады. b мен e доғасы даинцидентті. Әр доға e E өзі қосатын екі
төбеге инцидентті болады. Бір доғамен қосылатын 2 төбе сыбайлас
( бүйірлес) деп аталады.
Графтар теориясы-шектеулі математиканың кейбір
мәселелерді шешуге геометриялық тұрғыдан келу тән
бюолып табылатын бөлім. Граф теориясының негізгі
мазмұны графтарды зерттеу болып табылады. Граф –
«граф» – «жазамын» деген мағанадағы грек сөзінен
алынған.

Жазықтықта әртүрлі бес A,B,C,D,E нүктелерін белгілейік.
Осы нүктелерді графтың төбелері, ал оларды қосатын
сызықтарды \түзу немесе қисық\ графтың қабырғалары
деа атайды.
Бұл графты A,B,C,D,E нүктелерін қосатын сызықтар осы
нүктелерден басқа ешбір нүктелерден
қиылыспайтындай етіп те кескіндеуге болады.
Қабырғалары тек төбелерінде ғана
қиылысатын графты жазық граф деп атайды.
Графтың мынадай
негізгі қасиеттері болады:
Оның тақ төбелерінің саны әрқашан жұп болады. Тақ төбелерінің
саны тақ сан болатын графты сызып көрсету мүмкін емес.

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

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

Тақ төбелерінің саны екіден артық болатын графты бір сызықпен
сызып шығу мүмкін емес.
Кез – келген жазық граф
үшін Т – Қ + Ж= 2 теңдігі
Өзара орындалады. Мұндағы Т
қиылысу Қисық бір – граф төбелерінің саны,
нүктелерінде бағытты Қ – граф
екі ғана рет (уникурсал) қабырғаларының саны,
Ж –оның жақтарының
бола отырып болу үшін саны. Бұл теорема
сызып оның тақ жазық графтар үшін
шығуға түйіндерінің Эйлер теоремасы деп
болатын саны екіден аталады. Жалпы
жазық артықболмау апйтқанда, графтар
төбелерден ,
қисықты бір ы қажетті қабырғалардын және
бағытты және жақтардан тұрады.
қисық деп жеткілікті. Берілген граф арқылы
атайды. жазықтықтың бөлінген
бөліктері жақтар деп
аталады.
Графтағы ешбір қабырға арқылы бірден артық
рет өтпейтін сызық шынжыр деп аталады.
Егер қозғалысты А нүктесінен бастап барлық
төбелерден қайта оралу мүмкін болса , мұндай
жолды цикл деп атайды. Егер циклдыңң барлық
төбелері әртүрлі болса, мұндай цикл қарарайым
цикл, ал қарсы жағдайда қарапайым емес цикл
деп аталады. Кей жағдайда цикл графтың
барлық қабырғаларын дәл бір реттен қамтиды.
Мұндай циклдарды Эйлер сызықтарды деп
атайды.
ГРАФТАРДЫҢ ТҮРЛЕРІ
Бағдарланбaғaн граф
(Неориентированный граф)-
төбелерді қосатын доғаларының
бағыты болмайтын граф.

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

Ұқсас жұмыстар

Графтың қасиеттері

Деректер қоры

Графтар әдісі

Мектептегі дискретті математика элементтерін оқыту әдістемесі

МАШИНАЛАР БЕКІМДІЛІГІН ТӨМЕНДЕТЕТІН ІШКІ ЖӘНЕ СЫРТҚЫ ФАКТОРЛАР

11-15 ғасырлардағы Италия, 7 - сынып

Графтың байланыс компоненттері

Оқиға бірнеше түрге бөлінеді сенімді

Электрон жұптарының тебісу теориясы

Басқару теориясы

Пәндер