Subject: Mathematics

Course: Combinatorics and graph theory

ECTS credits: 3

Language: Croatian

Duration: 2 semesters

Status: compulsory

Method of teaching: lecture hour + practical class

Prerequisite: n/a

Assessment: Three exams during semester or at the end written and oral exam.

Course description:

1. Set, multi-set and sequence. Function and relation. Equivalence elation and partial order relation.

2. Mathematical induction and recursion. Natural numbers and mathematical induction. Sequence and recursion.

3. Dirichlet principle. Strong form of Dirichlet principle. General Dirichlet principle. Introduction to Ramsey theory.

4. Elementary principles of enumeration. Principle of bijection. Principle of sum. Principle of product.

5. Permutations. Symmetric group. Cycle and standard cyclic notation.

6. Combinations. Combinations of set and multi-set. Composition and weak composition of natural number.

7. Partitions of numbers and sets. Stirling numbers of I and I I order.

8. Graph and graph matrices. Graph and subgraph. Incidence and adjacency matrix. Vertices order, maximal and minimal order of graph.

9. Paths and cycles. Close path and cycles. Connection.

10. Tree. Cyclic partition. Characteristics of tree.

Course objectives:

In the course topics from combinations and graph theory are elaborated. At the beginning notions of multi-set, relation and mathematical induction are presented. In the combination part, topics such as enumeration of sets, multi-sets and functions are treated. In the part concerning graph basic notions of graph and tree are given.

Quality check and success of the course: Quality check and success of the course will be done by combining internal and external evaluation. Internal evaluation will be done by teachers and students using survey method at the end of semester. The external evaluation will be done by colleagues attending the course, by monitoring and assessment of the course.

Reading list:

1. D. Veljan, Kombinatorna i diskretna matematika, Algoritam, Zagreb 2001.