График V төбелерінің ақырлы жиыны және төбелердің жұптарын қосатын R жиектерінің жиыны, G=(V,R). V және R жиындарының кардиналиттері N және M-ге тең. Жиектер жиыны бос болуы мүмкін. Төбелердің мысалдары кез келген сипаттағы объектілер (елді мекендер, компьютерлік желілер). Шеттердің мысалдары - жолдар, бүйірлер, сызықтар.
Жиекпен қосылған шыңдар іргелес деп аталады. Ортақ төбесі бар жиектерді іргелес деп те атайды. Шет және оның екі төбесінің кез келгені оқиға деп аталады. Төбенің дәрежесі - оған түсетін шеттердің саны. Әрбір графикті жазықтықта төбелеріне сәйкес нүктелер жиыны арқылы көрсетуге болады, олар жиектерге сәйкес түзулер арқылы қосылған.
График жолы – бұл шыңдар мен жиектер тізбегі. Бастапқы және соңғы шыңдары бірдей болса, маршрут жабық (циклдік). Барлық шыңдар мен жиектер әр түрлі болса, маршрут қарапайым жол болып табылады. Әрбір төбеге кез келген басқа нүктеден жетуге болатын болса, график қосылған. Оқшауланған шеттері жоқ шыңдар деп аталады.
Оқиға матрицасы
Байланыс тізімдері
Қабырғалардың тізімі
Графиктің байланысқан өлшенген бағытталмаған графының іргелес матрицасы
Ең аз салмақтағы жалғанған ағаштың құрылысы. Крускаль алгоритмі Графиктен барлық шеттер жойылып, барлық төбелер оқшауланған ауқымды субграф алынады. Әрбір шың синглтон ішкі жиынына орналастырылады. Жиектер салмақтардың өсу реті бойынша сұрыпталады. Жиектер салмақтарының өсу ретімен тізбектеліп, созылатын ағашқа кіреді.
4 жағдай бар: 1) енгізілген жиектің екі төбесі бір элементті ішкі жиындарға жатады, содан кейін олар жаңа, қосылған ішкі жиынға біріктіріледі; 2) төбелердің бірі жалғанған ішкі жиынға жатады, ал екіншісі жатпайды, онда екіншісін біріншісі жататын ішкі жиынға қосамыз; 3) екі төбе де әр түрлі қосылған ішкі жиындарға жатады, онда ішкі жиындарды біріктіреміз; 4) Екі төбе де бір қосылған ішкі жиынға жатады, онда бұл жиекті алып тастаймыз.
GG графигі үшін ең аз салмақты аралық ағашты құру мысалы Орындалған әрекеттер Төбелер жиыны 1-график Оқшауланған және төбелері бар ауқымды ішкі графты тұрғызамыз Біз 5 жалғыз ішкі жиынды аламыз: (V 1 ), (V 2 ), (V 3 ), (V 4 ), (V 5 ) 2Ең кіші салмақтың жиегін (R 15) табыңыз және оны кеңейтілген ішкі графаға қосыңыз Шыңдардың қосылған ішкі жиынын жасаңыз: (V 1,V 5 ). Ішкі жиындарды сақтау (V 2 ), (V 3 ), (V 4 )
Орындалған әрекеттер Төбелер жиыны 3-график Қалғандардың ішінен ең аз салмақтың жиегін (R 45) тауып, оны таралатын ішкі графқа қосыңыз.Шыңды қосылған ішкі жиынға қосыңыз: (V 1,V 5, V 4 ). Ішкі жиындарды (V 2 ), (V 3 ) 4Қалғандардың ішінен ең аз салмақтың жиегін (R 23) табыңыз және оны аралық графаға қосамыз Жаңа қосылған шыңдар жиынын жасаңыз: (V 2,V 3 ) . Біз бірінші қосылған ішкі жиынды сақтаймыз (V 1,V 5, V 4 ).
Орындалған әрекеттер Төбелер жиыны 5-график Қалғандардың ішінен ең аз салмақтың жиегін (R 25) табыңыз және оны кеңейтілген ішкі графқа қосыңыз. Ішкі жиындарды бір қосылған ішкі жиынға біріктіріңіз (V 1,V 5, V 4,V 2,V 3 ). 6 Қалған жиектер графикке кірмейді, себебі олардың барлық шыңдары әлдеқашан бір қосылған жиынға жатады.
Орындалған әрекеттер Төбелердің жиыны График 7А графигі алынды, ол: ауқымды граф (барлық шыңдар қосылған); қосылған (барлық шыңдарды маршруттар арқылы қосуға болады); ағаш (циклдер жоқ); ең аз салмағы бар. 8Нәтижесінде пайда болған аралық ағаштың ең аз салмағы бар: R 12 +R 25 +R 15 +R 45 = =80 9 G графигінің циклдік саны γ=m-n+1=8-5+1=4, ол мынаған сәйкес келеді. ағашқа жатпайтын жиектер саны.
Айнымалы мәндерді жариялау График төбесінің координаттарын сақтауға арналған екі бес элементті бүтін X және Y массивтері График жиектерінің салмақтарын сақтауға арналған бүтін екі өлшемді R массиві Цикл есептегіштері үшін бүтін айнымалылар i, n және k Ағаш жиектерінің салмақтарының қосындысын сақтауға арналған бүтін айнымалы S S ең аз салмақ
Графиктің 5 төбесінің кездейсоқ координаталарын құру (i бойынша цикл). Жиектер салмағын есептеу. Салмақты диграфтың іргелес матрицасын шығару (n және k-дегі кірістірілген циклдар) Салмақты бағытталмаған графиктің іргелес матрицасын шығару – бастапқы матрица элементтерінің жартысы (бастапқы мән k=n+1) Бағдарлама денесі
Жабдық:
- заманауи технологиямен жабдықталған компьютерлік сынып, видеопроектор, экран;
- Windows XP, Microsoft Office 2003 PowerPoint бағдарламасы бар компьютерлер;
- тақта жабдығы (сабақ тақырыбы, жаңа терминдер). Үлестірмелі материал.
Сабақ жоспары.
II. Жаңа материалды таныстыру. (10 мин.)
III. Материалды бекіту. Практикалық жұмыс. (15-20 мин.)
IV. Сабақты қорытындылау (2 мин)
V. Үйге тапсырма.
I. Ұйымдастыру кезеңі. Білімді жаңарту.
Сәлеметсіз бе! Сабағымыз «Графиктер» деп аталады. Біз «Графиктер» ұғымымен танысамыз, оларды бейнелеуді және осы тақырып бойынша есептерді шығаруды үйренеміз.
II Жаңа материалды таныстыру.
Графтар теориясы бойынша алғашқы еңбек Леонхард Эйлерге (1736) тиесілі, дегенмен «граф» терминін алғаш рет 1936 жылы венгр математигі Денеш Коениг енгізген. Графиктер нүктелер мен түзулердің кесінділерінен немесе осы нүктелерді қосатын қисықтардан тұратын схемалар деп аталды (графиктердің мысалдары 1-суретте көрсетілген).
Графиктердің көмегімен білімнің әртүрлі салаларында тұжырымдалған есептерді шешу жиі жеңілдетілді: автоматика, электроника, физика, химия және т.б. Графиктердің көмегімен жолдардың, газ құбырларының, жылу және электр желілерінің диаграммалары бейнеленген. . Графиктер математикалық және экономикалық есептерді шешуге көмектеседі.
График – (грек тілінен grapho – жазамын) – объектінің элементтерін олардың арасындағы байланыстарды көрнекі түрде бейнелеу құралы. Бұл тамаша математикалық объектілер, олардың көмегімен сіз көптеген әртүрлі, сырттай ұқсамайтын есептерді шеше аласыз.
График - бұл қандай да бір ақпараттық модель
График доғалармен немесе сегменттермен - жиектермен қосылған шыңдардан немесе түйіндерден тұрады. Сызықты бағыттауға болады, яғни көрсеткі (доға), егер бағытталмаған болса - жиегі бар. Доға немесе жиек арқылы қосылған екі төбе іргелес деп аталады.
График мысалдары (Слайд 4, 5, 6)
1-тапсырма (7-слайд):
Күн жүйесінің тоғыз планетасы арасында ғарыштық байланыс орнатылды. Тұрақты зымырандар келесі бағыттар бойынша ұшады:
Жер - Меркурий; Плутон - Венера; Жер - Плутон; Плутон - Меркурий; Меркурий - Венера; Уран - Нептун; Нептун - Сатурн; Сатурн - Юпитер; Юпитер - Марс; Марс - Уран.
Жерден Марсқа тұрақты зымыранмен ұшу мүмкін бе?
Шешуі: Шарттың сызбасын саламыз: планеталарды нүктелермен, ал зымырандардың жүру жолдарын сызықтармен бейнелейміз.
Енді Жерден Марсқа ұшу мүмкін емес екені бірден белгілі болды.
Доға немесе жиек арқылы қосылған екі төбе іргелес деп аталады. Әрбір жиек немесе доға санмен байланысты. Сан елді мекендер арасындағы қашықтықты, бір шыңнан екіншісіне өту уақытын және т.б.
2-тапсырма (9-слайд) – шешімі тақтада. Маша хайуанаттар бағына келді және мүмкіндігінше көп жануарларды көргісі келеді. Ол қай жолмен жүруі керек? Сары, қызыл, жасыл?
3-тапсырма (11 слайд) – шешімі тақтада. A, B, C, D, E бес футбол командасы бір-бірімен матч ойнауы керек. Қазірдің өзінде B, C, D-мен A ойнады; B c A, C, D. осы уақытқа дейін қанша матч ойналды? Ойынға қанша қалды?
Графикті көрсету (12-слайд)
График доғалар тізімі (AB; 7) түрінде графикалық түрде немесе кесте арқылы көрсетілуі мүмкін.
| Арк тізімдері | Графикалық пішін | кестелік пішін | ||||||||||||||||
| (AB; 7), |  |
|
III. Материалдарды бекіту: оқушылар топқа бөлініп, тапсырмаларды орындауға шақырылады. Шағын топта жұмыс істей отырып, оқушылар сабақтың басында алған теориялық білімдері негізінде модельдерді талқылайды. Осылайша материалды қайталау мен бекітуге қол жеткізіледі.
2-тапсырма (13-слайд)
IV. Сабақты қорытындылау
Балалар, бүгін қандай жаңа сөздермен таныстыңдар? (Санау, график төбесі, граф жиектері.)
Графиктің төбелері нені бейнелей алады? (Қалалар; байланысқан объектілер.)
Графиктің шеттері нені білдіреді (жолдар, қозғалыстар, бағыттар)
Оларды өмірде қай жерде кездестіруге болатынына мысал келтіріңіз?
Графиктер қалай көрсетіледі?
V. Үйге тапсырма. (15-слайд)
1 слайд
2 слайд
Графтар теориясының негіздері алғаш рет Леонгард Эйлердің (1707-1783; швейцариялық, неміс және орыс математигі) еңбектерінде пайда болды, онда ол басқатырғыштар мен математикалық ойын-сауық есептерін шешуді сипаттады. График теориясы Эйлердің Кенигсбергтің жеті көпірі мәселесін шешуінен басталды.
3 слайд
Ұзақ уақыт бойы Кенигсберг тұрғындары арасында мұндай жұмбақ тарады: олардың ешқайсысынан екі рет өтпей, барлық көпірлерден (Преголя өзені арқылы) қалай өтуге болады? Көбісі серуендеу кезінде бұл мәселені теориялық және практикалық тұрғыдан шешуге тырысты. Бірақ мұны ешкім жасай алмады, бірақ оның тіпті теориялық тұрғыдан мүмкін емес екенін ешкім дәлелдей алмады. Жеңілдетілген диаграммада қаланың бөліктері (графигі) сызықтары бар көпірлерге (график доғалары), ал қаланың бөліктері сызықтардың қосылу нүктелеріне (график шыңдары) сәйкес келеді. Ойлау барысында Эйлер мынадай қорытындыға келді: Олардың ешқайсысынан екі рет өтпей, барлық көпірлердің үстінен өту мүмкін емес.
4 слайд
Қанның 4 түрі бар. Бір адамнан екінші адамға қан құйылған кезде барлық топтар сәйкес келмейді. Бірақ сол топтар адамнан адамға қан құюға болатыны белгілі, т. 1 - 1, 2 - 2 және т.б. Сондай-ақ 1-топты барлық басқа топтарға, 2 және 3-топтарды тек 4-топқа құюға болады. Тапсырма.
5 слайд
6 слайд
Графиктер График – графикалық түрде берілген ақпараттық модель. График – бұл шеттермен қосылған шыңдардың (түйіндер) жиынтығы. Алты төбесі және жеті қыры бар график. Төбелер жиекпен жалғанса, іргелес деп аталады.
7 слайд
Бағытталған графиктер – диграфтар Әр жиектің бір бағыты бар. Мұндай жиектер доғалар деп аталады. Бағытталған график
8 слайд
Салмақталған график Бұл жиектеріне немесе доғаларына сандық мәндер тағайындалған график (олар, мысалы, қалалар арасындағы қашықтықты немесе тасымалдау құнын көрсете алады). Графиктің салмағы оның шеттерінің салмақтарының қосындысына тең. Кесте (ол салмақ матрицасы деп аталады) графикке сәйкес келеді. 1 2 4 2 3 A B C D E
9 слайд
Тапсырма А, В, С, Г, Е, Ф елді мекендері арасында жолдар салынады, олардың ұзындығы кестеде келтірілген. (Кестеде санның болмауы нүктелер арасында тура жолдың жоқтығын білдіреді). А және F нүктелері арасындағы ең қысқа жолдың ұзындығын анықтаңыз (тек салынған жолдар бойымен қозғалуға болады деп есептей отырып). 1) 9 2) 10 3) 11 4) 12
10 слайд
1. 2. 3. 4. 5. A-B-C-E-F ең қысқа жолының ұзындығы 9 2 4 2 4 7 1 2 4 7 1 3 4 2 4 7 1 3 4 3 2 4 7 1 3 4 3 2
Коробова Анастасия, студент гр. 14-PGS-48D
Біздің уақытымызда әртүрлі әдістерді, қасиеттерді және стандартты емес қолданбаларды зерттеу маңызды. «График» әдісін қоршаған шындықта қолдануды қарастырамыз.
Математикадағы «граф» сөзі бірнеше нүктелер сызылған, олардың кейбіреулері сызықтармен жалғанған суретті білдіреді. Ең алдымен, талқыланатын графтардың бұрынғы ақсүйектерге еш қатысы жоқ екенін айта кеткен жөн. Біздің «графтар» гректің «grapho» сөзінен шыққан, «мен жазамын» дегенді білдіреді. «График», «өмірбаян» сөздеріндегі бір түбір.
Графтар теориясы бойынша алғашқы еңбек Леонгард Эйлерге тиесілі және ол 1736 жылы Петербург Ғылым академиясының басылымдарында пайда болды.
Есептер кездеседі:
физикада – электр тізбектерін құруда
химия мен биологияда – олардың тізбектерінің молекулаларын зерттеуде
тарихта - отбасылық ағаштарды құрастыру кезінде (тектік)
географияда – картаға түсіруде
геометрияда – көпбұрыштар, көпжақтар, кеңістік фигуралар сызбалары
экономикада – жүк көлігі ағындарының оңтайлы жолын таңдау мәселелерін шешу кезінде (әуе, метро, темір жол)
Графикалық теория математикалық олимпиада тапсырмаларын шешуде қолданылады. Графиктер есеп шартының көрнекілігін береді, шешуді жеңілдетеді, есептердің ұқсастығын ашады.
Қазір ғылым мен техниканың кез келген саласында графиктерді кездестіресіз.
Жүктеп алу:
Алдын ала қарау:
Презентацияларды алдын ала қарау мүмкіндігін пайдалану үшін Google есептік жазбасын (есептік жазбасын) жасаңыз және келесіге кіріңіз: https://accounts.google.com
Слайдтар тақырыбы:
Математикадан презентация Тақырыбы: «Графиктер» Орындаған 14-ПГС-48Д тобының студенті Коробова Анастасия
График - бұл нүктелер мен осы нүктелерді қосатын түзулерден тұратын фигура. Сызықтар графтың шеттері, ал нүктелер шыңдары деп аталады. Шеттерінің жұп саны шығатын төбелер жұп, тақ сан тақ деп аталады. Графиктердің графикалық теориясының мысалдары
Леонхард Эйлер ( 4 сәуір 1707 , Базель , Швейцария — 7 қыркүйек 1783 , Санкт-Петербург , Ресей империясы ) — математиканың дамуына зор үлес қосқан швейцариялық, неміс және орыс математигі, сонымен қатар механика, физика, т.б. астрономия және бірқатар қолданбалы ғылымдар. Эйлер математикалық талдау, дифференциалдық геометрия, сандар теориясы, жуық есептеулер, аспан механикасы, математикалық физика, оптика, баллистика, кеме жасау, музыка теориясы және т.б. бойынша 800-ден астам еңбектердің авторы.
Қағаздан қарындашты көтермей салуға болатын фигура (график) біркурстық деп аталады. Үлгі 1. Тек екі тақ төбесі бар графикті қағаздан қарындашты көтермей-ақ салуға болады, бұл ретте қозғалыс осы тақ төбелердің бірінен басталып, екіншісінде аяқталуы керек. (A-сурет) 2-үлгі. Екіден көп тақ төбелері бар графикті «бір штрихпен» салу мүмкін емес (В-сурет) Эйлер графиктері B A
Үлгі 3. Егер графтың барлық төбелері жұп болса, онда қарындашты қағаздан көтермей, әр жиегін бір рет қана сызып, осы графикті сызыңыз. Қозғалыс кез келген шыңнан басталып, оны бір шыңда аяқтай алады.
Ұзақ уақыт бойы Кенигсберг тұрғындары арасында мұндай жұмбақ тарады: олардың ешқайсысынан екі рет өтпей, барлық көпірлерден (Преголья өзені арқылы) қалай өтуге болады? Көбісі серуендеу кезінде бұл мәселені теориялық және практикалық тұрғыдан шешуге тырысты. Кенигсберг көпірлерінің мәселесі.
Бұл кейбір жиектер бағытталған, ал кейбіреулері бағытталмаған болуы мүмкін график. Аралас санау
Салмақталған график 1 2 4 2 3 A B C D E
Ағаш - циклдері жоқ кез келген байланыстырылған график. Ағаштар Ағаштар
Бұл жиектеріне бағыт тағайындалған (көп) график. Бағытталған жиектер доғалар деп те аталады. Бағытталған график
Есептер кездеседі:
Графикалық теория математикалық олимпиада тапсырмаларын шешуде қолданылады. Графиктер есеп шартының көрнекілігін береді, шешуді жеңілдетеді, есептердің ұқсастығын ашады. Қазір ғылым мен техниканың кез келген саласында графиктерді кездестіресіз.
Назарларыңызға рахмет!