MA010 Graph Theory

Fakulta informatiky
podzim 2026
Rozsah
2/1/0. 3 kr. (plus ukončení). Ukončení: zk.
Vyučováno kontaktně
Vyučující
prof. RNDr. Petr Hliněný, Ph.D. (přednášející)
RNDr. Jan Jedelský (cvičící)
Garance
prof. RNDr. Petr Hliněný, Ph.D.
Katedra teorie programování – Fakulta informatiky
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky
Předpoklady
! PřF:M5140 Teorie grafů &&!NOW( PřF:M5140 Teorie grafů )
Discrete mathematics. IB000 (or equivalent from other schools) is strongly recommended.
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Předmět si smí zapsat nejvýše 50 stud.
Momentální stav registrace a zápisu: zapsáno: 0/50, pouze zareg.: 24/50, pouze zareg. s předností (mateřské obory): 22/50
Mateřské obory/plány
předmět má 22 mateřských oborů, zobrazit
Anotace
This is a standard introductory course in graph theory, assuming no prior knowledge of graphs. The course aims to present basic graph theory concepts and statements with a particular focus on those relevant in algorithms and computer science in general. Selected advanced graph theory topics will also be covered. Although the content of this course is primarily targeted at computer science students, it should be accessible to all students with sufficient background in discrete mathematics.
Výstupy z učení
At the end of the course, students shall understand basic concenpts in graph theory; be able to reproduce the proofs of some fundamental statements in graph theory; be able to solve unseen simple graph theory problems; and be ready to apply their knowledge particularly in computer science.
Klíčová témata
  • Basic graph theory terms: graphs, subgraph, graph isomorphism, vertex degree sequence, paths and trees, Cayley formula.
  • Cycles in graphs, interval graphs, chordal graphs, Hamiltonian graphs.
  • Connectivity, cuts, directed graphs, Menger's theorem.
  • Planar graphs, duality, Euler's formula, Kuratowski theorem.
  • Graph coloring, bipartite graphs, Mycielski construction, 5-list-colorability, Brooks’ Theorem, Vizing’s Theorem, perfect graphs.
  • Matchings in graphs, Hall’s Theorem, Tutte's theorem, stable marriage theorem.
  • Ramsey Theorem.
Studijní zdroje a literatura
    doporučená literatura
  • DIESTEL, Reinhard. Graph theory. 4th ed. Heidelberg: Springer, 2010, xviii, 436. ISBN 9783642142789. info
  • http://diestel-graph-theory.com/
  • MATOUŠEK, Jiří a Jaroslav NEŠETŘIL. Kapitoly z diskrétní matematiky. 3., upr. a dopl. vyd. V Praze: Karolinum, 2007, 423 s. ISBN 9788024614113. info
  • HLINĚNÝ, Petr. Základy teorie grafů. Elportál. Brno: Masarykova univerzita, 2010. ISSN 1802-128X. URL info
Přístupy, postupy a metody používané ve výuce
MA010 is taught in weekly 2-hour lectures, which are primarily focused on introducing the material (concepts, statements, proofs). The lectures are complemented with bi-weekly 2-hour tutorials where examples and problems related to the material presented during the lectures are made available to practice.
Způsob ověření výstupů z učení a požadavky na ukončení
Students are expected to understand (not only memorize) the concepts taught in the lectures, including simple mathematical proofs. The resulting grade will based on the semester test (25%) and the final written exam (75%) - both parts require meeting their respective minimal thresholds. Grades B and A moreover require a subsequent oral discussion on the exam topics and questions.
Vyučovací jazyk
Angličtina
Navazující předměty
Odkaz a informace vyučujících
Basic information regarding course curriculum and examination can be found in the online syllabus MA010 in the Information System - "https://is.muni.cz/auth/el/1433/podzim20**/MA010/index.qwarp".
Další komentáře
Předmět je vyučován každoročně.
Výuka probíhá každý týden.
Nachází se v prerekvizitách jiných předmětů
Předmět je zařazen také v obdobích podzim 2002, podzim 2003, podzim 2004, podzim 2006, podzim 2007, podzim 2008, podzim 2009, podzim 2010, podzim 2011, podzim 2012, podzim 2013, podzim 2014, podzim 2015, podzim 2016, podzim 2017, podzim 2018, podzim 2019, podzim 2020, podzim 2021, podzim 2022, podzim 2023, podzim 2024, podzim 2025.
  • Statistika zápisu (nejnovější)
  • Permalink: https://is.muni.cz/predmet/fi/podzim2026/MA010