| 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 |
To acquaint students with the basic concepts of graph theory and bring them to a position where they can apply them; to master the presentation of problems in graph theory and methods for solving them; to master the main theoretical-graph algorithms; to study applied problems in various fields from the point of view of graph theory.
---
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. |