Some classes of graphs. Union, join and complement graph operations.
Trees, binary trees.
BFS and DFS algorithms.
Vector spaces of the graph.
n-connectivity of graphs.
Eulerian graphs. Hamiltonian Graphs.
Planar graphs, the characterization of planar graphs .
Covers, independence and domination.
System of distinct representatives, Hall’s Theorem, the perfect maching of the bipartite graph.
CLASSES
Application of fundamental counting rules in exercises.
Application of Inclusion-Exclusion principle in exercises.
Proving combinatorial identities.
Solving recurrence relations by characteristic equations or by induction.
Basic graph theory notation. Graph matrices and other kinds of graph representations. Basic graph operations.
Properties of trees, counting labelled trees. BFS, DFS-algorithm, fundamental circuits and fundamental bonds.
Connectivity of graphs.
Algorithms for determining Eulerian and Hamiltonian cycles. Properties of Eulerian and Hamiltonian graphs.
Euler’s Theorem and Kuratowski’s Theorem for planar graphs.
Independence number, covering number, domination number in graphs
Applications of Hall’s Thorem.
Teaching methods
Learning outcomes and methods of theirs verification
Outcome description
Outcome symbols
Methods of verification
The class form
Assignment conditions
Class. The final grade is issued on the points obtained during the classes and activity during the classes.
Lecture. The final grade is issued on the points of the final test.
Final course grade.The final grade consists of the class grade (50%) and the class grade (50%). The condition of passing the subject is a positive grade from both: the class and the lecture.
Recommended reading
V. Bryant, Aspects of Combinatorics, Cambridge University Press, 2000.
