Математикада?ы граф ??ымы.

Математикада?ы граф ??ымы

Е? алдымен с?з болып отыр?ан графты?, б?рын?ы кездегі аристократтар?а еш?андай ?атысы жо? екенін айта кеткен ж?н болар. Бізді? «графты?» т?бір с?зі «графо» деген с?зден шы??ан, ол «жазамын» дегенді білдіреді. Граф теориясы математиканы? логика, комбинаторика, та?ы бас?а салаларында ?олданылады.

Графтар теориясына байланысты ал?аш?ы е?бекті жаз?ан Леонард Эйлер (1736 жыл) болды, біра? «граф» терминін 1936 жылы венгр математигі Денеш Кениг енгізді. Б?дан 100 жыл ?ткен со?, ?сіресе, Англияда жаратылыстану ?ылымыны? барынша ?р т?рлі формада?ы саласында графтар теориясы ?олданыла бастады. Электр тізбегі мен кристалл моделін молекуланы? структурасын зерттеуге, сондай-а? ойындар теориясы мен программалауда, биология мен психологияда ке?інен ?олданылды.

Математикада граф т?белері деп аталатын а?ырлы н?ктелер жиынынан т?рады; олар бір-бірімен граф ?абыр?алары деп аталатын сызы?тармен ?осыл?ан. ?абыр?амен ?осыл?ан екі т?бе сыбайлас деп аталады. Граф т?бесінен шы??ан ?абыр?алар санын т?бені? д?режесі деп атайды. Графтарды мысал ар?ылы т?сіндірген о?ай.

1-мысал: Серік, Айдар, Досан, Жандос ж?не Марат бір-бірімен ?ол алысты. Барлы?ы неше ?ол алысу болды?

Айталы? ?рбір бала?а жазы?ты?та?ы ?з атыны? бірінші ?рпімен белгіленген бір н?ктені с?йкес ?ояйы?, ал ?ол алыс?андарын кесінді немесе ?исы?пен ?осайы?.

5 т?бесі бар граф 5 т?белі толы? емес граф 5 т?белі толы? граф

А, С, Д, Ж ж?не М н?ктелері граф т?белері, б?л н?ктелерді ?осатын сызы?тар графты? ?абыр?алары деп аталады.

Шешуі: Толы? граф салын?ан суреттегі ?абыр?алар санын санаса?, ?ол алысуларды? санына те? болады. Ол 10?а те?.

1-суретте бір-бірімен о?шаулан?ан (изолированный) т?белерден т?ратын граф нольдік граф деп аталады, б?л ?ол алысу басталмай т?р?анда?ы схема. 2-суретте ?ол алысу толы? ая?талма?ан жа?дай?а с?йкес келетін схема, м?нда барлы? м?мкін ?абыр?алар салынба?ан, сонды?тан ол толы? емес граф деп аталады. 3-суретте барлы? м?мкін ?ол алысулар толы? біткенге с?йкес келетін схема, б?л граф толы? граф деп аталады.

3-суреттегі толы? графты? ?р т?бесіні? д?режесі – 4-ке те?. 2-суретте А, С, Д т?белеріні? д?режесі 2-ге, ал М ж?не Ж т?белеріні? д?режесі 1-ге те?.

Графтар?а т?н т?мендегідей за?дылы?тар?а то?талайы?:

Егер толы? графты? n т?бесі болса, онда ?абыр?алар саны те? болады.
Толы? графты? ?р т?бесіні? д?режесі бірдей болады ж?не оларды? ?р?айсысыны? саны граф т?бесіні? санынан 1-ге кем.
Графты? т?белеріні? д?режелеріні? ?осындысы графты? ?абыр?алар санын екі еселегенге те? болатын ж?п сан болады. Б?л кез келген граф ?шін д?рыс. Б?дан:
Кез келген графты? та? д?режелі т?белеріні? саны ж?п болады

1-есеп: Класта 30 адам бар. Оларды? 9-ны? осы класта 3-тен досы, 11-ні? 4-тен, 10-ны? 5-тен досы болуы м?мкін бе?

Шешуі: Егер м?мкін болса, онда 30 т?белі граф салып, оны? 9ы ?шінші д?режелі, 11і т?ртінші д?режелі, 10ы бесінші д?режелі болар еді. Онда б?л графты? 19 та? д?режелі т?белері бар болар еді. Б?л біз айтып кеткен за?дылы??а ?айшы.

Б?л за?дылы?тардан мынадай салдарлар шы?ады:

1-салдар: Кез келген топта?ы та? санды таныстарды? танысты?тарыны? саны ж?п болады

2-салдар: Та? санды ?ырлар т?йісетін к?пжа?ты? т?белер саны ж?п болады. (1–?осымшада?ы суреттен к?руге болады).

3-салдар: Бас?алармен та? санды рет ?ол алыс?ан адамдар саны ж?п болады.

2-есеп: 17 б?рышты? диагональдар саны ?анша?

Шешімі: 17 б?рышты? т?белері – графты? т?белері, ал ?абыр?алары мен диагональдары графты? ?абыр?алары болсын деп есептейміз. 17 т?белі граф барлы?ы 136 сызы?пен ?осыл?ан. Оны? 17сі ?абыр?а, ?ал?андары - диагональ. Онда диагональдары 136-17=119.

3-есеп: Марат пен Балн?р мынадай ойын ойнап отыр? Олар кезекпен 5 ба?анды ?ос-?остан бантпен байлайды. Кім со??ы ба?анда?ы ?осты бантпен байласа, сол же?еді. Ойынды бірінші баста?ан адам же?уі м?мкін бе?

Шешуі: Барлы?ы бантпен байлан?ан кезде 5 т?бесі бар толы? граф пайда болады. Б?л графты? ?абыр?асыны? саны 10. Олай болса, екінші байла?ан ойыншы же?еді.

4-есеп: Сарайда тама?ы бар 10 ыдыс пен 20 шош?а бар. Шош?алар бір ыдыстан екіншісіне барып ж?р. ?рбір ыдыстан бас?асына ?андай да бір шош?аны? келгені белгілі болса,е? болма?ан да бір шош?аны? 3тен кем емес келетінін д?лелде?дер.

Шешуі: Ыдыстарды графты? т?белері деп белгілейік. Оларды? т?белерін ?абыр?алармен ?осамыз, ?йткені ?рбір ыдыстан бас?асына шош?аны? келгені айтыл?ан. 10 т?белі толы? графта 45 ?абыр?а бар. Егер ?р ыдыстан бас?асына шош?алар екі рет барса, барлы?ы 40 ?абыр?а шы?ар еді. Олай болса, е? болма?анда бір шош?а ?ш рет келгені белгілі болады.

5-есеп: К?н ж?йесіні? 7 планетасы арасында ракеталы??атынас орнатыл?ан. Министр ?рбір планетадан бас?а 5 планета?а тура ?атынас бар деп айтты. Министрді? ?ателескенін д?лелде.

Шешуі: Планеталар – граф т?белері, ал ?атынастар – граф ?абыр?алары болсын. Егер министрді? с?зі шын болса, онда графты? та? д?режелі т?белеріні? саны та? болар еді. Ал олай болуы 4-інші за?дылы??а ?айшы.

6-есеп: (Эйлер есебі деп аталады) XVIII ?асырда Кенисберг (?азіргі Калининград) ?аласында т?р?ан ?зенге ?ала шетінде т?р?ан екі аралды байланыстыратын 7 к?пір салынды. ?рбір к?пірде біра? рет болып, барлы? 7 к?пірді басып ?тіп, маршрут бастал?ан жерге ?айта ?айтып келуге бола ма?

Показать полностью

Вы уже знаете о суперспособностях современного учителя?

Тратить минимум сил на подготовку и проведение уроков.

Быстро и объективно проверять знания учащихся.

Сделать изучение нового материала максимально понятным.

Избавить себя от подбора заданий и их проверки после уроков.

Наладить дисциплину на своих уроках.

Получить возможность работать творчески.

=> ПОЛУЧИТЬ СУПЕРСПОСОБНОСТИ УЧИТЕЛЯ <=

Просмотр содержимого документа
«математикада?ы граф ??ымы. »

Математикадағы граф ұғымы

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

Графтар теориясына байланысты алғашқы еңбекті жазған Леонард Эйлер (1736 жыл) болды, бірақ «граф» терминін 1936 жылы венгр математигі Денеш Кениг енгізді. Бұдан 100 жыл өткен соң, әсіресе, Англияда жаратылыстану ғылымының барынша әр түрлі формадағы саласында графтар теориясы қолданыла бастады. Электр тізбегі мен кристалл моделін молекуланың структурасын зерттеуге, сондай-ақ ойындар теориясы мен программалауда, биология мен психологияда кеңінен қолданылды.

Математикада граф төбелері деп аталатын ақырлы нүктелер жиынынан тұрады; олар бір-бірімен граф қабырғалары деп аталатын сызықтармен қосылған. Қабырғамен қосылған екі төбе сыбайлас деп аталады. Граф төбесінен шыққан қабырғалар санын төбенің дәрежесі деп атайды. Графтарды мысал арқылы түсіндірген оңай.

1-мысал: Серік, Айдар, Досан, Жандос және Марат бір-бірімен қол алысты. Барлығы неше қол алысу болды?

Айталық әрбір балаға жазықтықтағы өз атының бірінші әрпімен белгіленген бір нүктені сәйкес қояйық, ал қол алысқандарын кесінді немесе қисықпен қосайық.

5 төбесі бар граф 5 төбелі толық емес граф 5 төбелі толық граф

А, С, Д, Ж және М нүктелері граф төбелері, бұл нүктелерді қосатын сызықтар графтың қабырғалары деп аталады.

Шешуі: Толық граф салынған суреттегі қабырғалар санын санасақ, қол алысулардың санына тең болады. Ол 10ға тең.

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

3-суреттегі толық графтың әр төбесінің дәрежесі – 4-ке тең. 2-суретте А, С, Д төбелерінің дәрежесі 2-ге, ал М және Ж төбелерінің дәрежесі 1-ге тең.

Графтарға тән төмендегідей заңдылықтарға тоқталайық:

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

1-есеп: Класта 30 адам бар. Олардың 9-ның осы класта 3-тен досы, 11-нің 4-тен, 10-ның 5-тен досы болуы мүмкін бе?

Шешуі: Егер мүмкін болса, онда 30 төбелі граф салып, оның 9ы үшінші дәрежелі, 11і төртінші дәрежелі, 10ы бесінші дәрежелі болар еді. Онда бұл графтың 19 тақ дәрежелі төбелері бар болар еді. Бұл біз айтып кеткен заңдылыққа қайшы.

Бұл заңдылықтардан мынадай салдарлар шығады:

1-салдар: Кез келген топтағы тақ санды таныстардың таныстықтарының саны жұп болады

2-салдар: Тақ санды қырлар түйісетін көпжақтың төбелер саны жұп болады. (1–қосымшадағы суреттен көруге болады).

3-салдар: Басқалармен тақ санды рет қол алысқан адамдар саны жұп болады.

2-есеп: 17 бұрыштың диагональдар саны қанша?

Шешімі: 17 бұрыштың төбелері – графтың төбелері, ал қабырғалары мен диагональдары графтың қабырғалары болсын деп есептейміз. 17 төбелі граф барлығы 136 сызықпен қосылған. Оның 17сі қабырға, қалғандары - диагональ. Онда диагональдары 136-17=119.

3-есеп: Марат пен Балнұр мынадай ойын ойнап отыр? Олар кезекпен 5 бағанды қос-қостан бантпен байлайды. Кім соңғы бағандағы қосты бантпен байласа, сол жеңеді. Ойынды бірінші бастаған адам жеңуі мүмкін бе?

Шешуі: Барлығы бантпен байланған кезде 5 төбесі бар толық граф пайда болады. Бұл графтың қабырғасының саны 10. Олай болса, екінші байлаған ойыншы жеңеді.

4-есеп: Сарайда тамағы бар 10 ыдыс пен 20 шошқа бар. Шошқалар бір ыдыстан екіншісіне барып жүр. Әрбір ыдыстан басқасына қандай да бір шошқаның келгені белгілі болса, ең болмаған да бір шошқаның 3тен кем емес келетінін дәлелдеңдер.

Шешуі: Ыдыстарды графтың төбелері деп белгілейік. Олардың төбелерін қабырғалармен қосамыз, өйткені әрбір ыдыстан басқасына шошқаның келгені айтылған. 10 төбелі толық графта 45 қабырға бар. Егер әр ыдыстан басқасына шошқалар екі рет барса, барлығы 40 қабырға шығар еді. Олай болса, ең болмағанда бір шошқа үш рет келгені белгілі болады.

5-есеп: Күн жүйесінің 7 планетасы арасында ракеталық қатынас орнатылған. Министр әрбір планетадан басқа 5 планетаға тура қатынас бар деп айтты. Министрдің қателескенін дәлелде.

Шешуі: Планеталар – граф төбелері, ал қатынастар – граф қабырғалары болсын. Егер министрдің сөзі шын болса, онда графтың тақ дәрежелі төбелерінің саны тақ болар еді. Ал олай болуы 4-інші заңдылыққа қайшы.

6-есеп: (Эйлер есебі деп аталады) XVIII ғасырда Кенисберг (қазіргі Калининград) қаласында тұрған өзенге қала шетінде тұрған екі аралды байланыстыратын 7 көпір салынды. Әрбір көпірде бірақ рет болып, барлық 7 көпірді басып өтіп, маршрут басталған жерге қайта қайтып келуге бола ма? (Суретін 2- қосымшадан көруге болады).