Homepage
Curriculum vitae
Publikace
Výuka
Kontakt
   

Teorie grafů     LS 2025/2026

Předmět: 470-4302: Teorie grafů   (TG)
Garant: Petr Kovář
Rozsah: 6 kreditů (2/2/0/0/2)
Akademický rok: 2025/2026

Osnova předmětu je v systému Edison.

Průběh semestru

Účast na cvičeních je povinná a účast na přednáškách je předpokládaná, neboť přednášky a cvičení navazují, případně se prolínají.

Průběh cvičení

Během semestru studenti odevzdají zápočtový projekt (maximálně za 20 bodů). Zápočet dostanou ti studenti, kteří za projekt získají alespoň 10 bodů.

Příklady k procvičení

Příklad k procvičení najdete v učebním textu, který je v seznamu literatury. Obsah souborů se průběžně aktualizuje.
Na zkoušku vybírám příklady vždy z učebního textu (z platné verze ke konci semestru). Pokud najdete v textu chyby, dejte mi, prosím, vědět.

 

Projekty   (20 bodů)

Můžete se podívat na seznam projektů z let 2007/2008, 2008/2009, 2009/2010, 2010/2011, 2011/2012, 2012/2013, 2013/2014, 2015/2016, 2016/2017, 2017/2018, 2018/2019, 2019/2020, 2020/2021, 2021/2022, 2022/2023, 2023/2024, 2024/2025 a 2025/2026 nebo na vzorový projekt ve formátu pdf: tg_vzorovy_projekt.pdf.

  1. Cykly v hyperkrychli   Vypočítejte a) počet cyklů délky 4, b) počet cyklů délky 5 a počet cyklů délky 6 v grafu hyperkrychle Qn. Ověřte obecné vztahy pro n = 1, 2, 3, 4. Podaří se vám spočítat také počet cyklů délky 8?
  2. Hra HEX   Hra HEX je popsána v kapitole 3. Ukažte, že ve hře HEX nemůže nastat remíza. Návod: využijte Spernerovo lemma (Lemma 3.16.).
  3. Tranzitivní grafy   Ukažte, že graf, který je hranově tranzitivní a není vrcholově tranzitivní, musí být bipartitní.
  4. Rovinný graf s velkým obvodem   Ukažte, že pokud má rovinný graf obvod alespoň 6, tak obsahuje vrchol stupně 2. Platí tvrzení i pro nerovinné grafy? Zdůvodněte.
  5. Věta o pěti barvách   Dokažte Větu o pěti barvách, tj. že pro každý planární graf G je χ(G) < 5.
  6. Königovo lemma   Dokažte Königovo lemma: Mějme souvislý graf G s nekonečně mnoha vrcholy, ve kterém je každý vrchol konečného stupně. Pak každý vrchol grafu G leží na nějaké cestě nekonečné délky.
  7. Úplná párování v kubickém grafu   Ukažte, že v kubickém grafu G bez mostů patří každá hrana do nějakého úplného párování grafu G.
  8. Hranová barvení 4-pravidelných grafů   Dokažte nebo vyvraťte: každý 4-pravidelný graf, který má úplné párování, je třídy 1.
  9. Lichý les   Lichým grafem rozumíme každý graf, který má všechny vrcholy lichého stupně. Ukažte, že každý les je možno rozložit na nejvýše dva liché podgrafy.
  10. Téma dle dohody

Témata, která jsou už zadaná, jsou šedá. Očekává se, že projekty budou vypracovány na úrovni, která odpovídá studentům magisterského nebo doktorského studia. Nezapomeňte na správné citace použitých zdrojů. Případná různá obtížnost témat bude kompenzována mírou, jak přísně budou projekty hodnoceny.

Termín odevzdání projektů je úterý 21. 4. 2026 (pro studenty posledního ročníku v zápočtovém týdnu).

 

Zkouška   (80 bodů)

Termíny zkoušek najdete ke konci semestru v systému Edison. Zkouška má část písemnou (řešení příkladů dle zadání) a část ústní (rozprava nad probíranými tématy).

 

Literatura

Je možné používat i jiné úvodní knihy a skripta, ovšem pozor: některé detaily se mohou lišit! (zejména definice pojmů) a u zkoušky platí to, co bylo probráno na přednášce.

 

Animace

Pro lepší pochopení vybraných pojmů můžete při studiu využít následující animace.

 

Konzultační hodiny

Zastihnete mne nejlépe osobně během konzultačních hodin. Během letního semestru 2025/2026 jsou stanoveny následující konzultační hodiny.

Best way to reach me is during my office hours. During Summer (Spring) Term 2025/2026 the office hours are the following.

DenČasMístnost
Pondělí/Monday10:00-11:00EA536*
*Dne 5.10.2026 konzultace nebudou.
Konzultace on-line po předchozí domluvě.

Po předchozí domluvě jsou konzultace možné i v jinou dobu. / Or by appointment.


email
kancelář EA536, tel. 596 995 972
Upraveno: 13.04.2026