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

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

Тақырыбы:
“Графтар теориясының
элементтері”
Жоспар:
1 Графтар және оның түрлері

2 Графтың қасиеттері
Графтармен байланысты алғаш-қы
жұмыстардың бірі ретінде Л.Эйлердің
(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. Тақ төбелерінің саны екіге тең болатын
графты бір сызықпен сызып шығуға болады.
Мұнда қозғалысты тақ төбелердің кез келген
біреуінен бастап екіншісінен аяқтау қажет.
4. Тақ төбелерінің саны екіден
артық болатын графты бір сызық-
пен сызып шығу мүмкін емес.
5. Кез келген байланысты графтың
дәрежелері тең болатын ең
болмағанда екі төбесі бар болады.
6. Барлық төбелерінің дәрежелері
жұп болатын байланысты граф
Эйлердің сызығы болып
табылады.
7. Байланысты графта оның
барлық қырларын дәл бір реттен
қамтитын l(A, B) шынжыры бар
болуы үшін А мен В төбелерінен
басқа тақ дәрежелі төбелердің
болмауы қажетті және жеткілікті.
Толық графтың және толық жазық
графтың мынадай қасиеттері болады:
1. Егер толық графтың
төбелерінің саны n-ге тең болса,
онда қырларының саны -
ге тең болады.

2. Төбелерінің саны n-ге тең
болатын, мұндағы n≥3, толық
жазық графтың қырларының
саны 3n – 6-ға тең болады.
3. Егер толық графтың төбе-
лерінің саны п 4 болса,
онда ол жазық граф болып
табы-лады.
Анықтама.
Өзара қиылысу нүктелерінде 2
peт қана бола отыра сызып шығу
мүмкін болатын жазық қисықты
уникурсал қисық деп атайды.
Қисықтың нүктесінен тақ санды
жолдар шығатын болса, ондай
нүктені тақ түйін, ал жұп санды
жолдар шығатын болса, жұп түйін
дейді.
Графтың аса маңызды бір
қасиетін теорема түрінде
тұжырым-дайық.
Теорема.
Кез келген графтың тақ
төбелерінің саны жұп болады.
Назарларыңызға
рахмет!

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

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

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

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

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

Қайталану саны белгісіз алгоритм құрылысы

ЕСЕПТЕУДІҢ АЛГОРИТМДІК ШЕШІМІ АЛГОРИТМДІК КҮРДЕЛІКТІ ТАЛДАУ

Алгоритмдер туралы түсінік

Мәліметтер қорының басқа да моделі

Дыбыс биіктігі

Дыбыстың биіктігі

Пәндер