Графтар теориясының элементтері
Автор: kadirbai01 • Октябрь 3, 2021 • Лекция • 1,418 Слов (6 Страниц) • 1,463 Просмотры
Лекция 3. Графтар теориясының элементтері (2 сағат)
- Графтар және оның түрлері
- Графтың қасиеттері
3. Л.Эйлер теоремасы
Лекция мақсаты: Граф түрлері және графтар теориясының элементтерімен таныстыру.
Графтар теориясы - кейбір мәселелерді шешуге геометриялық тұрғыдан келу тән болып табылатын математиканың бөлімі. Граф- «графа» - «жазамын» деген мағынадағы грек сөзінен алынған.
Граф - нүктелер (төбелер) жиынынан және осы нүктелерді байла-ныстыратын түзулер кесінділері мен қисықтардан (қырлар) құралған схема (геометриялық фигура). Графтың әрбір қыры екі төбені байла-ныстырады және керісінше, әрбір қырын жүргізу үшін оның екі төбесі қажет болады.
Берілген графпен бөлінгенде шыққан жазықтықтың бөліктерін, сыртқысын да қоса есептегенде, оның жақтары деп атайды. Графтың әр төбесінен шығатын қырларының санын графтың төбесінің дәре-жесі деп атайды. Төбенің дәрежесі нөлге тең болуы, әртүрлі төбелер-дің дәрежелері бірдей немесе әртүрлі болуы да мүмкін. Егер графтың барлық төбелерінің дәрежелері өзара тең болса, онда граф біртекті деп аталады.
Графтың төбелерінен шығатын қырларының саны тақ болса, ондай төбелер тақ деп, ал жұп сан болса, ондай төбелер жұп төбелер деп аталады. Егер графтың барлық төбелері дәрежелерінің санын қоссақ, онда оның қырларының екі еселенген саны шығады, өйткені графтың әр қыры екі рет саналады, яғни 2р=а+b+с+…+ n, мұндағы р – граф қырларының саны; а,b,с,…,n – төбелердің дәрежелері.
Графтың келесідей түрлерін ажыратады.
1. Нөлдік граф – оқшауланған төбелерден тұрады. | [pic 1] |
2. Толық емес граф – байланыстан бос төбелері (Ажәне В, Е және D, Dжәне С) болады, өйткені оның А төбесі үш төбемен (Е, D, С) және В нүктесі - үш нүктемен (Е, D, С). D– екі нүктемен (А, В). С– екі нүктемен (А, В) қосылған. | [pic 2] |
3. Жазық граф– қырлары тек төбелерінде ғана қиылысатындай етіп, жазықтықта сызып көрсетуге болады. | [pic 3] |
4. Толық жазық граф –«байланыстан бос» екі пар А және С, Кжәне С төбелерді қосқанда жазық екендігі сақталады. Осылардай басқа төбелер жоқ. Қосылмаған А және D екі төбе қалды, ал оларды қосқанда жазық екендігі сақталмайды. | [pic 4] |
5. Толық емес жазық граф – қосқанда жазық екендігі сақталып қалатын байланыстырылуы тиіс бос төбелері болады. | [pic 5] |
6. Бағдарланған граф– барлық қырларының бағыты көрсетіледі. | [pic 6] |
7. Бағдарланбаған граф– барлық қырларының бағыты көрсетілмейді. | [pic 7] |
8. Аралас граф– бағдарланған да, бағдарланбаған да қырлары болады. | [pic 8] |
9. Бірдей немесе изоморфты (тең тұрпатты) графтар – сызықтармен қосылған төбелері бір ғана және бірдей ақпарат береді, өйткені: 1) олардың төбелерінің арасында өзара бірмәнді сәйкестік тағайындауға болады; 2) егер графтардың біреуінің екі төбесі бір қырмен қосылса, онда графтың екіншісінің сәйкес екі төбесі де бір қырмен ғана қосылады. | [pic 9] |
10. Тұзақты граф – ұштарындағы нүктелері беттесетін (тұзақ түзетін) қырлары болады. Графты кескіндеп көрсету барысында шыққан төбеге қайтып келетін және басқа төбелерден өтпейтін тұйық доға түрінде болады. Әдетте тұзақ бағдарланбаған болып есептеледі. | [pic 10] |
11. Байланысты граф– кез келген екі төбесі қандай да бір шынжырмен байланысады, яғни бірде бір оқшауланған төбесі болмайды. Графтың ешбір қыры арқылы бірден артық рет өтпейтін сызық шынжыр деп аталады. Егер қозғалысты А төбеден бастап, графтың бірнеше төбелерінен әр қыры бойымен тек бір ғана рет жүре отырып, сол төбеге қайта оралу мүмкін болса, мұндай жолды цикл деп атайды. | [pic 11] |
12. Байланыссыз граф–А, В, С, D төбелерден шығып, оның К, Р, Q төбелеріне қырларының ешқайсысынан бір рет қана өте отырып бару мүмкін болмайды. | [pic 12] |
13. Байланыссыз нөлдік граф– төбелері қырларымен қосылмаған, яғни оқшауланған төбелері бар. | [pic 13] |
...