| Сабақтың коды | Курс аты | Сынып | Академиялық кредит | Cағат | Апталық сабақ сағаттары (лекция) | Апталық сабақ сағаттары (практика) | Апталық сабақ сағаттары (зертханалық) |
|---|---|---|---|---|---|---|---|
| GT 3201 | Графтар Теориясы | Үшінші курс | 5 | 150 | 1 | 2 | 2 |
Білім алушыларды графтар теориясының негізгі ұғымдарымен таныстыру және оларды қолдана алатын жағдайға жеткізу; графтар теориясында есептердің қойылымы мен оларды шешу әдістерін меңгерту; негізгі теориялық-графтық алгоритмдерді игерту; түрлі салалардағы қолданбалы есептерді графтар теориясы тұрғысынан зерттеу.
---
Дискретті математика.
баяндау, пікір алмасу, пікірталасу, проблемалық әдістер.
| 1 | Графтар теориясының негізгі ұғымдарын, графтардың түрлерін және оларды беру тәсілдерін біледі. |
| 2 | Графтардағы ең қысқа жолдарды іздеу және желідегі максималды ағынды табу алгоритмдерін түсінеді. |
| 3 | Ағаш ұғымы мен ағаштардың қасиеттерін біледі. |
| 4 | Эйлерлік және гамильтондық циклдер ұғымдарын және олардың бар болу шарттарын біледі. |
| 5 | Планарлық және жазық графтар ұғымдарын, графтың планарлық болуының қажетті және жеткілікті шарттарын, графтың хроматикалық санын бағалау әдістерін біледі. |
| 6 | Графтарды беру тәсілдерін қолданады. |
| 7 | Графтардағы ең қысқа жолдарды табу мәселелерін шешудің классикалық алгоритмдерін қолданады және олардың модификацияларын жасайды. |
| 8 | Ең аз салмақты қаңқалы ағаш құра біледі. |
| 9 | Графтарда эйлерлік және гамильтондық циклдерді таба біледі. |
| 10 | Жазықтыққа планарлық графты жатқыза біледі, графтың планарлық болып табылатындығын анықтай алады, графтың оңтайлы бояуын табады. |
| Haftalık Konu | Бағалау әдісі | |
|---|---|---|
| 1 | Графтар теориясының тарихы. Сыбайластық. Графтар және оған ұқсас нысандар. Графтар изоморфизмы. Валенттілік. | |
| 2 | Графтарды беру жолдары. Графтарға қолданылатын амалдар. | |
| 3 | Графтар саны. Ішкі графтар. Графтар түрлері. | |
| 4 | Маршруттар, шынжырлар, циклдер. Маршруттардың сандарын анықтау. Маршруттар мен циклдердің бар болуын анықтау. | |
| 5 | Графтың метрикалық сипаттамалары. Графты айналып өту. | |
| 6 | Байланыстық компоненттері. Графтардағы және орграфтардағы байланыстық. Конденсация құру алгоритмы. Базаны және антибазаны анықтау. | |
| 7 | Желідегі ағындар. Форд-Фалкерсон теоремасы. Максималды ағынды табу алгоритмы. | |
| 8 | Салмақталған графтардағы ең қысқа жолдар. Ең қысқа жолдарды табу есебінің қойылуы. Дейкстра алгоритмы. Форд-Беллман алгоритмы. | |
| 9 | Ағаштар және олардың қасиеттері. Ағаштар центроиды. Прюфер коды. | |
| 10 | Ағаштардағы есептер. Қанқалы ағаштарды тізбектеу. Қанқалы ағаштарды санау. | |
| 11 | Минималды қанқалар. Краскал алгоритмы. Прим алгоритмы. Бағытталған, реттелген және бинарлы ағаштар. | |
| 12 | Фундаменталды циклдер және фундаменталды қималар жүйелері. Тәуелсіз циклдер жиыны. Фундаменталды циклдерді құру алгоритмы. Тәуелсіз қималар жиыны. Фундаменталды қималарды құру алгоритмы. | |
| 13 | Эйлерлік циклдер (шынжырлар). Эйлерлік циклдердің бар болуының қажетті және жеткілікті шарттары. Эйлерлік циклдерді табу алгоритмы. Гамильтондық циклдер. Гамильтондық циклдің бар болуының жеткілікті шарттары. Гамильтондық циклдерді табу алгоритмы (алгебралық әдіс). | |
| 14 | Төбелердің тәуелсіз (ішкі орнықтылық) жиыны ұғымы. Максималды тәуелсіз жиындарды іздеу алгоритмы. Төбелердің доминдеуші (сыртқы орнықтылық) жиыны ұғымы. Минималды доминдеуші жиындарды іздеу алгоритмы. | |
| 15 | Жазық графтар. Планарлы графтар. Графты жазықтыққа жатқызу алгоритмы. Графтың хроматикалық саны. Графты бояу алгоритмдері. |
| PÇ1 | PÇ2 | PÇ3 | PÇ4 | PÇ5 | PÇ6 | PÇ7 | PÇ8 | PÇ9 | PÇ10 | PÇ11 | PÇ12 |
|---|
| Оқулық / Материал / Ұсынылатын ресурстар | ||
|---|---|---|
| 1 | Ә.С.Төлеп, Б.И.Ескараева. Графтар теориясы. Оқу құралы. -Түркістан, 2019. -115 б. | |
| 2 | Ә.С. Төлеп, Б.И. Ескараева. Дискретті математика. Теория және практикум. -Шымкент, 2020. -132 б. | |
| 3 | Абильдаева Г.Б. Дискретті математика: Электрондық оқулық. - Қарағанды: ҚарМТУ, 2017 |