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

Тақырыбы: “Графтар теориясының элементтері”

Notes: Оригинальные шаблоны для презентаций: https://presentation-creation. ru/powerpoint-templates. html

Бесплатно и без регистрации.

Жоспар:

Графтар және оның түрлері

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

Графтармен байланысты алғаш-қы жұмыстардың бірі ретінде Л. Эйлердің (1736 ж. ) «Жеті көпір» туралы есептің шешуін тапқан жұмысы айтылады

XVIII ғасырдың соңына қарай арнасы Кенигсберг (Калининград) қаласы ішімен өтетін Прегель өзенінде, оның жағаларын қала аумағындағы екі аралмен байланыстыратын, жеті көпір салынған болатын. Бір күні қала тұрғыны өзінің көршісінен: «Әрқайсысында бір ғана реттен бола отырып және серуендеуді бастаған жеріне барлық көпірлермен жүріп өткенде, қайтып келе аласың ба?, - деп сұрағандығын әңгіме етеді.

XIX ғасырдың аяғына дейін графтар кейбір жекелеген қызықты есептерді шешуде ғана қолданылып келді. Ең алғаш peт «граф» терминін 1936 жылы венгер математигі Д. Кениг енгізді. Графтар теориясының математиканың жеке бөлімі ретінде бөлініп шығуына қолайлы жағдайлар туғызған аса маңызды нәтижелер XX ғасырда ғана алынды. Қазіргі кезде графтар теориясы қарыштап даму үстінде, ол математиканың классикалық салаларымен бірге, оның жаңа салаларында да жаппай қолданыс табуда.

Графтар теориясы - кейбір мәселелерді шешуге геометриялық тұрғыдан келу тән болып табылатын математиканың бөлімі. Граф- «графа» - «жазамын» деген мағынадағы грек сөзінен алынған.

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

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

Графтың төбелерінен шығатын қырларының саны тақ болса, ондай төбелер тақ деп, ал жұп сан болса, ондай төбелер жұп төбелер деп аталады. Егер графтың барлық төбелері дәрежелерінің санын қоссақ, онда оның қырларының екі еселенген саны шығады, өйткені графтың әр қыры екі рет саналады, яғни 2р=а+b+с+…+ n, мұндағы р - граф қырларының саны; а, b, с, …, n - төбелердің дәрежелері.

Графтың келесідей түрлерін ажыратады.

1. Нөлдік граф - оқшауланған төбелерден тұрады.

2. Толық емес граф - байланыстан бос төбелері (А және В, Е және D, D және С) болады, өйткені оның А төбесі үш төбемен (Е, D, С) және В нүктесі - үш нүктемен (Е, D, С) . D - екі нүктемен (А, В) . С - екі нүктемен (А, В) қосылған.

3. Жазық граф - қырлары тек төбелерінде ғана қиылысатындай етіп, жазықтықта сызып көрсетуге болады.

4. Толық жазық граф - «байланыстан бос» екі пар А және С, К және С төбелерді қосқанда жазық екендігі сақталады. Осылардай басқа төбелер жоқ. Қосылмаған А және D екі төбе қалды, ал оларды қосқанда жазық екендігі сақталмайды.

5. Толық емес жазық граф - қосқанда жазық екендігі сақталып қалатын байланыстырылуы тиіс бос төбелері болады.

6. Бағдарланған граф - барлық қырларының бағыты көрсетіледі.

7. Бағдарланбаған граф - барлық қырларының бағыты көрсетілмейді.

8. Аралас граф - бағдарланған да, бағдарланбаған да қырлары болады.

9. Бірдей немесе изоморфты (тең тұрпатты) графтар - сызықтармен қосылған төбелері бір ғана және бірдей ақпарат береді, өйткені: 1) олардың төбелерінің арасында өзара бірмәнді сәйкестік тағайындауға болады; 2) егер графтардың біреуінің екі төбесі бір қырмен қосылса, онда графтың екіншісінің сәйкес екі төбесі де бір қырмен ғана қосылады.

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

11. Байланыссыз граф - А, В, С, D төбелерден шығып, оның К, Р, Q төбелеріне қырларының ешқайсысынан бір рет қана өте отырып бару мүмкін болмайды.

12. Байланыссыз нөлдік граф - төбелері қырларымен қосылмаған, яғни оқшауланған төбелері бар

Графтың мынадай қасиеттері болады:

1. Оның тақ төбелерінің саны әрқашан жұп болады. Тақ төбелерінің саны тақ сан болатын графты сызып көрсету мүмкін емес.

2. Егер графтың барлық төбелері жұп болса, оңда графты бір сызықпен сызып шығуға (яғни қарындашты қағаз бетінен ажыратпай-ақ, әрбір қырды тек бір ғана рет жүргізе отырып) болады. Мұнда қозғалысты кез келген төбеден бастап, сол төбеден аяқтауға болады.

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