Граф

[pic 1]
 
   

РЕФЕРАТ

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

Орындаған: Ертлеуов А.

Тобы: ВТиПО 22-11

Тексерген: Молдакалыкова А.Ж.

Алматы 2020

МАЗМҰНЫ

Графтар теориясы туралы алғашқы еңбекті Леонард Эйлер

1773 жылы жазған, бірақ «граф» ұғымын 1936 жылы тұңғын рет

венгр математигі Денеш Кениғ енгізген.

Зерттеліп отырған жазықтағы жүйенің, үдерістердің,

құбылыстардың кез келғен көрнекті кескіші кең мағынадағы

графикалық көрініс болып табылады. Оларға аймақтың жос-

пар-картасымен сипаттамасын, үдерістердің блок-схемаларын,

диаграммаларын және т.б. байланысты сызбаларын, суреттерін,

кескіндерді жатқызуға болады. Мұңдай бейнелеулер түрлі

өзара байланыстарды, өзара шарттылық өрнекті түрде, яғни

обьектілердің тополоғиялық (кеңістіктік) орналасуын, үдеріс-

тер мен құбылыстардың хронологиялық (уақыт бойынша)

қатысын, логикалық, құрылымдық және басқа да байланыстарын

көрсетеді.

Графтар теориясы - графтардың қасиетін оқытатын дискретті

математиканың бір бөліміне жатады. Графтар теориясының

практикалық мүмкіндіктері өте зор. Түрлі білім салаларында,

мысалы психолоғия, химия, электротехника, сонымен қатар көлік

тасымалдауда, басқаруда, сауда-саттықта және білім беруді жос-

парлауда туындайтын кейбір проблемалар графтар теориясының

мәселесі ретінде қалыптасуы мүмкін. Осы жағдайларға байланыс-

ты графтар теориясы өз алдына қызықты деп қана саналмай,

алынған нәтижелерін жинақтайтын, біліктендіретін, жалпылай-

тын және жан-жақты тарататын білімнің түрлі аймағындағы бас-

ты негіздерін көрсетеді.

Мысалы, графтар теориясы ғеоақпараттық жүйелерде де

қолданылады. Жаңадан жоспарланған немесе салынған үйді

қайта жоспарлауда, құрылыстарда, нысандарда және т.б. ол

төбелері ретінде қарастырылса, олардың жолдарының бірігуін,

инженерлік желілер, электротасымалдау желілері және т.б.-оның

қабырғасы ретінде қарастырылады. Сондай-ақ, ең қысқа айналу

жолын немесе ең жақын азық-түлік дүкенін табу сияқты графтардан шығатын түрлі ессптеулерді қолдану тиімді бағдарларды

жоспарлауға мүмкіндік береді.

Соңғы жылдары математиканың сандык құрылғыларға,

сандық байланыс пен сандык есептеу машиналарына қатысы бар

бөлімдері ерекше маңызға ие болуда. Осы пәндерді оқытудың

негізін үздіксіз физикалық модельдерді талдаудың классикалық

әдістерімен қатар, дискретті математиканың әр алуан модельдерін

зерттеудің алгебралық, логикалык және комбинаторлық әдістері

құрап отыр.

Дискретті математиканың тармағы -- графтар теориясының

танымалдығы едәуір өсті. Графтар әртүрлі атаулар мен көптеген

салаларда кездеседі: азаматтық құрылыста- «құрылым», электро-

никада - «желі», социология мен экономикада <- «соңиограмма»,

химияда - «молекулярлық құрылым», «жол карталары», электр

немесе газ тарату желілері және т.с.с.

Компьютерлік химия графтар теориясын қолдануға негіз-

делген химия ғылымының салыстырмалы түрде жас саласы бо-

лып табылады.

Графтар теориясы хемоинформатиканың математикалық

негізін құрап отыр, ол көмірсутектердің және басқа органикалық

қосылыстардың теориялық жағынан ықтимал изомерлерінің са-

нын дәл анықтауға мүмкіндік береді.

Басқатырғыштар мен ойындарды, атап айтқанда, кениғсберг

көпірлері, Гамильтон ойыны сияқты есептерді шешу кезінде пай-