MA052 Advanced Graph Theory II

Fakulta informatiky
jaro 2009
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í)
RNDr. Robert Ganian, Ph.D. (pomocník)
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–16:50 B411
Předpoklady
Teorie grafů MA010. Dále je vhodná úvodní znalost výpočetní složitosti a predikátové logiky.
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
Cíle předmětu
Tzv. strukturální teorie grafů zažívá v poslední době nebývalý rozmach spojený s Teorií grafových minorů Robertsona a Seymoura, což je jeden z nejhlubších výsledků dosažených v diskrétní matematice vůbec. Mimo jiné z této teorie vyplývá existence polynomiálních algoritmů pro velkou třídu grafových problémů, kde často ani není jasné, proč by měly být tyto problémy algoritmicky řešitelné. Náplní přednášky je uvedení do celé oblasti strukturální teorie grafů a jejích aplikací. Jsou vyloženy či alespoň naznačeny principy, na kterých tato teorie i její algoritmická využití stojí. Velký důraz je kladen především na "šířkové" parametry grafů jako je tree-width nebo branch-width.
Studenti se především naučí nejnovější velmi pokročilé poznatky zmíněné oblasti teorie grafů.
Osnova
  • Repetition of basic graph terms.
  • Connectivity on graphs, different measures. Menger's theorem. Linking, submodular functions.
  • Width decompositions and measures: tree-width, branch-width. Algorithmic applications.
  • Minors and their basic properties, well-quasi-ordering, WQO on trees.
  • Planar graphs, drawing on surfaces, forbidden minors.
  • The Graph Minor Theorem, an outline.
  • Advanced width measures: clique-width, rank-width.
  • MS2- and MS1-theorems.
Literatura
  • DIESTEL, Reinhard. Graph theory. New York: Springer, 1998, xiv, 286. ISBN 0387982108. 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/AGTS.html
Free online access to the course book: Diestel, Reinhard. Graph theory. "http://diestel-graph-theory.com/GrTh.html"
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.
Předmět je zařazen také v obdobích jaro 2007, jaro 2011, jaro 2013.