|
1 |
Title of discipline |
Discrete mathematics and graph theory |
|
2 |
Year of study |
2, Specialty “Mathematics (scientific and design activities)” |
|
3 |
Semester of study |
3 |
|
4 |
Number of credits |
3 |
|
5 |
Full name of lecturer |
Candidate of physical and mathematical sciences, Associate Professor Metelsky Yury Mikhailovich |
|
6 |
Objectives of studying the discipline |
Acquaintance with the problems and methods of discrete mathematics. Forming the skills of discrete mathematical thinking and the ability to apply it in solving specific problems. |
|
7 |
Prerequisites |
Initial information from the theory of mappings, set theory and linear algebra |
|
8 |
Content of discipline |
Initial concepts of graph theory. Isomorphism. Routes, connected components. Breadth first search. Bipartite graphs. Trees and skeletons. Equivalent definitions of trees. Kirchhoff’s theorem on the number of spanning trees. Skeletons of minimum weight. Independence and covers in graphs. Hall’s theorem on matchings in bipartite graphs. The numbers of vertex and edge connectivities of a graph. Two-connected graphs. Menger’s theorem on vertex separators. Traversals of graphs. |
|
9 |
Recommended literature |
1. Zuev Yu.A. On the ocean of discrete mathematics: From enumerative combinatorics to modern cryptography. In 2 volumes. Moscow: Book House “Librokom”, 2012. (in Russian) |
|
10 |
Teaching methods |
Reproductive (passive), visual, comparative, dialog-heuristic, problem, research |
|
11 |
Language of study |
Russian |
|
12 |
Current test activities |
Theoretical colloquiums, written test works |
|
13 |
Type of current certification |
Test |