The course introduces advance notions and ideas of discrete mathematics in theoretic and algorithmic aspects.
Wymagania wstępne
Discrete Mathematics 1
Zakres tematyczny
LECTURE/CLASSES
Selected classes of graphs: interval graphs, chordal graphs, edge graphs, k-trees, their properties, and applications.
Various types of domination in graphs.
Graph coloring (classic, from a list), theorems by Brooks, Szekeres-Wilf, Vizing, Thomassen.
Digraphs, definitions, and notations.
Strongly connected digraphs, transitive, acyclic, their properties.
Selected digraph algorithms.
Metody kształcenia
Traditional lecture; auditory exercises where students solve problems.
Efekty uczenia się i metody weryfikacji osiągania efektów uczenia się
Opis efektu
Symbole efektów
Metody weryfikacji
Forma zajęć
Warunki zaliczenia
Conditions for passing classes and lectures:
Checking students' level of preparedness and their activity during exercises.
A test with tasks of varying difficulty levels, allowing assessment of whether and to what extent a student has achieved the mentioned learning outcomes, mainly in terms of skills and competencies.
Conversation during the lecture to verify higher levels of learning outcomes in terms of knowledge and skills.
A written test verifying learning outcomes in terms of knowledge and competencies acquired during the lecture.
The final grade for the course consists of the exercise grade (50%) and the lecture grade (50%). The condition for passing the course is obtaining positive passing grades for both exercises and the lecture.
Literatura podstawowa
J. Bang-Jensen, G. Gutin, Digraphs, Theory and Algorithms, 2001.
R. Distel, Graph Theory, Springer-Verlag, New York 2017.
V.B. Brandstadt, J.P. Le, Spinrad, Graph Classes: a survey, SIAM 2004.
Literatura uzupełniająca
H. L. Bodlaender, A partial k-arboretum of graphs with bounded treewidth,Theoretical Computer Science 209 (1998) 1-45.
Uwagi
Zmodyfikowane przez dr Ewa Synówka (ostatnia modyfikacja: 10-04-2024 19:35)
Ta strona używa ciasteczek (cookies), dzięki którym nasz serwis może działać lepiej. Korzystając z niniejszej strony, wyrażasz zgodę na ich używanie. Dowiedz się więcej.