Barevnost grafů a kombinatorických struktur - NDMI060
Anglický název: Coloring of Graphs and Other Combinatorial Structures
Zajišťuje: Informatický ústav Univerzity Karlovy (32-IUUK)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2024
Semestr: zimní
E-Kredity: 3
Rozsah, examinace: zimní 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: nevyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Způsob výuky: prezenční
Garant: prof. Mgr. Zdeněk Dvořák, Ph.D.
Třída: DS, diskrétní modely a algoritmy
Informatika Mgr. - Diskrétní modely a algoritmy
Kategorizace předmětu: Informatika > Diskrétní matematika
Výsledky anket   Termíny zkoušek   Rozvrh   Nástěnka   
Anotace -
Barevnost grafů a jejich speciálních tříd (zejména grafů na plochách). Důkazové techniky používané při odhadech barevnosti grafů (pravděpodobnostní metoda, algebraické metody, metoda přerozdělování náboje). Tuttův polynom. Zobecnění a speciální typy barvení grafů: diagonální, cyklické, vybíravost, channel assignment, L(2,1)-barvení, T-barvení apod. Barevnost jiných kombinatorických struktur.
Poslední úprava: T_KAM (26.04.2003)
Podmínky zakončení předmětu -

Ústní zkouška.

Poslední úprava: Pangrác Ondřej, RNDr., Ph.D. (07.06.2019)
Literatura

1. Bollobas, B.: Modern Graph Theory. Springer-Verlag, New York (1998).

2. Tommy R. Jensen and Bjarne Toft. Graph Coloring Problems. Discrete Mathematics and Optimization. Wiley and Sons, New York, 1995.

3. R. Diestel, "Graph Theory," Graduate Texts in Math., Vol. 173, Springer-Verlag, New York, NY, 1997.

Poslední úprava: T_KAM (26.04.2003)
Požadavky ke zkoušce -

Zkouška proběhne ústní formou, v rozsahu 2-3 otázek pokrytých látkou probranou na přednáškách.

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

Barevnost grafů a jejich speciálních tříd (zejména grafů na plochách). Důkazové techniky používané při odhadech barevnosti grafů (pravděpodobnostní metoda, algebraické metody, metoda přerozdělování náboje). Tuttův polynom. Zobecnění a speciální typy barvení grafů: diagonální, cyklické, vybíravost, channel assignment, L(2,1)-barvení, T-barvení apod. Barevnost jiných kombinatorických struktur.

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