FI:MA051 Advanced Graph Theory I - Informace o předmětu

MA051 Advanced Graph Theory I

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

St 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, D-IN)
• Informatika (program FI, M-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)
• Teoretická informatika (program FI, N-IN)
• Učitelství výpočetní techniky pro střední školy (program FI, M-SS)
• Učitelství výpočetní techniky pro střední školy (program FI, M-TV)
• 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

Rovinné grafy a grafy kreslené na vyšších plochách hrají (poněkud překvapivě) velmi důležitou úlohu v teorii grafů a v jejích aplikacích. (Pro příklad zmíníme Větu a čtyřech barvách, projekt grafových minorů, či mnohé nedávné parametrizované algoritmy pro těžké grafové problémy.)
Náš předmět je pro studenty matematiky nebo teoretické informatiky úvodem do této krásné oblasti teorie grafů, která se také nazývá topologická teorie grafů. Naše přednášky shrnují důležité výsledky v této oblasti od klasické Kuratowského věty, přes větu o čtyřech barvách, až po nedávné strukturální výsledky spojené s projektem grafových minorů a po problém průsečíkového čísla.

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

• MOHAR, Bojan a Carsten THOMASSEN. Graphs on Surfaces. Johns Hopkins University Press, 2001. ISBN 0-8018-6689-8. URL info
• NEŠETŘIL, Jaroslav a Jiří MATOUŠEK. Invitation to discrete mathematics. Oxford: Clarendon Press, 1998, xv, 410 s. ISBN 0-19-850207-9. info

Metody hodnocení

This is an advanced course, taught in English, and conducted quite informally (seminar-type). Evaluation by a written individual homework assignment (one), and a subsequent oral exam.

Vyučovací jazyk

Angličtina

Navazující předměty

• MA052 Advanced Graph Theory: Structural
• MA053 Matroid theory and combinatorial optimization

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 2008, nejnovější)
  
• Permalink: https://is.muni.cz/predmet/fi/jaro2008/MA051