SubjectsSubjects(version: 850)
Course, academic year 2019/2020
   Login via CAS
Combinatorics and Graph Theory I - NDMI011
Title in English: Kombinatorika a grafy I
Guaranteed by: Computer Science Institute of Charles University (32-IUUK)
Faculty: Faculty of Mathematics and Physics
Actual: from 2019 to 2019
Semester: summer
E-Credits: 5
Hours per week, examination: summer s.:2/2 C+Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: taught
Language: English
Teaching methods: full-time
Guarantor: doc. RNDr. Vít Jelínek, Ph.D.
doc. RNDr. Jiří Fiala, Ph.D.
Class: Informatika Bc.
Classification: Informatics > Discrete Mathematics
Incompatibility : NDMA001
Annotation -
Last update: PANGRAC/MFF.CUNI.CZ (08.04.2010)
Inclusion-exclusion principle and its applications. Generating functions. Finite projective planes, latin squares. Hall theorem and its applications. Flows in digraphs. k-connectivity of graphs. Ramsey theory.
Course completion requirements -
Last update: Andrew Goodall, Ph.D. (14.02.2018)

Andrew Goodall:

There will be two written tests for obtaining a credit (pass) for this course, taken during the semester, based on the topics covered in lectures and tutorials.

To pass the class you should satisfy one of the following criteria:

1) get a score of at least 50% of the total marks on each test taken during the semester.

2) get a score of at least 60% of the total marks on each test that is either missed due to absence or fails to score at least 50% of the total marks, by (re)taking the corresponding test(s), and this to be done latest one week after the end of semester.

You will be informed of what the total mark is when taking the tests.

There is no other provision for repeated attempts at obtaining a course credit.

Literature -
Last update: doc. RNDr. Vít Jelínek, Ph.D. (22.11.2012)

J. Matoušek, J. Nešetřil: Invitation to Discrete Mathematics, Oxford University Press (1998)

R. Diestel: Graph Theory (4th edition), Springer (2010)

Requirements to the exam -
Last update: Andreas Emil Feldmann, Dr. (19.02.2018)

The exam has a combined form: written and oral. The knowledge requirements for the exam correspond to the syllabus of the course.

The ability to generalize and apply the acquired theoretical knowledge from the tutorials is also required.

Syllabus -
Last update: doc. RNDr. Pavel Töpfer, CSc. (26.01.2018)

Basic course of the computer science study plan. It extends Discrete Mathematics course and covers fundamentals of graph theory and combinatorics from

both structural and algorithmic point of view.

Estimates on the factorial function and binomial coefficients

The number of spanning trees of the complete graph

Generating functions and applications

Finite projective planes, Latin squares and their orthogonality

Double counting - number of spanning trees of K_n-e, Sperner's theorem on independent systems

Flows in networks

Hall's theorem and its applications, maximum matching in bipartite graphs

Higher connectivity of graphs, Menger-type theorems, structure of 2-connected graphs

Ramsey theory

Charles University | Information system of Charles University |