Kombinatorika a grafy II - NDMI012
| Anglický název: |
Combinatorics and Graph Theory II |
| Zajišťuje: |
Informatický ústav Univerzity Karlovy (32-IUUK) |
| Fakulta: |
Matematicko-fyzikální fakulta |
| Platnost: |
od 2013 do 2014 |
| Semestr: |
zimní |
| E-Kredity: |
6 |
| Rozsah, examinace: |
zimní s.:2/2, Z+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: |
čeština |
| Způsob výuky: |
prezenční |
| Způsob výuky: |
prezenční |
|
|
| Anotace -
| |
|
Poslední úprava: T_KAM (10.04.2011)
Přehledová přednáška o klasických výsledcích v kombinatorice a teorii grafů. Předpokládají se znalosti v rozsahu
NDMI011 nebo NDMA001.
Poslední úprava: T_KAM (20.04.2008)
The lecture extends NDMI011. An overview lecture on classical results in combinatorics and graph
theory.
|
| Literatura -
| |
|
Poslední úprava: doc. RNDr. Vít Jelínek, Ph.D. (23.06.2016)
R. Diestel, Graph theory, 3rd edition, Springer, 2005.
S. Jukna, Extremal combinatorics with application in computer science, Springer, 2001.
Poslední úprava: doc. RNDr. Vít Jelínek, Ph.D. (23.06.2016)
R. Diestel, Graph theory, 3rd edition, Springer, 2005.
S. Jukna, Extremal combinatorics with application in computer science, Springer, 2001.
|
| Sylabus -
| |
|
Poslední úprava: doc. RNDr. Pavel Töpfer, CSc. (26.01.2018)
- Tutteho a Petersenova věta
- Hamiltonovské kružnice, Oreho podmínka, Chvátalův uzávěr
- Plochy vyššího rodu, zobecněná Eulerova formule, Heawoodova formule
- Lemma o kontrahovatelné hraně, Tutteho věta o 3-souv. grafech, Kuratowského věta
- Barevnost grafů, Brooksova věta, Vizingova věta
- Tutteho polynom: různé definice, význačné body
- Obyčejné a exponenciální vytvořující funkce
- Burnsideovo lemma, Pólyova enumerace, příklady aplikací
- Věta o slunečnici, Erdös-Ko-Radoova věta, Turánova věta
- Dilworthova věta, pojem perfektních grafů
Poslední úprava: doc. RNDr. Pavel Töpfer, CSc. (26.01.2018)
- Tutte's and Petersen's theorem
- Hamilton cycles, Ore's theorem, Chvátal closure
- Surfaces of higher genus, generalized Euler's formula, Heawood's formula
- Tutte's theorem on 3-connected graphs, Kuratowski's theorem
- Brooks' theorem, Vizing's theorem
- Tutte polynomial: equivalent definitions, important points
- Ordinary and exponential generating functions
- Burnside's lemma, Póla's enumeration
- Sunflower theorem, Erdös-Ko-Rado theorem, Turán's theorem
- Dilworth's theorem, perfect graphs
|
|
