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. |