Kombinatorika a grafy 2 - NDMX012
Anglický název: Combinatorics and Graph Theory 2
Zajišťuje: Studijní oddělení (32-STUD)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2020
Semestr: letní
E-Kredity: 6
Rozsah, examinace: letní 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í
Je zajišťováno předmětem: NDMI012
Garant: prof. Mgr. Zdeněk Dvořák, Ph.D.
doc. RNDr. Vít Jelínek, Ph.D.
Třída: Informatika Bc.
Kategorizace předmětu: Informatika > Diskrétní matematika
Prerekvizity : {NXXX014, NXXX015, NXXX016, NXXX017, NXXX018, NXXX022, NXXX023, NXXX024, NXXX025, NXXX033}
Neslučitelnost : NDMI012
Záměnnost : NDMI012
Je neslučitelnost pro: NDMI012
Je záměnnost pro: NDMI012
Výsledky anket   Termíny zkoušek   Nástěnka   
Anotace -
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 (10.04.2011)
Podmínky zakončení předmětu -

Podmínky získání zápočtu: Zápočet bude za zisk alespoň dvou třetin bodů ze standardních úkolů. Body bude možné získat dle uvážení cvičícího i za bonusové úkoly a aktivní účast na cvičeních.

Povaha kontroly předmětu vylučuje opravné termíny u zápočtů.

Zkoušku lze složit i před získáním zápočtu.

Poslední úprava: Veselý Pavel, Mgr., Ph.D. (12.02.2023)
Literatura -

R. Diestel: Graph theory, 3rd edition, Springer, 2005.

H. Wilf: Generatingfunctionology (https://www.math.upenn.edu/~wilf/DownldGF.html).

  • Videozáznamy přednášek
  • Poslední úprava: Kuchař Jan, PaedDr. (04.10.2016)
    Požadavky ke zkoušce -

    Zkouška má ústní formu, s možností písemné přípravy předcházející vlastnímu ústnímu zkoušení. Požadavky ke zkoušce odpovídají sylabu předmětu v rozsahu, v jakém byl pokryt na přednáškách a cvičeních. Je požadována i schopnost zobecnit a aplikovat získané teoretické znalosti při praktickém řešení kombinatorických úloh.

    Poslední úprava: Jelínek Vít, doc. RNDr., Ph.D. (11.10.2017)
    Sylabus -

    Párování v obecných grafech.

    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-souvislých grafech, Kuratowského věta.

    Barevnost grafů, Brooksova věta, Vizingova věta.

    Tutteho polynom: různé definice, význačné body, prostor cyklů a řezů grafu.

    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.

    Perfektni grafy, Dilworthova věta.

    Chordální grafy.

    Poslední úprava: Dvořák Zdeněk, prof. Mgr., Ph.D. (27.09.2020)