Courses – Fakultet tehničkih nauka u Novom Sadu

Subject: Fundamentals of Graph Theory and Combinatorics (17.IFE212)

Native organizations units: Department of Fundamentals Sciences, Chair of Mathematics

Type of studies	Title
Undergraduate Academic Studies	Information Engineering (Godina: 2, Winter)

General information:

Category	Scientific-professional
Scientific or art field	Teorijska i primenjena matematika
Interdisciplinary	Yes
ECTS	7

Educational goal:

The main aim of the course is to train students abstract thinking and acquire basic knowledge in the field of classical combinatorial objects, non-classical combinatorial objects and graph theory. Students will learn to classify combinatorial problems and solve them using well-known combinatorial methods, through the acquisition of theoretical knowledge and solving practical examples. Through the learning of well-known concepts and theorems from graph theory, students will be able to set graphic formal models from other fields (e.g. computer science and transport engineering). Properties of graphs will be precisely mathematically proved, with the aim of further development of students skills for deriving proofs.

Educational outcome:

As outcome of the course, students will acquire basic knowledge in the field of classical combinatorial objects, non-classical combinatorial objects and graph theory, with their abstract thinking and the skills of proofing being greatly improved. Students will be able to recognize combinatorial objects and solve them by known methods, as well as to develop and analyse graph models in some other fields.

Course content:

Lectures (Theoretical lectures). Logic relations, classical combinatorial objects (permutations, variations and combinations with and without repetition), partition sets, Stirling numbers, combinatorics on words, recurrent formulas, generative functions, basic concepts of graph theory, connection graphs, special classes of graphs, isomorphism of graphs, matrices neighborhoods, operations on graphs, trees, planar graphs (the fundamental theorem), Euler and Hamiltonian paths, Hamiltonian contours. Practice lectures (lab): In laboratory exercises adequate examples and tests from the theoretical lectures are done in order to exercise lectured theory where exercises contribute to understanding of the theory.

Teaching methods:

Lectures; Computing practice. Consultations. Lectures are dynamic and interactive. In lectures theoretical part of the course is presented accompanied by characteristic and representative examples in order to better understand the matter. In practice, which follows lectures, typical problems are solved and lectured theory is deepened. Besides lectures and practice, regular consultations and group consultations are also held. Part of the course, which is a logical unit, can be passed within the teaching process in the following 2 modules. The first module: Combinatorics. The second module: Graph theory.

Literature:

Authors	Title	Year	Publisher	Language
Tošić Ratko	Kombinatorika	1999	Univezitet u Novom Sadu	Serbian language
Robin J. Wilson	Introduction to Graph Theory	1996	Robin Wilson	English
D.Mašulović, M.Pech	Zbirka zadataka iz kombinatorike	2015	Prirodno-matematički fakultet, Departman za matematiku i informatiku	Serbian language
I. Bošnjak, D. Mašulović, V. Petrović, R. Tošić	Zbirka zadataka iz teorije grafova	2006	Univerzitet u Novom Sadu, Novi Sad	Serbian language
Doroslovački, R.	Kombinatorika na rečima	2000	Feljton, Novi Sad	Serbian language

Knowledge evaluation:

Course activity	Pre-examination	Obligations	Number of points
Written part of the exam - tasks and theory	No	Yes	30.00
Computer exercise attendance	Yes	Yes	5.00
Theoretical part of the exam	No	Yes	40.00
Test	Yes	Yes	10.00
Test	Yes	Yes	10.00
Lecture attendance	Yes	Yes	5.00