MA052 Advanced Graph Theory II

Fakulta informatiky
jaro 2007
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
Usual basic knowledge of discrete mathematics and graphs. (See the book "Invitation to discrete mathematics".) Some knowledge of algorithmic complexity.
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
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.
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.
  • Extensions to structural matroid theory.
Literatura
  • DIESTEL, Reinhard. Graph theory. New York: Springer, 1998, xiv, 286. ISBN 0387982108. 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/Teaching/AGTS.html
Online access to the course book: Diestel, Reinhard. Graph theory. "http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/"
Supplementary literature: Nešetřil, Jaroslav - Matoušek, Jiří. Invitation to discrete mathematics. Oxford : Clarendon Press, 1998. xv, 410 s. ISBN 0-19-850207-9.
Students must read the course web page "http://www.fi.muni.cz/~hlineny/Teaching/AGTS.html" for information.
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 2009, jaro 2011, jaro 2013.