| Lesson Code | Course Name | Class | Credit | Lesson Time | Weekly Lesson Hours (Theoretical) | Weekly Lesson Hours (Practice) | Weekly Class Hours (Laboratory) |
|---|---|---|---|---|---|---|---|
| GT 3201 | Graph Theory | Үшінші курс | 5 | 150 | 1 | 2 | 2 |
Aimed at introducing students to the basics of graph theory and network analysis. As a result of studying the subject, students will get practical skills to work with the Python NetworkX library to analyze and visualize social graphs. The acquired competences can be used by advertising and public relations specialists to monitor the information field and plan communication campaigns.
---
Discrete Mathematics
Narrative, exchange of ideas, discussion, problem methods.
| 1 | Knows the basic concepts of graph theory, types of graphs and their representation methods. |
| 2 | Understands the algorithms of searching for the shortest paths in graphs and finding the maximum flow in the network. |
| 3 | Knows the concept of trees and the properties of trees. |
| 4 | Knows the concepts of Eulerian and Hamiltonian cycles and the conditions of their existence. |
| 5 | Knows the concepts of planar and planar graphs, necessary and sufficient conditions for a graph to be planar, methods of estimating the chromatic number of a graph. |
| 6 | Uses methods of providing graphs. |
| 7 | Uses classic algorithms for solving problems of finding the shortest paths in graphs and makes their modifications. |
| 8 | Able to create the smallest weight frame wood. |
| 9 | Can find Eulerian and Hamiltonian cycles in graphs. |
| 10 | Can relate a planar graph to a plane, determine whether the graph is planar, find the optimal coloring of the graph. |
| Haftalık Konu | Evaluation Method | |
|---|---|---|
| 1 | History of graph theory. Complicity. Graphs and similar objects. Isomorphism of graphs. Valence. | |
| 2 | Ways to transfer graphs. Operations on graphs. | |
| 3 | Number of graphs. Internal graphs. Types of graphs. | |
| 4 | Routes, chains, cycles. Determination of route numbers. Determining the existence of routes and loops. | |
| 5 | Metric characteristics of a graph. Traversing the graph. | |
| 6 | Communication components. Connectivity in graphs and digraphs. Condensation creation algorithm. Identify the base and antibase. | |
| 7 | Online streams. Ford-Falkerson theorem. Algorithm for finding the maximum flow. | |
| 8 | Shortest paths in weighted graphs. Calculation of finding the shortest paths. Dijkstra's algorithm. Ford-Bellman algorithm. | |
| 9 | Trees and their properties. Centroid of trees. Prufer code. | |
| 10 | Problems in trees. Chaining of gnarled trees. Counting gnarled trees. | |
| 11 | What is the minimum. Kraskal's algorithm. Prim's algorithm. Directed, ordered and binary trees. | |
| 12 | Fundamental cycles and systems of fundamental sections. A set of independent cycles. Algorithm for creation of fundamental cycles. A set of independent sections. Algorithm for creation of fundamental sections. | |
| 13 | Euler cycles (chains). Necessary and sufficient conditions for the existence of Euler cycles. Algorithm for finding Euler cycles. Hamiltonian cycles. Sufficient conditions for the existence of a Hamiltonian cycle. Algorithm for finding Hamiltonian cycles (algebraic method). | |
| 14 | The concept of an independent (internal stability) set of vertices. Algorithm for searching maximally independent sets. The concept of a dominating (external stability) set of peaks. Algorithm for searching minimal dominating sets. | |
| 15 | Planar graphs. Planar graphs. Algorithm for mapping a graph to a plane. Chromatic number of a graph. Graph coloring algorithms. |
| PÇ1 | PÇ2 | PÇ3 | PÇ4 | PÇ5 | PÇ6 | PÇ7 | PÇ8 | PÇ9 | PÇ10 | PÇ11 | PÇ12 |
|---|
| Textbook / Material / Recommended Resources | ||
|---|---|---|
| 1 | A. Tolep, B. Yeskarayeva. Graph theory. Educational tool. - Turkestan, 2019. - 115 p. | |
| 2 | A.Tolep, B. Yeskarayeva. Discrete mathematics. Theory and practice. -Shymkent, 2020. -132 p. | |
| 3 | Abildayeva G. Discrete Mathematics: An Electronic Textbook. - Karaganda: KMTU, 2017. | |
| 4 | Shevelev Yu. Discrete mathematics: textbook. - 4th edition, st. - St. Petersburg: Lan, 2022. |