Logo ČVUT
CZECH TECHNICAL UNIVERSITY IN PRAGUE
STUDY PLANS
2024/2025

Graph Theory

Login to KOS for course enrollment Display time-table
Code Completion Credits Range Language
XP01TGR ZK 4 2P+1S Czech
Course guarantor:
Marie Demlová
Lecturer:
Marie Demlová
Tutor:
Marie Demlová
Supervisor:
Department of Mathematics
Synopsis:

Basic course in graph theory. Trees, their characterization, minimal spanning tree. Strongly connected components, rooted trees. Shortest paths, Floyds algorithm. Euler graphs and their applications, Hamiltonian graphs and their applications. Chvatal's theorem. Flow in networsk, admissible flows and admissible circulations. Matchings in general graphs and in bipartite graphs. Vertex cover and independent sets. Cliques. Colorings. Plannar graphs. Graphs and vector spaces. The content of the course is modified according to the needs of students.

Requirements:

No.

Syllabus of lectures:

1. Basic notions and properties concerning undirected graphs.

2. Vertex connectivity a edge connectivity, cut vertices, bridges.

3. Basic notions and propertis concerning directed graphs.

4. Transitive closure and transitive reduction of difectec graphs, minimally strongly connected graphs.

5. Hamiltonian graphs (undirected, directed), Chvatal's theorem.

6. Flow in networks. Ford-Fulkerson Theorem. Bases of fast algorithms for finding maximal flow in a network.

7. Admissible flows and addmisible circulations.

8. Matching in general graphs and in bipartite graphs.

9. Independent sets, cliques, vertex covers.

10. Edge covers. Colorability with emphasis to vertex colorings.

11. Graphs and vector spaces. Circiut vector subspace and cut vector subspace.

12. Duality. Duality based on plannar graphs is the same notions as duality

arising from circuits and cuts.

Syllabus of tutorials:

Excerices have the form of homeworks with consultations.

Study Objective:

The main goal of the course is to introduce to students methods and techniques used in graph theory. Emphasis is given to self study; during semestr students get small task to be solved and the solution correctly written together with its justification.

Study materials:

1. Reinhard Diestel: Graph Theory. Springer-Verlag, New York, 1997.

2. M.N.S. Swamy, K. Thulasiraman: Graphs, Networks, and Algorithms, Part 1, Graph Theory, John Wiley & Sons, New York, 1981

Note:
Further information:
https://moodle.fel.cvut.cz/courses/XP01TGR
Time-table for winter semester 2024/2025:
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Mon
Tue
Wed
roomT2:C2-83
Demlová M.
08:15–09:00
(lecture parallel1
parallel nr.101)

Dejvice
cvičebna
roomT2:C2-83
Demlová M.
09:15–10:45
(lecture parallel1)
Dejvice
cvičebna
Thu
Fri
Time-table for summer semester 2024/2025:
Time-table is not available yet
The course is a part of the following study plans:
Data valid to 2024-10-11
For updated information see http://bilakniha.cvut.cz/en/predmet11506804.html