Předmět Graph Theory (MA010)
Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu MA010 - Graph Theory, Fakulta informatiky, Masarykova univerzita (MU).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Cíl
This is a standard course in graph theory.All standard concepts, graph properties (with simplified proofs), formulations of usual graph problems, and abstract-level algorithms for their solving, are presented. Although the content of this course is targeted at CS students, it is accessible also to others.At the end of the course, successful students shall understand in depth and tell all the basic terms of graph theory; be able to reproduce the proofs of some fundamental statements on graphs; be able to solve new graph problems; and be ready to apply this knowledge in (especially) computer science applications.
Osnova
Graphs and relations. Subgraphs, isomorphism, degrees. Directed graphs.Graph connectivity and searching, multiple connectivity. Trees, the MST problem.Distance in graphs, graph metrics, concepts of route planning in graphs.Network flows. The "max-flow min-cut" theorem via Ford-Fulkerson algorithm. Applications to connectivity, matching and representatives.Matching in graphs, packing problems, enumeration.Graph colouring, properties, easy and hard cases. Edge and list colourings.Computationally hard graph problems: independent set, clique, vertex cover, dominating set, Hamiltonian, etc.Planar embeddings of graphs, Euler formula and its applications. Graph drawing.Selected advanced topics (time allowing):Intersection graph representations, chordal graphs, structural width measures, graph minors, graph embeddings on surfaces, crossing number, Ramsey theory.
Literatura
doporučená literaturaGraph theory. Edited by Reinhard Diestel. 3rd ed. Berlin: Springer, 2006. xvi, 410s. ISBN 3540261834. infohttp://diestel-graph-theory.com/HLINĚNÝ, Petr . Základy teorie grafů. Elportál, Brno: Masarykova univerzita, 2010. ISSN 1802-128X. URL infoMATOUŠEK, Jiří a Jaroslav NEŠETŘIL. Kapitoly z diskrétní matematiky. 3., upr. a dopl. vyd. V Praze: Karolinum, 2007. 423 s. ISBN 978-80-246-1411-3. info
Požadavky
! PřF:M5140 Teorie grafů &&! NOW ( PřF:M5140 Teorie grafů )Discrete mathematics, basic concepts of graphs and graph algorithms. IB000 (or equivalent from other schools) is highly recommended.
Garant
prof. RNDr. Mojmír Křetínský, CSc.
Vyučující
prof. RNDr. Petr Hliněný, Ph.D.RNDr. Jan Bouda, Ph.D.Frédéric Dupont Dupuis, Ph.D.Mgr. Jan Obdržálek, PhD.