FI:MA051 Advanced Graph Theory I - Informace o předmětu
MA051 Advanced Graph Theory I
Fakulta informatikyjaro 2010
- Rozsah
- 2/1. 3 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: k, z.
- Vyučující
- prof. RNDr. Petr Hliněný, Ph.D. (přednášející)
- Garance
- prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Petr Hliněný, Ph.D. - Rozvrh
- Čt 9:00–11:50 B411
- Předpoklady
- Teorie grafu MA010 (Graph theory). Introductory knowledge of topology is also welcome.
- 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 30 stud.
Momentální stav registrace a zápisu: zapsáno: 0/30, pouze zareg.: 0/30, pouze zareg. s předností (mateřské obory): 0/30 - Mateřské obory/plány
- Aplikovaná informatika (program FI, N-AP)
- Bezpečnost informačních technologií (program FI, N-IN)
- Bioinformatika (program FI, N-AP)
- Informační systémy (program FI, N-IN)
- Informatika (program FI, N-IN)
- Matematická informatika (program FI, B-IN)
- Paralelní a distribuované systémy (program FI, N-IN)
- Počítačová grafika (program FI, N-IN)
- Počítačové sítě a komunikace (program FI, N-IN)
- Počítačové systémy (program FI, N-IN)
- Programovatelné technické struktury (angl.) (program FI, N-IN)
- Programovatelné technické struktury (program FI, N-IN)
- Služby - výzkum, řízení a inovace (angl.) (program FI, N-AP)
- Služby - výzkum, řízení a inovace (program FI, N-AP)
- Teoretická informatika (program FI, N-IN)
- Učitelství výpočetní techniky pro střední školy (program FI, N-SS) (2)
- Umělá inteligence a zpracování přirozeného jazyka (program FI, N-IN)
- Zpracování obrazu (program FI, N-AP)
- Cíle předmětu
- This subject introduces a mathematician or a theoretical computer scientist into the beauties of the topological graph theory.
The lectures survey important results in this area, starting from classical ones like the Kuratowski theorem, through the Four Colour theorem, till recent structural results connected with the Graph Minor project, and the crossing number problem.
In this course the students will learn about some cutting-edge recent development in graph theory. At the end, they should: understand the basic principles of topological graph theory and of graph crossing numbers including algorithmic applications; and be able to continue with some scientific work in this area if they choose to. - Osnova
- Basic graph terms, planar graphs, colourings.
- The Kuratowski Theorem, with a proof.
- The Four Colour Theorem, with an outline of a proof.
- Planarity algorithms and complexity.
- Graphs embedded on higher surfaces.
- Graph minors, tree-width, and "forbidden" characterizations.
- The "Kuratowski" theorem for any surface.
- Graphs drawings with edge-crossings. The crossing number.
- Complexity of the graph crossing number problem.
- Crossing-critical graphs and their structure.
- Literatura
- Výukové metody
- This is an advanced theoretical course, taught in English, and conducted quite informally (a seminar-type lecturing). Students are expected to actively participate in all the lectures and tutorials.
- Metody hodnocení
- Evaluation is based on a mandatory written individual homework assignment (one essay), and on a subsequent oral exam.
- Vyučovací jazyk
- Angličtina
- Navazující předměty
- Informace učitele
- http://www.fi.muni.cz/~hlineny/Teaching/AGTT.html
Course based on the book * Mohar, Bojan - Thomassen, Carsten. Graphs on Surfaces.
Supplementary literature (in Czech): Petr Hliněný. Teorie grafů, "http://www.fi.muni.cz/~hlineny/Vyuka/GT/". - Další komentáře
- Studijní materiály
Předmět je vyučován jednou za dva roky.
- Statistika zápisu (jaro 2010, nejnovější)
- Permalink: https://is.muni.cz/predmet/fi/jaro2010/MA051