FI:MA010 Graph Theory - Informace o předmětu
MA010 Graph Theory
Fakulta informatikypodzim 2023
- Rozsah
- 2/1/0. 3 kr. (plus ukončení). Ukončení: zk.
- Vyučující
- prof. RNDr. Daniel Kráľ, Ph.D., DSc. (přednášející)
Ander Lamaison Vidarte, PhD (cvičící)
RNDr. Kristýna Pekárková (pomocník)
Mgr. Xichao Shu (pomocník) - Garance
- prof. RNDr. Daniel Kráľ, Ph.D., DSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Daniel Kráľ, Ph.D., DSc.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky - Rozvrh
- Čt 14:00–15:50 A217
- Rozvrh seminárních/paralelních skupin:
MA010/02: Po 25. 9. až Po 4. 12. každé liché pondělí 10:00–11:50 B411, D. Kráľ
MA010/03: Po 18. 9. až Po 11. 12. každé sudé pondělí 12:00–13:50 B411, A. Lamaison Vidarte
MA010/04: Po 25. 9. až Po 4. 12. každé liché pondělí 12:00–13:50 B411, A. Lamaison Vidarte - Předpoklady
- ! PřF:M5140 Teorie grafů &&! NOW ( PřF:M5140 Teorie grafů )
Discrete mathematics. IB000 (or equivalent from other schools) is 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 200 stud.
Momentální stav registrace a zápisu: zapsáno: 29/200, pouze zareg.: 0/200, pouze zareg. s předností (mateřské obory): 0/200 - Mateřské obory/plány
- předmět má 26 mateřských oborů, zobrazit
- Cíle předmětu
- 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.
- 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.
- Osnova
- Basic graph theory notions: graphs, subgraph, graph isomorphism, vertex degree, paths, cycles, connected components, directed graphs.
- Trees, Hamilton cycles, Dirac’s and Ore’s conditions.
- Planar graphs, duality of planar graphs, Euler's formula and its applications.
- Graph coloring, Five Color Theorem, Brooks’ Theorem, Vizing’s Theorem.
- Interval graphs, chordal graphs, and their chromatic properties.
- Vertex and edge connectivity.
- Matchings in graphs, Hall’s Theorem.
- Ramsey's Theorem.
- Selected advanced topics (to be chosen from): Graph minors, graph embeddings on surfaces, planarity testing, list coloring, Tutte’s Theorem, Cayley’s formula.
- Literatura
- doporučená literatura
- DIESTEL, Reinhard. Graph theory. 4th ed. Heidelberg: Springer, 2010, xviii, 436. ISBN 9783642142789. info
- BONDY, J. A. a U. S. R. MURTY. Graph theory. [New York, N.Y.]: Springer, 2008, xiv, 657. ISBN 9781846289699. 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
- Výukové metody
- 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.
- Metody hodnocení
- The resulting grade will based on the final written exam. To register for the exam, it is necessary to obtain at least 16 points, which can be obtained for solving homework assignments; the homework assignments will have deadlines during the term.
- Vyučovací jazyk
- Angličtina
- Navazující předměty
- Informace učitele
- https://www.fi.muni.cz/~dkral/ma010.html
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". More detailed information can be found on the course webpage maintained by the lecturer.
Since 2020, the grade is determined by the final exam only.
Since 2016, grading of MA010 changes by including a written homework assignment worth 20% and decreasing the weight of the final exam to 60%.
Since 2009, MA010 is taught in English. Předmět MA010 je od roku 2009 vyučován primárně anglicky. Informace v angličtině mají přednost, české materiály jsou doplňkové. - Další komentáře
- Studijní materiály
Předmět je vyučován každoročně. - Nachází se v prerekvizitách jiných předmětů
- Statistika zápisu (podzim 2023, nejnovější)
- Permalink: https://is.muni.cz/predmet/fi/podzim2023/MA010