Subject description - XP01TGR

Summary of Study | Summary of Branches | All Subject Groups | All Subjects | List of Roles | Explanatory Notes               Instructions
XP01TGR Graph Theory
Roles:S Extent of teaching:2P+1S
Department:13101 Language of teaching:CS
Guarantors:Demlová M. Completion:ZK
Lecturers:Demlová M. Credits:4
Tutors:Demlová M. Semester:Z

Web page:

https://moodle.fel.cvut.cz/courses/XP01TGR

Anotation:

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.

Study targets:

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.

Content:

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.

Course outlines:

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.

Exercises outline:

Excerices have the form of homeworks with consultations.

Literature:

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

Requirements:

No.

Keywords:

Directed and undirected graphs, k-connected graphs, strongly connected graphs, Hamiltonian graphs, flow in networks, matching, independent sets, cluques, vertex and edge covers. colorings, graphs and vector spaces.

Subject is included into these academic programs:

Program Branch Role Recommended semester
DOKP Common courses S –
DOKK Common courses S –

Page updated 14.3.2025 14:51:46, semester: Z,L/2024-5, Z,L/2025-6, Send comments about the content to the Administrators of the Academic Programs Proposal and Realization: I. Halaška (K336), J. Novák (K336)
Responsible person: prof. Ing. Jiří Jakovenko, Ph.D.