| Lesson Code | Course Name | Class | Credit | Lesson Time | Weekly Lesson Hours (Theoretical) | Weekly Lesson Hours (Practice) | Weekly Class Hours (Laboratory) |
|---|---|---|---|---|---|---|---|
| GNA 3377 | Basic algorithms in graphs | Үшінші курс | 5 | 150 | 15 | 30 |
The purpose of the discipline: to acquaint students with the basic concepts of graph theory and bring them to a state in which they can be used; to master the methods of solving and setting problems in graph theory; to master the basic graph-theoretical algorithms; to study applied problems in various fields from the point of view of graph theory.
critical thinking, brainstorming, exchange of views, discussion, problem methods.
| 1 | knows the basic concepts of graph theory, types of graphs and their representation methods |
| 2 | Can use algorithms to search for shortest paths in graphs and find 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 |
| 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, find the optimal coloring of the graph. |
| Haftalık Konu | Evaluation Method | |
|---|---|---|
| 1 | History of graph theory. Adjacency. Graphs and similar objects. Isomorphism of graphs. Valence. | |
| 2 | Ways to represent graphs. Operations on graphs. | |
| 3 | Number of graphs. Subgraphs. Types of graphs. | |
| 4 | Routes, chains, cycles. Determination of route numbers. Determining the existence of routes and loops. | |
| 5 | Metric characteristics of a graph. Circumventing the graph. | |
| 6 | Communication components. Connectivity in graphs and orgraphs. Condensation creation algorithm. Identify the base and antibase. | |
| 7 | Streams on the network. 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 | The spanning trees. 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 (circuit). 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 | Plane 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 | PÇ13 | PÇ14 | PÇ15 |
|---|
| 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 |