Программа дисциплины для студентов
жүктеу/скачать 5,71 Mb.
|
| Түрлері:
1)Бағдарланбaғaн граф (Неориентированный граф) — төбелерді қосатын доғаларының бағыты болмайтын граф. 2)Бағдарланған граф (Ориентированный граф; directed graph) - әр түрлі төбелер жұбын жалғастыратын қабырғалармен бірге түйіндердің (немесе төбелердің) құр ақырғы жиыны. Егер е қабырғасы Vl және V2 төбелерін жалғастырса, онда Vl мен И,-ні инцидент деп атайды және бұл төбелер көршілес болып саналады, е — реттелмеген жұп (К, и V2). Әдетте, граф көрнекті формада ұсынылады, сонымен бірге төбелері нүктелермен немесе кейде ұқсастыру мақсатымен ентаңбаланған басқа мүсіндермен, ал қабырғалары сәйкес нүктелерді жалғастыратын сызықтармен кескінделеді. Егер әрбір қабырғаға бағыт көрсетілсе, онда мұндай граф бағдарланған граф деп аталады. Бұл жағдайда қабырға әр түрлі төбелердің реттелген жұбының жиынын үйымдастырады және оларды көбінесе доға деп атайды. Бағдарланған граф көрнекті түрде ұсынылған кезде әрбір доға жебелікпен жабдықталады. "Есептерді граф арқылы шешу" тақырыбы бойынша көптеген нүктелерді жүргізе отырып, әр түрлі фигураларды құрастырамыз. Соның салдарынан "граф" ұғымы пайда болған. "Граф" деп кез-келген нүктелерді, яғни олардың түзумен немесе бағыттауыштармен (стрелка) байланысқаны. Көптеген элементтерді бейнелейтін нүктелерді "граф шыңы" деп атайды. Егер бағыттауыштардың(стрелка) басы мен соңы теңессе, онда оны дәнекер деп атайды. Граф теориясы математиканың логика, комбинаторика, тағы басқа салаларында қолданылады. Сондықтан бұл тақырыпты мектепте оқыту жалпы білім беретін, мәдениет танытатын, математикалық мән-мағынасы ерекше. Күнделікті өмірде көптеген графикалық иллюстрацияларды, геометриялық елестерді және т.б. көптеген тәсілдер пайдаланылады Оқушыларға әрбір логикалық пікірдің дәмін сезіне білу керек және бұл жерде графтарды қолдану логикаға назарын аударуға көмектеседі. Графтардың түзулері қабырғалары деп, ал нүктелері төбелері деп аталады. Графтардың төбелері тек нүктемен ғана емес, сонымен қатар, дөңгелектермен немесе басқа да фигуралармен берілуі мүмкін. Оқушы граф арқылы есеп шығара отырып, өзінің логикасын дамытады. Есептерді граф арқылы шешуді есеп шығару кезінде қолдана білсе, онда олардың пәнге деген қызығушылығы артады. "Граф" сөзі математикалық әдебиетте жаңадан пайда болған ұғым. Сонымен қатар, граф тек қана математикада ғана қолданылып қоймай, тіпті техника мен күнделікті өмірде де басқа атаулармен (схема, диаграмма,т.б) кездеседі. Әсіресе граф көптеген логикалық есептерді шығаруда көмектеседі. Графтар есептерді немесе олардың шығару жолдарын адам есіне лезде сақтап алуы үшін де қолданылады. Логикалық есептер адамның ойлау қабілеттігін арттырады. Оқушыларға әрбір логикалық пікірдің дәмін сезіне білу керек және бұл жерде графтарды қолдану логикаға назарын аударуға көмектеседі. Графтардың түзулері қабырғалары деп, ал нүктелері төбелері деп аталады. Графтардың төбелері тек нүктемен ғана емес, сонымен қатар, дөңгелектермен немесе басқа да фигуралармен берілуі мүмкін. Граф теориясы математиканың логика, комбинаторика, тағы басқа салаларында қолданылады. Сондықтан бұл тақырыпты мектепте оқыту жалпы білім беретін, мәдениет танытатын, математикалық мән-мағынасы ерекше. Күнделікті өмірде көптеген графикалық иллюстрацияларды, геометриялық елестерді және т.б. көптеген тәсілдер пайдаланылады Кенигсберг көпірі жайындағы есепті алғаш рет Л.Эйлер (1707-1783) графтар теориясы арқылы қарастырды. Бұдан 100 жыл өткен соң әсіресе Англияда жаратылыстану ғылымының барынша әр түрлі формадағы саласында гарфтар теориясы қолданыла бастады. Электр тізбегі мен кристалл моделін молекуланың структурасын зерттеуге, сондай-ақ ойындар теориясы мен программалауда, биология мен психологияда кеңінен қолданылды. Графтар арқылы есептерді шешуге мынадай мысалдарды қарастыратын болсақ: 1-есеп: Үш дос- Серік, Талғат, Ернар әр түрлі үш пәннен (химия, биология, физика) Алматының, Қарағандының, Көкшетаудың мектептерінде оқытады. Егер мына мәліметтер белгілі болса: 1) Серік Алматыда істемейді, ал Талғат Қарағандыда тұрмайды; 2) Алматылық физикадан сабақ бермейді; 3) Қарағандыда тұратын мұғалім химиядан сабақ береді; 4) Талғат биологиядан сабақ бермейді. Әр мұғалім қай қалада тұрады, қандай пәннен сабақ береді? Шешуі:Үш жиын алып, олардан үштен нүкте қарастырамыз. Оларды адамдар аттарының бас әріптері, пәндер мен қалалардың аттарының бірінші әріптерімен белгілейміз. Әр түрлі жиыннан алынған нүктелер бір ғана адамның қасиеттерін бейнелей алса, онда ол нүктелерді тұтас (үзіксіз) сызықтармен қосамыз, егер олар әр түрлі адамның белгілерін білдірсе, үзік сызықтармен (штрихтармен) қосамыз. Үзік-қызыл, ал тұтас – қара түспен сызамыз. Есептің берілгендері 1 –суретте: 1-СУРЕТ Граф есеп шартында көрсетілген жиын элементі және олардың арасындағы байланыс болады. Бұл есеп граф тілінде төбелері үш жиында жатқан, қабырғалары тұтас сы-зықтармен қосылған үш үшбұрышты салуға келтіреледі. ХТ- сәйкес келмейді, Х мен Т-ны қызыл сызықпен қосамыз, ол КХ сәйкес келеді (Көкшетауда тұратын мұғалім химиядан береді), Т мен К сәйкес келмейді – ТК, сондықтан Т мен Х сәйкес келмейді (2-суретте). Граф арқылы осы есепке ұқсас есепті шешкенде мынадай ережелерді пайдаланамыз: 1) Үш төбесі үш жиында жатқан үщбұрыштың бір қабырғасы тұтас (қара) сызықпен, екіншісі үзік(қызыл) сызықпен сызылса, онда үшінші қабырғасы үзік (қызыл) сызықпен сызылады; 2) Жиыннның бір нүктесінен 2-жиындағы 2-нүктеге үзік (қызыл) сызық жүргізілсе, онда үшіншісіне тұтас (қара) сызық жүргізіледі; 3) Егер төбелері әр түрлі жиында жатқан үшбұрыштың екі қабырғасы тұтас (қара) сызықпен сызылса, онда үшіншісі де тұтас (қара) сызықпен қосылады. Ережеге сүйеніп Ф мен Т-ны тұтас сызықпен қосамыз (ФТ). АТ- үзік сызықпен сызылады, себебі ТФА үшбұршында ТФ –тұтас, ФА- үзік сызықтармен сызылады. ТҚ тұтас сызықпен қосылады, себебі ТА,ТК- үзік сызықтар. ФҚ- тұтас сызық. Олай болса, ТФҚ-үшбұрышының қабырғалары тұтас сызық болады. АЕ,СК,ХС, БА, БЕ-тұтас сызықтарын жүргіземіз. Сонда ТФҚ, КХС және ЕАБ- үшбұрышының төбелеріндегі элементтер сәйкес келіп,есептің сұрағына жауап береді, яғни Ернар- биолог Алматыда тұрады; Серік - Көкшетауда тұрып, химиядан сабақ береді; Талғат Қарағандыда тұрады, физикадан сабақ беред. 2-есеп: Дүйсенбі күнгі сабақ кестесін құру кезінде үш мұғалім мынадай өтініш айтты: 1) математика бірінші не екінші, 2) тарих бірінші не үшінші, 3) әдебиет екінші не үшінші болсын. Қанша тәсілмен мұғалім өтінішін орындауға болады? 3-СУРЕТ Шешуі: Математика, тарих, әдебиеттің бас әріптерінен бір жиын сабақтардың 1,2,3 –деген ретінен екінші жиын құралық (3-сурет)) Математиканы 1-сабаққа (онда ол 2-бола алмайды) қойсақ, онда тарих тек үшніші ғана болады, тарих 1-қойылмайды, онда әдебиет 2-сабаққа қойылған болады, ол 3- сабаққа қойылмайды. Сонымен математика- бірінші, әдебиет-екінші, тарих-үшінші болады. Теңдеуді граф арқылы шешу, яғни бұл бағытталған граф болып табылады. 3-есеп: Мен бір сан ойладым. Сол санға 24 қоссақ, одан шыққан санды 9-ға көбей-тсек, сосын 76- ны алсақ, ендігі шыққан санды 19- ға бөлсек, онда 23 шығады.Ойлаған санды табайық. ((х + 24)*9-76)/19=23 9х+140=437 9х=297 х=33 Графты құрайық. Енді осы сандарды керісінше амалмен шығарайық (4-сурет) 23*19 =437 437+76=513 513/9=57 57-24=33. Сонымен ойлаған санды таптық-33. 4-СУРЕТ Математикада ешбір математикалық ережелерді немесе теоремаларды қолдануға келмейтін, тек ойлау арқылы шығарылатын есептер деп аталады. Осындай логикалық есертерді, математикалық басқатырғыларды шешуде графтар қолданылады. Граф деп қандай да бір берілген пункттерді қосатын сызықтар системасын айтамыз, яғни әуелі біз берілген обьектілерді нүктелер арқылы кескіндейміз, оларды берілген шарттар арқылы кескінділермен қосамыз, нүктелер мен кесінділер арасында операциялар орындаймыз. Графтар теориясы бас қатырғыларды шешумен байланысты XVIII ғасырда туды. Графтар теориясынан ең бірінші еңбекті белгілі швед математигі Эйлер 1736 жылы жазды. Әуелгі кезде бұл теория тек топологияның өркендеуіне байланысты графтар теориясы математиканың бір саласы ретінде ең алғаш ХХ ғасырдың 30 жылдарында венгер математигі Кенигтің еңбегінде айтылады. 4-есеп: Географиялық картаға қарағанда көзге, бірден темір жол желісі түседі. Бұл негізгі граф: дөңгелектер станция-граф шыңы, ал байланыстыру жолы-қабырғаны білдіреді. 5-суреттегі граф М,А,Б,В,Г аралықтарындағы кент жолдарының схемасы көрсетілген. Мұнда әрбір 2 шың қабырғамен байланысады. Мұндай графты толық граф деп атайды. 5-суреттегі сандар кент жолдағы арақашықты көрсетеді. М-кентінде пошта және пошташы қалған 4 кентке хат тарату керек. Жол жүруге арналған әр түрлі маршруттар бар. Осылардың арасынан ең қысқасын қалай табамыз? Ең қысқасы бүкіл нұсқаларды нәтижелеу. Мұны істеуге жаңа граф (5-сурет) ондағы мүмкін маршруттарды жеңіл мүмкіншілікті көретіндей. М-шыңының үстінде –маршруттар бастамасы. Одан А-ға, Б-ға, В-ға немесе Г-ға осындай тәсілмен жол бастауға болады. Біреуін қолданған соң ақырында 3-маршрутты жалғастырудың 3 мүмкіндігі қалады, одан кейін 2, содан соң ең соңғы кент және қайтадан М-кентіне оралды.. Барлығы 4*3*2*1=24 тәсіл. Олардың барлығы осы графта көрсетілген. Кент аралығын білдіретіндей қабырғаларына сандар қоямыз, соңына әрбір маршруттың соммасын жазамыз. Осыдан шыққан 24 санына екіншісі 2 сан 28 км-ден, М-В-Б-А-Г-М және М-Г-А-Б-В-М маршруттарына сәйкес келеді. Бұл бірдей жол, бірақ әр түрлі бағытта жүрілген. жүктеу/скачать 5,71 Mb. Достарыңызбен бөлісу:
|