Grafy a počty - NDMI078

• Anglický název: Graphs and counting
• Zajišťuje: Katedra aplikované matematiky (32-KAM)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2020
• Semestr: letní
• E-Kredity: 3
• Rozsah, examinace: letní s.:2/0, Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: vyučován
• Jazyk výuky: angličtina
• Způsob výuky: prezenční
• Garant: prof. RNDr. Martin Loebl, CSc.
• Vyučující: prof. RNDr. Martin Loebl, CSc.
• Třída: Informatika Mgr. - volitelný
• Kategorizace předmětu: Informatika > Diskrétní matematika

Anotace

čeština

Přednáška ukazuje diskretní enumerace se společnými aplikacemi v teorii grafů a statistické fyzice.

Poslední úprava: Macharová Dana, JUDr. (06.01.2009)

angličtina

Discrete enumeration with applications in both graph theory and statistical physics.

Poslední úprava: Macharová Dana, JUDr. (06.01.2009)

Podmínky zakončení předmětu

čeština

Ústní zkouška.

Poslední úprava: Kynčl Jan, doc. Mgr., Ph.D. (31.05.2019)

angličtina

Oral exam.

Poslední úprava: Kynčl Jan, doc. Mgr., Ph.D. (31.05.2019)

Literatura

čeština

Mohar, Thomassen, Graphs on surfaces, The Johns Hopkins University Press,

2001.

Stanley, Enumerative Combinatrics I, Cambridge University Press 1997.

Loebl, M.: Discrete mathematics and statistical physics; introductory lecture

notes (připravovaná skripta)

Poslední úprava: Macharová Dana, JUDr. (06.01.2009)

Požadavky ke zkoušce

čeština

Zkouška je ústní. Požadavky odpovídají sylabu v míře pokryté přednáškami.

Poslední úprava: Kynčl Jan, doc. Mgr., Ph.D. (24.05.2019)

angličtina

For the main exam, the requirements correspond to the syllabus as covered by the lectures.

Poslední úprava: Kynčl Jan, doc. Mgr., Ph.D. (24.05.2019)

Sylabus

čeština

Algebraická struktura cyklů a řezů v grafech

Duality enumerací: věta MacWilliamsové

Souvislost s partiční funkcí Isingova problému

Ekvivalence generujících funkcí řezu, sudých podmnožin a perfektních

párování

Algoritmické aspekty

Poslední úprava: Loebl Martin, prof. RNDr., CSc. (30.12.2020)

angličtina

Algebraic structure of cycles and cuts of graphs

Duality of enumeration: MacWilliams' theorem

Connections with the Ising partition function

Equivalence of basic generating functions

Algorithmic aspects

Poslední úprava: Loebl Martin, prof. RNDr., CSc. (30.12.2020)