SubjectsSubjects(version: 853)
Course, academic year 2019/2020
  
Graph Theory and Applications - P413001
Title: Teorie grafů a její aplikace
Guaranteed by: Department of Mathematics (413)
Actual: from 2019
Semester: both
Points: 0
E-Credits: 0
Examination process:
Hours per week, examination: 3/0 other [hours/week]
Capacity: winter:unknown / unknown (unknown)
summer:unknown / unknown (unknown)
Min. number of students: unlimited
Language: Czech
Teaching methods: full-time
Level:  
For type: doctoral
Note: course is intended for doctoral students only
can be fulfilled in the future
you can enroll for the course in winter and in summer semester
Guarantor: Turzík Daniel doc. RNDr. CSc.
Maxová Jana RNDr. Ph.D.
Interchangeability : D413012
Is interchangeable with: AP413001
Annotation -
Last update: Maxová Jana RNDr. Ph.D. (08.06.2018)
The basic concepts of graph theory are introduced. Algorithmic solutions of engineering problems are discussed.
Aim of the course -
Last update: Maxová Jana RNDr. Ph.D. (08.06.2018)

Students will acquire the basic concepts of graph theory. They will learn to analyze various engineering tasks and solve them using known graph algorithms. They will then learn how to

recognize computationally hard tasks and gain insight into many of the problems solved by graph theory.

Literature -
Last update: Maxová Jana RNDr. Ph.D. (08.06.2018)

A: Matousek J., Nesetril J.: Invitation to Discrete Mathematics, Oxford University Press, USA, 2011. ISBN 978-0198570424

A: West D. B.: Introduction to Graph Theory. Pearson, 2001. ISBN 978-0130144003.

A: Diestel R.: Graph Theory (Graduate Texts in Mathematics). Springer, 2010. ISBN 978-3642142789.

A: Christofides N.: Graph Theory. An Algoritmic Approach. Academic Press Inc, 1975. ISBN 978-0121743505.

Learning resources -
Last update: Maxová Jana RNDr. Ph.D. (07.06.2018)

www.vscht.cz/mat/Ang/indexAng.html

Teaching methods -
Last update: Maxová Jana RNDr. Ph.D. (24.09.2018)

lectures, tutorials, individual work on the project

Syllabus -
Last update: Maxová Jana RNDr. Ph.D. (08.06.2018)

1. Basic concepts in graph theory. Representations of graphs.

2. Paths in graphs. The task of the shortest path.

3. Connected graphs, Components od connectivity, blocks of graphs.

4. Trees. Heap-sort.

5. Spanning tree. Greedy algorithm for minimal spanning tree.

6. System of distinct representatives. Matching in bipartite graphs.

7. Matching in general graphs.

8. Euler graphs. The Chinese postman problem.

9. Hamiltonian graphs. The travelling salesman problem.

10. Planar graphs and their characteristics.

11. Coloring. Coloring of Planar graphs.

12. Flows in networks.

13. Theory of complexity. P and NP problems. Good characteristics.

14. Examples of graph theory applications.

Registration requirements -
Last update: Mareš Jan doc. Ing. Ph.D. (03.10.2018)

none

Course completion requirements -
Last update: Maxová Jana RNDr. Ph.D. (07.06.2018)

The subject is finished by an oral exam. Before the exam is completed, 3 of the tasks assigned during the semester must be successfully solved.

Coursework assessment
Form Significance
Oral examination 100

 
VŠCHT Praha