Детерминделмеген алгоритмдер. Лекция-1673199582231 (1). Дріс 12 Дрісті таырыбы
 Скачать 18.24 Kb.
|
|
Дәріс № 12 Дәрістің тақырыбы: Детерминделмеген алгоритмдер. Дәрістің мақсаты: Детерминделмеген алгоритмдер және граф ұғымымен таныстыру. Жоспар: Граф ұғымы. Бағытталған және бағытталмаған графтар. Графтардың берілуі. Графтар теориясы-берілген нүктелерді бір-бірімен қосатын сызықтардан құралған схемалардың қасиеттері жайында ілім. Математиканың бұл саласы электр тізбектерін құрастыру,қалалар арасындағы жүк тасымалын жоспарлау,есептегіш машиналар жасау т.с.с.есептерді шешу негізінде соңғы кезде қалыптасты. Ол алгебрамен,сандар теориясымен,математикалық логикамен тікелей байланысы бар топологияның бір тарауы ретінде қарастырылады. Берілген нүктелерді бір-бірімен қосатын сызықтар торы граф деп аталады. Берілген нүктелерді графтың төбелері дейді, төбелерді екі-екіден қосатын сызықтарды графтың қырлары дейді. Қыр түзу де, қисық сызықта болуы мүмкін. Төбелерден шығатын қырлардың саны сол төбелердің дәрежесі деп аталады. Мысалы: Алматы, Көкшетау, Семей; Талдықорған қалаларын алайық, оларды қысқаша А,К,С,Т әріптерімен белгілейік. Сонда Алматы-Семей жолы АС, Көкшетау - Талдықорған жолы КТ,…,т.с.с. болады(темір жол,қара жол,су жолы,әуе жолы,төте немесе бұрыс жол бәрі бір).Бұл жолдардың схемасыграф құрастырады,схемадағы А,К,С,Т нүктелері графтың төбелері АС,АК,…,СТ сызықтары графтың қырлары рөлін атқарады. Мұндай графтың төбелері үшінші дәрежелі болады. Төбелері сызықтар арқылы қосылмаған схеманы нөлдік граф дейді. Нөлдік графтар-байланыссыз нүктелер жиыны. Кез-келген 2 төбесі қыр арқылы қосылған, кейбір төбелері қосылмаған толымсыз графтар да кездеседі. Оларды, жетпей тұрған қырларын сызып, толықтыруға болады. Төбелері бір жазықтыққа жататын графтар жазық графтар деп аталады, төбелері бір жазықтықта жатпайтын гратар кеңістік графтары деп аталады. Кеңістік графтарын жазық графтарға жіктеуге болады. Әдетте жазық графтар қырлары төбеде ғана қиылыспайтындай етіліп сызылады. Графтардың алдын ала берілген шарттарды қанағаттандыратын арнайы түрлері де бар. Мысалы: бағдарлы графтарда қырлардың бағдары - төбелерден өту реті айтылады, қырларының “салмағы” бар графтарда тиісті қырдың ұзындығы, өткізу қабілеті т.с.с. көрсетіледі. Кейбір қырлары бірнеше рет есептелінетін (“еселі қырлар”),кейбір төбелері айрықша рөл атқаратын (“полюстер”) графтар да қарастырылады. Практикада төбелерінің саны шектеулі графтар жиі кездеседі. Графтар теориясы Кенигсберг көпірлері жөніндегі Л. Эйлердің әйгілі есебінен басталған. Бұл есеп 1736 жылы Петербург ғылым академиясының журналында жарияланған. Кенигсберг (қазіргі Калининград) қаласы Прегель өзенінің екі жағасында және өзен ішіндегі екі аралда орналасқан. Қала халқы оның бірбөлігінен екінші бөлігіне көпір арқылы өтеді. Көпірлердің саны 7. ”Кенигсбергтің бір ауданынан шыққан адам әр көпірден бір-ақ рет өтіп, қаланы түгел аралап шыққан ауданына қайта орала ала ма?” Кенигсберг есебі осы. Жағадағы аудандарды А және В әріптерімен, аралдарды С және Е әріптерімен белгілесек, жол схемасы А, В, С, Е төбелерден және АС, ВС, АЕ, …, СЕ қырлардан құралған граф болып шығады. АС және ВС қырлары екі еселі болады. Эйлер мұндай серуеннің болуы мүмкін емес екендігін көрсетті. Геометрия тілінде айтқанда,қай төбеден шықса да, граф бойынша жүріп отырып,ешбір қырдан екі реет өтпей, шыққан төбеге келуге болмайды. Графтар теориясы программалау теориясында,есептегіш машиналар жасауда, физикалыық, химиялық және технологиялық процестерді зерттеуде, лингвистикада, халық шаруашылығын жоспарлау сияқты жұмыстарда қолданылады. Бақылау сұрақтары: 1. Граф ұғымы. 2.Бағытталған және бағытталмаған графтар. Графтардың берілуі. |