SubjectsSubjects(version: 802)
Course, academic year 2016/2017
   Login via CAS
Combinatorics and Graph Theory I - NDMI011
Czech title: Kombinatorika a grafy I
Guaranteed by: Computer Science Institute of Charles University (32-IUUK)
Faculty: Faculty of Mathematics and Physics
Actual: from 2016 to 2016
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: Czech, English
Teaching methods: full-time
Guarantor: RNDr. Martin Tancer, 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.
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)

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

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 |