M5140 Graph Theory

Faculty of Science
Autumn 2010 - only for the accreditation
Extent and Intensity
2/1/0. 3 credit(s) (příf plus uk k 1 zk 2 plus 1 > 4). Type of Completion: zk (examination).
Teacher(s)
doc. RNDr. Josef Niederle, CSc. (lecturer)
Guaranteed by
doc. RNDr. Josef Niederle, CSc.
Department of Mathematics and Statistics – Departments – Faculty of Science
Prerequisites (in Czech)
! M5145 Graph Theory && !( FI:MA010 Graph Theory )
Course Enrolment Limitations
The course is also offered to the students of the fields other than those the course is directly associated with.
fields of study / plans the course is directly associated with
there are 8 fields of study the course is directly associated with, display
Course objectives
This is an introductory course in graph theory. The objectives are to understand basic concepts and their properties as well as to be able to formulate simple graph problems and apply standard effective algorithms for solving them.
Syllabus
  • Basic concepts
  • Paths
  • Eulerian and Hamiltonian graphs
  • Trees. Characterization theorems, rooted trees, ordered trees, binary trees.
  • Spanning trees. Algorithms for finding minimal spannig trees
  • The shortest-path problem. Algorithms Moore, Dijkstra, Ford, Critical Path Method
  • Network flow. Ford-Fulkerson Theorem, Ford-Fulkerson algorithm
  • Bipartite graphs and matchings. Minimal matchings
  • Connectivity in graphs. Menger Theorem, 2-connected and 3-connected graphs
  • Planar graphs
Literature
  • KUČERA, Luděk. Kombinatorické algoritmy. 2., nezměn. vyd. Praha: SNTL - Nakladatelství technické literatury, 1989, 286 s. info
  • NEŠETŘIL, Jaroslav. Teorie grafů. Vyd. 1. Praha: SNTL - Nakladatelství technické literatury, 1979, 316 s. URL info
  • PLESNÍK, Ján. Grafové algoritmy. 1. vyd. Bratislava: Veda, 1983, 343 s. info
  • FUCHS, Eduard. Kombinatorika a teorie grafů. Vyd. 1. Praha: Státní pedagogické nakladatelství, 1986, 138 s. info
  • NEŠETŘIL, Jaroslav. Kombinatorika. Vyd. 1. Praha: Státní pedagogické nakladatelství, 1983, 173 s. URL info
Teaching methods
Lectures and seminars.
Assessment methods
Written exam.
Language of instruction
Czech
Further comments (probably available only in Czech)
The course is taught annually.
The course is taught: every week.
Listed among pre-requisites of other courses
The course is also listed under the following terms Autumn 2007 - for the purpose of the accreditation, Autumn 1999, Autumn 2000, Autumn 2001, Autumn 2002, Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2011 - acreditation, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.