MA051 Advanced Graph Theory: Topological

Fakulta informatiky
jaro 2014
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.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky
Rozvrh
Čt 9:00–11:50 G191m
Předpoklady
Graph Theory MA010. 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
předmět má 19 mateřských oborů, zobrazit
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, basics of topology.
  • Jordan's curve theorem, with a proof.
  • Kuratowski's 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 problem, complexity.
  • Crossing-critical graphs and their structure.
Literatura
    povinná literatura
  • MOHAR, Bojan a Carsten THOMASSEN. Graphs on Surfaces. Johns Hopkins University Press, 2001. ISBN 0-8018-6689-8. URL info
Výukové metody
This is an advanced theoretical course, taught in English, and conducted quite informally (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/stud-en.html#spring
Do not be afraid of this course if you like graphs. The topic is advanced, yet it will be given on a nicely accessible level. Lecture time is not in the central timetable, we will choose it based on your preferences at the beginning - go to the curse discussion in IS and express your wish.
Další komentáře
Studijní materiály
Předmět je vyučován jednou za dva roky.
Předmět je zařazen také v obdobích jaro 2006, jaro 2008, jaro 2010, jaro 2012.

MA051 Advanced Graph Theory: Topological

Fakulta informatiky
jaro 2012
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.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky
Rozvrh
Út 13:00–15:50 G191m
Předpoklady
Graph Theory MA010. 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
předmět má 20 mateřských oborů, zobrazit
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, basics of topology.
  • Jordan's curve theorem, with a proof.
  • Kuratowski's 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 problem, complexity.
  • Crossing-critical graphs and their structure.
Literatura
    povinná literatura
  • MOHAR, Bojan a Carsten THOMASSEN. Graphs on Surfaces. Johns Hopkins University Press, 2001. ISBN 0-8018-6689-8. URL info
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/stud-en.html#spring
Do not be afraid of this course if you like graphs. The topic is advanced, yet it will be given on a nicely accessible level.
Další komentáře
Studijní materiály
Předmět je vyučován jednou za dva roky.
Předmět je zařazen také v obdobích jaro 2006, jaro 2008, jaro 2010, jaro 2014.

MA051 Advanced Graph Theory I

Fakulta informatiky
jaro 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
předmět má 19 mateřských oborů, zobrazit
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
  • MOHAR, Bojan a Carsten THOMASSEN. Graphs on Surfaces. Johns Hopkins University Press, 2001. ISBN 0-8018-6689-8. URL info
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.
Předmět je zařazen také v obdobích jaro 2006, jaro 2008, jaro 2012, jaro 2014.

MA051 Advanced Graph Theory I

Fakulta informatiky
jaro 2008
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
předmět má 20 mateřských oborů, zobrazit
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
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.
Předmět je zařazen také v obdobích jaro 2006, jaro 2010, jaro 2012, jaro 2014.

MA051 Advanced topics in Graph Theory: Graphs on surfaces

Fakulta informatiky
jaro 2006
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 14:00–15:50 B411 a každý sudý čtvrtek 16:00–17:50 B411
Předpoklady
Běžné znalosti diskrétní matematiky a pojmu grafu. (Viz kniha "Kapitoly z diskrétní matematiky"). Vítány jsou i úvodní znalosti topologie.
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.: 0/50, pouze zareg. s předností (mateřské obory): 0/50
Mateřské obory/plány
předmět má 7 mateřských oborů, zobrazit
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.
  • (A graph view of surface classification.)
  • 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
  • MATOUŠEK, Jiří a Jaroslav NEŠETŘIL. Kapitoly z diskrétní matematiky. Vyd. 2., opr. Praha: Karolinum, 2000, 377 s. ISBN 8024600846. info
Metody hodnocení
Written individual homework assignment (one), and a subsequent oral exam.
Vyučovací jazyk
Angličtina
Informace učitele
http://www.fi.muni.cz/~hlineny/Teaching/AGTT.html
Další komentáře
Předmět je vyučován jednou za dva roky.
Předmět je zařazen také v obdobích jaro 2008, jaro 2010, jaro 2012, jaro 2014.

MA051 Advanced Graph Theory: Topological

Fakulta informatiky
jaro 2019

Předmět se v období jaro 2019 nevypisuje.

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.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky
Předpoklady
Graph Theory MA010. 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
předmět má 20 mateřských oborů, zobrazit
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, basics of topology.
  • Jordan's curve theorem, with a proof.
  • Kuratowski's 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 problem, complexity.
  • Crossing-critical graphs and their structure.
Literatura
    povinná literatura
  • MOHAR, Bojan a Carsten THOMASSEN. Graphs on Surfaces. Johns Hopkins University Press, 2001. ISBN 0-8018-6689-8. URL info
Výukové metody
This is an advanced theoretical course, taught in English, and conducted quite informally (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/stud-en.html#spring
Do not be afraid of this course if you like graphs. The topic is advanced, yet it will be given on a nicely accessible level. Lecture time is not in the central timetable, we will choose it based on your preferences at the beginning - go to the curse discussion in IS and express your wish.
Další komentáře
Předmět již není vypisován.
Výuka probíhá každý týden.
Předmět je zařazen také v obdobích jaro 2006, jaro 2008, jaro 2010, jaro 2012, jaro 2014.

MA051 Advanced Graph Theory: Topological

Fakulta informatiky
jaro 2018

Předmět se v období jaro 2018 nevypisuje.

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.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky
Předpoklady
Graph Theory MA010. 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
předmět má 20 mateřských oborů, zobrazit
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, basics of topology.
  • Jordan's curve theorem, with a proof.
  • Kuratowski's 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 problem, complexity.
  • Crossing-critical graphs and their structure.
Literatura
    povinná literatura
  • MOHAR, Bojan a Carsten THOMASSEN. Graphs on Surfaces. Johns Hopkins University Press, 2001. ISBN 0-8018-6689-8. URL info
Výukové metody
This is an advanced theoretical course, taught in English, and conducted quite informally (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/stud-en.html#spring
Do not be afraid of this course if you like graphs. The topic is advanced, yet it will be given on a nicely accessible level. Lecture time is not in the central timetable, we will choose it based on your preferences at the beginning - go to the curse discussion in IS and express your wish.
Další komentáře
Předmět již není vypisován.
Výuka probíhá každý týden.
Předmět je zařazen také v obdobích jaro 2006, jaro 2008, jaro 2010, jaro 2012, jaro 2014.

MA051 Advanced Graph Theory: Topological

Fakulta informatiky
jaro 2017

Předmět se v období jaro 2017 nevypisuje.

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.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky
Předpoklady
Graph Theory MA010. 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
předmět má 20 mateřských oborů, zobrazit
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, basics of topology.
  • Jordan's curve theorem, with a proof.
  • Kuratowski's 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 problem, complexity.
  • Crossing-critical graphs and their structure.
Literatura
    povinná literatura
  • MOHAR, Bojan a Carsten THOMASSEN. Graphs on Surfaces. Johns Hopkins University Press, 2001. ISBN 0-8018-6689-8. URL info
Výukové metody
This is an advanced theoretical course, taught in English, and conducted quite informally (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/stud-en.html#spring
Do not be afraid of this course if you like graphs. The topic is advanced, yet it will be given on a nicely accessible level. Lecture time is not in the central timetable, we will choose it based on your preferences at the beginning - go to the curse discussion in IS and express your wish.
Další komentáře
Předmět již není vypisován.
Výuka probíhá každý týden.
Předmět je zařazen také v obdobích jaro 2006, jaro 2008, jaro 2010, jaro 2012, jaro 2014.

MA051 Advanced Graph Theory: Topological

Fakulta informatiky
jaro 2016

Předmět se v období jaro 2016 nevypisuje.

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.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky
Předpoklady
Graph Theory MA010. 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
předmět má 20 mateřských oborů, zobrazit
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, basics of topology.
  • Jordan's curve theorem, with a proof.
  • Kuratowski's 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 problem, complexity.
  • Crossing-critical graphs and their structure.
Literatura
    povinná literatura
  • MOHAR, Bojan a Carsten THOMASSEN. Graphs on Surfaces. Johns Hopkins University Press, 2001. ISBN 0-8018-6689-8. URL info
Výukové metody
This is an advanced theoretical course, taught in English, and conducted quite informally (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/stud-en.html#spring
Do not be afraid of this course if you like graphs. The topic is advanced, yet it will be given on a nicely accessible level. Lecture time is not in the central timetable, we will choose it based on your preferences at the beginning - go to the curse discussion in IS and express your wish.
Další komentáře
Předmět již není vypisován.
Výuka probíhá každý týden.
Předmět je zařazen také v obdobích jaro 2006, jaro 2008, jaro 2010, jaro 2012, jaro 2014.

MA051 Advanced Graph Theory: Topological

Fakulta informatiky
jaro 2015

Předmět se v období jaro 2015 nevypisuje.

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.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky
Předpoklady
Graph Theory MA010. 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
předmět má 19 mateřských oborů, zobrazit
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, basics of topology.
  • Jordan's curve theorem, with a proof.
  • Kuratowski's 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 problem, complexity.
  • Crossing-critical graphs and their structure.
Literatura
    povinná literatura
  • MOHAR, Bojan a Carsten THOMASSEN. Graphs on Surfaces. Johns Hopkins University Press, 2001. ISBN 0-8018-6689-8. URL info
Výukové metody
This is an advanced theoretical course, taught in English, and conducted quite informally (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/stud-en.html#spring
Do not be afraid of this course if you like graphs. The topic is advanced, yet it will be given on a nicely accessible level. Lecture time is not in the central timetable, we will choose it based on your preferences at the beginning - go to the curse discussion in IS and express your wish.
Další komentáře
Předmět je vyučován jednou za dva roky.
Výuka probíhá každý týden.
Předmět je zařazen také v obdobích jaro 2006, jaro 2008, jaro 2010, jaro 2012, jaro 2014.

MA051 Advanced Graph Theory: Topological

Fakulta informatiky
jaro 2013

Předmět se v období jaro 2013 nevypisuje.

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.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky
Předpoklady
Graph Theory MA010. 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
předmět má 19 mateřských oborů, zobrazit
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, basics of topology.
  • Jordan's curve theorem, with a proof.
  • Kuratowski's 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 problem, complexity.
  • Crossing-critical graphs and their structure.
Literatura
    povinná literatura
  • MOHAR, Bojan a Carsten THOMASSEN. Graphs on Surfaces. Johns Hopkins University Press, 2001. ISBN 0-8018-6689-8. URL info
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/stud-en.html#spring
Do not be afraid of this course if you like graphs. The topic is advanced, yet it will be given on a nicely accessible level.
Další komentáře
Předmět je vyučován jednou za dva roky.
Výuka probíhá každý týden.
Předmět je zařazen také v obdobích jaro 2006, jaro 2008, jaro 2010, jaro 2012, jaro 2014.

MA051 Advanced Graph Theory I

Fakulta informatiky
jaro 2011

Předmět se v období jaro 2011 nevypisuje.

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.
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
předmět má 19 mateřských oborů, zobrazit
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
  • MOHAR, Bojan a Carsten THOMASSEN. Graphs on Surfaces. Johns Hopkins University Press, 2001. ISBN 0-8018-6689-8. URL info
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.
Výuka probíhá každý týden.
Předmět je zařazen také v obdobích jaro 2006, jaro 2008, jaro 2010, jaro 2012, jaro 2014.

MA051 Advanced Graph Theory I

Fakulta informatiky
jaro 2009

Předmět se v období jaro 2009 nevypisuje.

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.
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
předmět má 16 mateřských oborů, zobrazit
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
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
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
Předmět je vyučován jednou za dva roky.
Výuka probíhá každý týden.
Předmět je zařazen také v obdobích jaro 2006, jaro 2008, jaro 2010, jaro 2012, jaro 2014.

MA051 Advanced Graph Theory I

Fakulta informatiky
jaro 2007

Předmět se v období jaro 2007 nevypisuje.

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.
Předpoklady
Usual basic knowledge of discrete mathematics and graphs. (See the book "Invitation to discrete mathematics".) 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
předmět má 8 mateřských oborů, zobrazit
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.
  • (A graph view of surface classification.)
  • 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
  • MATOUŠEK, Jiří a Jaroslav NEŠETŘIL. Kapitoly z diskrétní matematiky. Vyd. 2., opr. Praha: Karolinum, 2000, 377 s. ISBN 8024600846. info
Metody hodnocení
Written individual homework assignment (one), and a subsequent oral exam.
Vyučovací jazyk
Angličtina
Navazující předměty
Informace učitele
http://www.fi.muni.cz/~hlineny/Vyuka/
Další komentáře
Předmět je vyučován jednou za dva roky.
Výuka probíhá každý týden.
Předmět je zařazen také v obdobích jaro 2006, jaro 2008, jaro 2010, jaro 2012, jaro 2014.